用于双向随机访问的 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>>.

Answer 2

boost::bimap怎么样？ http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html 我认为这是给你的。

Answer 3

Map 和 Multimap 的效率为 O（log n），因此，我认为这是存储数据的最佳方式。我建议使用

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