在C++映射中,有没有办法搜索给定值的键？

Question

在C++中std::map,有没有办法在给定映射值的情况下搜索密钥？例:

我有这张地图:

map<int,string> myMap;
myMap[0] = "foo";

有没有什么方法可以找到相应的int,给定值"foo"？

cout << myMap.some_function("foo") <<endl;

Output: 0

Answer 1

std::map 没有提供(快速)方法来查找给定值的键.

你想要的通常被称为"双射地图",或简称为"bimap".Boost有这样的数据结构.这通常通过使用两个"粘合"在一起的索引树来实现(其中std::map只有一个用于键).Boost还提供了具有类似用例的更通用的多索引.

如果您不想使用Boost,如果存储不是一个大问题,并且您可以使用额外的代码工作,您可以简单地使用两个地图并手动将它们粘合在一起:

std::map<int, string> myMapForward;
std::map<string, int> myMapBackward;    // maybe even std::set

// insertion becomes:
myMapForward.insert(std::make_pair(0, "foo"));
myMapBackward.insert(std::make_pair("foo", 0));

// forward lookup becomes:
myMapForwar[0];

// backward lookup becomes:
myMapBackward["foo"];

当然,您可以将这两个映射包装在一个类中并提供一些有用的接口,但这可能有点过分,并且使用两个具有相同内容的映射无论如何都不是可选的解决方案.如下所述,异常安全性也是该解决方案的问题.但在许多应用程序中,只需添加另一个反向映射就足够了.

请注意,由于std::map存储唯一键,此方法仅支持对唯一值的后向查找,因为前向映射的值空间中的冲突对应于后向映射的键空间中的冲突.