9

我有两个集合 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

但也许有更好的方法来更有效地处理这个问题。

谢谢你的帮助

4

3 回答 3

7

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

于 2012-11-16T09:49:04.217 回答
2

怎么样boost::bimap？http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html我认为它适合你。

于 2012-11-16T09:48:05.670 回答
1

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

map<pair<unsigned int, unsigned int>, unsigned int> AtoB
multimap<pair<unsigned int, unsigned int>, unsigned int> BtoA
于 2012-11-16T10:14:07.630 回答