反向地图查找

我有1对1的地图。什么是找到值的键的最佳方式，反向地图查找

即

为例子，如果地图是这个

KEY VALUE

a 1 
b 2 
c 3 
d 4

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

谢谢！

来源

2011-04-21 user620189

你可以做的事情不多。您可以选择使用两张地图，使用来自Boost Multi-Index库的多密钥地图，或进行线性搜索。

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

来源

2011-04-21 19:53:22

最直接的方法是维护一个平行的地图，其中的值和关键是相反的（因为关系是一对一的）。

来源

2011-04-21 19:54:25 MAK

除非地图是巨大的，或者你有知道线性搜索太慢的一些其他的方式，我开始与线性搜索：

#include <iostream> 
using std::cout; 

#include <map> 
using std::map; 

#include <algorithm> 
using std::find_if; 

#include <boost/assign/list_of.hpp> 
using boost::assign::map_list_of; 

typedef map<char, int> Map; 
typedef Map::key_type Key; 
typedef Map::value_type Pair; 
typedef Map::mapped_type Value; 


struct finder { 
    const Value v; 
    finder(const Value& v) : v(v) {} 
    bool operator()(const Pair& p) { 
     return p.second == v; 
    } 
}; 

Map m = map_list_of('a', 1)('b', 2)('c', 3)('d', 4)('e', 5); 

int main() { 
    Pair v = *find_if(m.begin(), m.end(), finder(3)); 
    cout << v.second << "->" << v.first << "\n"; 
}

来源

2011-04-21 20:02:51

我最近回用C++经过20多年使用其它语言的，所以我有相当多的铁锈。有没有一种方法来实现finder作为内联lambda函数/表达式？ – WXB13 2013-11-05 06:41:25

另一种解决方案是使用（鲜为人知？）Boost.Bimap：

Boost.Bimap是双向映射库C++。通过Boost.Bimap，您可以在中创建关联容器，这两种类型都可以用作关键字。 A bimap<X,Y>可以被认为是std::map<X,Y>和 std::map<Y,X>的组合。 bimap的学习曲线几乎是平坦的，如果你知道如何使用标准容器。一个很好的努力已被放入映射Boost.Bimap中的STL 的命名方案。该库是设计用来匹配常见的STL 容器。

来源

2011-04-21 20:24:33

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

来源

2012-06-03 05:42:54 Amit

上@Robᵩ的回答上面使用拉姆达的变化：

map<char, int> m = {{'a', 1}, {'b', 2}, {'c', 3}, {'d', 4}, {'e', 5}}; 

int findVal = 3; 
auto it = find_if(m.begin(), m.end(), [findVal](const Pair & p) { 
    return p.second == findVal; 
}); 
if (it == m.end()) { 
    /*value not found*/ 
    cout << "*value not found*"; 
} 
else { 
    Pair v = *it; 
    cout << v.second << "->" << v.first << "\n"; 
}

（感谢@Nawaz为他/她的贡献在这里：https://stackoverflow.com/a/19828596/1650814）

来源

2013-11-07 06:42:28 WXB13

我知道这是一个非常古老的问题，但这个codeproject文章（http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map）是双向映射的一个很好的例子。

这是一个示例程序，说明它是多么容易：

#pragma warning(disable:4503) 

    #include "bimap.h" 
    #include <iostream> 
    #include <string> 

    using codeproject::bimap; 

    int main(void) 
    { 
     bimap<int,std::string> bm; 

     bm[1]="Monday"; 
     bm[2]="Tuesday"; 
     bm[3]="Wednesday"; 
     bm[4]="Thursday"; 
     bm[5]="Friday"; 
     bm[6]="Saturday"; 
     bm[7]="Sunday"; 

     std::cout<<"Thursday occupies place #"<<bm["Thursday"]<< 
       " in the week (european style)"<<std::endl; 
     return 0; 
    }

来源

2014-10-09 15:34:40

反向地图查找

回答

相关问题