c++ efficient data structure for bidirectional random access

Question

I have elements a and b of two sets A and B. Now these are related to each other (0..1:n cardinality) so each a has at most one partner in B and each b can have several (at least one) associations to items in A. A is a set of integer pairs and B are integers.

Is there efficient way to store such a "bi-directional" map? A simple approach would be to use two maps:

map<pair<unsigned int, unsigned int>, unsigned int> AtoB
map<unsigned int, vector<pair<unsigned int, unsigned int> > > BtoA

But perhaps there is good way to deal with this more efficiently.

Thanks for your help

Answer 1

Boost contains two libraries to deal with this: Boost.Bimap and Boost.MultiIndex. The former is specific to the problem of bijective ("bidirectional") maps, while the second is more general and implements something akin to an in-memory database with arbitrary indexes.

Given that your unsigned int keys don't uniquely map to your pairs, I think MultiIndex is more in order. It's a long time since I've last used this library, but looking at the tutorial, you would need something like

struct YourData {
     unsigned key;
     std::pair<unsigned, unsigned> value;
};

typedef multi_index_container<
    YourData,
    indexed_by<
        ordered_non_unique<member<YourData, unsigned, &YourData::key> >,
        ordered_unique<member<YourData, std::pair<unsigned, unsigned>,
                              &YourData::value> >
    >
> YourContainer;

If you don't want to use Boost, then you can at least simplify your current setup by replacing the

map<unsigned int, vector<pair<unsigned int, unsigned int> > >

by an std::multimap<unsigned, std::pair<unsigned, unsigned>>.