反向地图查找

Question

我有1对1的地图.从值中查找键的最佳方法是什么,

即

例如,如果地图是这样的

核心价值

a    1
b    2
c    3 
d    4

我希望能够找到对应于3的键是C.

谢谢!

Answer 1

你无能为力.您可以选择使用两个地图,使用Boost Multi-Index库中的多键地图,或进行线性搜索.

更新:最轻量级的开箱即用解决方案似乎是Boost.Bimap,它代表双向地图.

Answer 2

假设你有一张地图<X,Y>.构建第二个结构,可能是一个<Y*,X*,Deref>启用反向查找的映射,但避免将存储开销加倍,因为使用指针时,不需要存储每个X和Y两次.第二个结构只是指向第一个结构.

Answer 3

最直接的方法是维护一个平行映射,其中值和键被反转(因为关系是一对一的).

Answer 4

另一个解决方案是使用(鲜为人知的？)Boost.Bimap:

Boost.Bimap是一个用于C++的双向映射库.使用Boost.Bimap,您可以创建关联容器,其中两种类型都可以用作键.A bimap<X,Y>可以被认为是a std::map<X,Y>和a 的组合std::map<Y,X>.如果您知道如何使用标准容器,那么bimap的学习曲线几乎是平坦的.在Boost.Bimap中映射STL的命名方案已经付出了很多努力.该库旨在匹配常见的STL容器.

Answer 5

给定std::map从键到值，以下函数将返回一个反向查找表，std::map从值到键。

    /// Given a map from keys to values, creates a new map from values to keys 
    template<typename K, typename V>
    static map<V, K> reverse_map(const map<K, V>& m) {
        map<V, K> r;
        for (const auto& kv : m)
            r[kv.second] = kv.first;
        return r;
    }