C++中按键值/值对快速反向查找的建议方法

Question

我需要在C++内存中有一个大键/值对数组，它可能类似于下面的内容。然而，现实世界的例子将是成千上万的记录：

key    value
-----  -----
1      20
2      20
3      12
4      3
5      blank
6      3
7      blank
...

给定'3‘值，我需要快速反向查找匹配的键(本例中为4&6)。我想避免重复列表。在C++中有推荐的解决方案吗？

我更喜欢使用Qt库。我看过QMap和QHash，但是快速反向查找似乎不是一种选择吗？

Answer 1

在C++中有推荐的解决方案吗？

如果Boost是一种选择(我知道你更喜欢Qt)。那么您可以使用Boost.Bimap

Boost.Bimap是C++的双向映射库。使用Boost.Bimap，您可以创建两个类型都可以用作键的关联容器。bimap可以被看作是std::map和std::map的组合。如果您知道如何使用标准容器，那么bimap的学习曲线几乎是平坦的。在Boost.Bimap中对STL命名方案的映射进行了大量的研究。这个库被设计成与普通的STL容器匹配。

否则，由于Qt没有合适的数据结构.你可以用两张地图来达到你的目标。但是，它会复制内存。

Answer 2

你要找的是双向地图概念。遗憾的是，Qt并没有提供一个现成的解决方案。

如果您只想使用Qt库，则必须维护两个QMap(或QHashes或类似的东西)。

QMap<int, QPair<int,bool> > forwardLookupMap
QMap<QPair<int, bool>, int> reverseLookupMap

您必须手动维护反向查找映射，这很麻烦，而且内存需求看起来也不太好。

替代选项是使用第三方实现，如Boost.Bimap。