which data structure should be used multimap, boost::bimap, multiset or any other

Question

In my program there are some users and their clients. I have the list of users and their associated clients.

Example

U1 -> c1, c2, c3, c5, c8, c10, c12
U2 -> c3, c5, c13, c8, c12, c14
U3 -> C2, C5, c8, c11, c12, c14
..
...
....
.....
and many more.

some clients are common in user's list.

I want to make reverse hierarchy of clients to users . If any update comes for any client then it will goes to only those users for which the client is associated.

Please suggest me which data structure should be used map, multimap, boost::bimap, multiset

Answer 1

Perhaps this is a use case for a Boost.Bimap where both keys are multisets, and an entry in the bimap represents a single connection between a user and the client. So for the following setup

U1 -> C1 C2 C3
U2 -> C4 C1
U3 -> C5 C1

you would have entries (U1, C1), (U1, C2), (U1, C3), (U2, C4), (U2, C1), (U3, C5) and (U3, C1).

You can traverse both keys in their order, i.e. U1, U1, U1, U2, U3 on the left and C1, C1, C1, C2, C3, C4, C5 on the right. (Note how both sides contain repeated entries!)

Answer 2

What you need here is a bimultimap in fact and I believe there is not such thing implemented in boost. What I suggest is that you have an map<int, vector<int> > user_clients (here of course map may also be unordered_map) and another map: map<int, vector<int> > client_users. You will have to keep them in sync. Probably creating a wrapper class to do that for you is the best option.

Answer 3

You need bi*multi*map as Ivaylo Strandjev said, and in fact there is one. What you need is

boost::bimap<multiset_of<User>, multiset_of<Client>>