C++高效双向随机访问的数据结构

Question

我有两个集合A和B，分别包含元素a和b。现在这两个集合是相关的（0..1:n基数），所以每个a最多只有一个伙伴在B中，而每个b可以与A中的多个元素关联（至少一个）。 A是一个整数对的集合，B是整数。

是否有有效的方法来存储这样一个“双向”映射？ 一种简单的方法是使用两个映射：

Translated:

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

也许有更高效的处理方法。感谢您的帮助。

- Draess

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>>实现。

- Fred Foo

Answer 2

那么boost::bimap怎么样？http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html 我认为这个对你很有帮助。

- ForEveR

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

- Vargan