c ++用于双向随机访问的高效数据结构

Question

我有两组A和B的元素a和b.现在这些元素彼此相关(0..1:n基数),所以每个a在B中最多只有一个伙伴,每个b可以有几个(至少一个)与A中项目的关联.A是一组整数对,B是整数.

有没有有效的方法存储这样的"双向"地图？一种简单的方法是使用两张地图:

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

但也许有更好的方法可以更有效地处理这个问题.

谢谢你的帮助

Answer 1

Boost包含两个处理这个的库:Boost.Bimap和Boost.MultiIndex.前者是特定于双向("双向")映射的问题,而第二种是更通用的,并且实现类似于具有任意索引的内存数据库的东西.

鉴于您的unsigned int密钥没有唯一映射到您的对,我认为MultiIndex更加有序.自从我上次使用这个库以来已经有很长一段时间了,但是看一下教程,你需要这样的东西

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;

如果您不想使用Boost,那么您至少可以通过替换来简化当前设置

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

通过std::multimap<unsigned, std::pair<unsigned, unsigned>>.