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

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

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

Solution

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!)