c++ - 在 C++ 映射中，有没有办法在给定值的情况下搜索键？

Question

在 C++ std::map 中，有什么方法可以在给定映射值的情况下搜索键？示例:

我有这张 map :

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

在给定值 "foo" 的情况下，有什么方法可以找到相应的 int 吗？

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

Output: 0

Answer 1

std::map 不提供(快速)查找给定值的键的方法。

你想要的通常被称为“双射映射”，或简称“双映射”。 Boost has such a data structure.这通常是通过使用“粘合”在一起的两个索引树来实现的(其中 std::map 只有一个用于键)。 Boost also provides the more general multi index with similar use cases.

如果您不想使用 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"];

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

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