c++ efficient data structure for bidirectional random access

c++, data-structures, dictionary

Solution

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>>`.

Problem

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

Original source