In a C++ map, is there any way to search for the key given a value?

Question

In a C++ std::map, is there any way to search for the key given the mapped value? Example:

I have this map:

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

Is there any way that I can find the corresponding int, given the value "foo"?

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

Output: 0

Answer 1

std::map doesn't provide a (fast) way to find the key of a given value.

What you want is often called a "bijective map", or short "bimap". Boost has such a data structure. This is typically implemented by using two index trees "glued" together (where std::map has only one for the keys). Boost also provides the more general multi index with similar use cases.

If you don't want to use Boost, if storage is not a big problem, and if you can affort the extra code effort, you can simply use two maps and glue them together manually:

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"];

Of course you can wrap those two maps in a class and provide some useful interface, but this might be a bit overkill, and using two maps with the same content is not an optional solution anyways. As commented below, exception safety is also a problem of this solution. But in many applications it's already enough to simply add another reverse map.

Please note that since std::map stores unique keys, this approach will support backward lookup only for unique values, as collisions in the value space of the forward map correspond to collisions in the key space of the backward map.