CODEWITHSUNDEEP
c++data-structuresdictionary
Draess
Draess

Reputation: 218

c++ efficient data structure for bidirectional random access

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

Upvotes: 9

Views: 1700

Answers (3)

Vargan
Vargan

Reputation: 1317

Map and Multimap haves an efficiency of O(log n), so, I think is the best way to store your data. I suggest to use

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

Upvotes: 1

Fred Foo
Fred Foo

Reputation: 363587

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

Upvotes: 7

ForEveR
ForEveR

Reputation: 55887

How about boost::bimap? http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html I think it's for you.

Upvotes: 2

Related Questions