C++ 反向地图查找
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5749073/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Reverse map lookup
提问by user620189
I have a 1 to 1 map. What's the best way to find keys from values,
我有一张 1 比 1 的地图。从值中查找键的最佳方法是什么，
i.e.
IE
For examples if the map is this
例如，如果地图是这个
KEY VALUE
核心价值
a 1
b 2
c 3
d 4
I want to be able to find that key corresponding to 3 is C.
我希望能够找到对应于 3 的键是 C。
Thanks!
谢谢！
采纳答案by user620189
There isn't much you can do about it. Your have options to work with two maps, use multi-key map like one from Boost Multi-Indexlibrary, or do linear search.
你对此无能为力。您可以选择使用两张地图、使用多键地图（如Boost Multi-Index库中的一张）或进行线性搜索。
UPDATE:The most lightweight out of the box solution seems to be Boost.Bimap, which stands for bi-directional map.
更新：最轻量级的开箱即用解决方案似乎是Boost.Bimap，它代表双向地图。
回答by Amit
Say you have a map<X,Y>. Build a second structure, perhaps a map<Y*,X*,Deref>that enables the reverse lookup but avoids doubling the storage overhead, because, using pointers, there's no need to store each X and Y twice. The second structure simply has pointers into the first.
假设你有一张地图<X,Y>。构建第二个结构，可能是一个<Y*,X*,Deref>启用反向查找但避免双倍存储开销的映射，因为使用指针，无需将每个 X 和 Y 存储两次。第二个结构只是指向第一个结构的指针。
回答by MAK
The most direct way would be to maintain a parallel map where the values and keys are reversed (since the relationship is one to one).
最直接的方法是维护一个并行映射，其中值和键是颠倒的（因为关系是一对一的）。
回答by Eugen Constantin Dinca
Another solution would be to use (the less known?) Boost.Bimap:
另一种解决方案是使用（鲜为人知的？）Boost.Bimap：
Boost.Bimap is a bidirectional maps library for C++. With Boost.Bimap you can create associative containers in which both types can be used as key. A
bimap<X,Y>can be thought of as a combination of astd::map<X,Y>and astd::map<Y,X>. The learning curve of bimap is almost flat if you know how to use standard containers. A great deal of effort has been put into mapping the naming scheme of the STL in Boost.Bimap. The library is designed to match the common STL containers.
Boost.Bimap 是 C++ 的双向映射库。使用 Boost.Bimap 您可以创建关联容器，其中两种类型都可以用作键。A
bimap<X,Y>可以被认为是 astd::map<X,Y>和 a 的组合std::map<Y,X>。如果您知道如何使用标准容器，bimap 的学习曲线几乎是平坦的。在 Boost.Bimap 中映射 STL 的命名方案已经投入了大量的精力。该库旨在匹配常见的 STL 容器。
回答by Rob?
Unless the map is huge, or you have some other way of knowing that linear search is too slow, I'd start with linear search:
除非地图很大，或者您有其他方式知道线性搜索太慢，否则我将从线性搜索开始：
#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";
}
回答by WXB13
A variation on @Rob?'s answer above that uses a lambda:
上面使用 lambda 的@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";
}
(thanks to @Nawaz for his/her contribution here: https://stackoverflow.com/a/19828596/1650814)
（感谢@Nawaz 在这里的贡献：https://stackoverflow.com/a/19828596/1650814 ）
回答by Yannick Lange
I know this is a really old question but this codeproject article (http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map) is a pretty good example of a bidirectional map.
我知道这是一个非常古老的问题，但是这篇 codeproject 文章（http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map）是双向映射的一个很好的例子。
This is an example program that shows how easy it is:
这是一个示例程序，显示了它是多么容易：
#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;
}
回答by cdiggins
Given a std::mapfrom keys to values, the following function will return a reverse lookup table, a std::mapfrom values to keys.
给定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;
}
