Reverse lookup of an STL map (Finding map's key by its value in C++)

This post will discuss how to perform a reverse lookup of a map in C++. In reverse lookup, we can find a map’s key by its value.

1. Using `std::for_each` function

If the given value is mapped to the multiple keys, the recommended approach is to iterate the map using range-based for-loop or std::for_each algorithm and retrieve all keys having given value in the map, as shown below:

#include <iostream>

#include <unordered_map>

#include <algorithm>

int main()

{

std::unordered_map<char, int> m = {

{'A', 1}, {'B', 2}, {'C', 1}, {'D', 3}, {'E', 3}

};

int value = 1;

bool found = false;

std::for_each(m.begin(), m.end(),

[&value, &found](const std::pair<char, int> &p)

{

if (p.second == value)

{

std::cout << p.first << " -> " << p.second << std::endl;

found = true;

}

});

if (!found) {

std::cout << "Key with given value not found";

}

return 0;

}

Download Run Code

Output:

A -> 1
C -> 1

2. Using `std::find_if` function

If the given value is mapped to a single key, we can use the standard algorithm std::find_if that conditionally searches a given range of elements.

The following code uses std::find_if with lambdas (introduced in C++11), which can also be replaced with an object of a class for which the () operator (function call operator) is overloaded (see code here).

#include <iostream>

#include <unordered_map>

#include <algorithm>

int main()

{

std::unordered_map<char, int> m = {

{'A', 65}, {'B', 66}, {'C', 67}, {'D', 68}, {'E', 69}

};

int value = 65;

auto it = std::find_if(m.begin(), m.end(),

[&value](const std::pair<char, int> &p) {

return p.second == value;

});

if (it == m.end()) {

std::cout << "Key with given value not found";

}

else {

std::cout << it->first << " -> " << it->second << std::endl;

}

return 0;

}

Download Run Code

Output:

A -> 65

3. Using Inverse Map

Another good alternative is to construct an inverse map std::unordered_map<V,K> from the original map std::unordered_map<K,V> that can easily do the reverse lookup in constant time.

We can easily build the inverse map by iterating the original map using a simple for-loop or range-based for-loop (in C++11, see code here) or std::for_each algorithm. Notice that this works only if we have 1:1 mapping between keys and values.

#include <iostream>

#include <unordered_map>

#include <algorithm>

template<typename K, typename V>

std::unordered_map<V, K> inverse_map(std::unordered_map<K, V> &map)

{

std::unordered_map<V, K> inv;

std::for_each(map.begin(), map.end(),

[&inv] (const std::pair<K, V> &p) {

inv.insert(std::make_pair(p.second, p.first));

});

return inv;

}

int main()

{

std::unordered_map<char, int> m = {

{'A', 65}, {'B', 66}, {'C', 67}, {'D', 68}, {'E', 69}

};

int value = 65;

std::unordered_map<int, char> inverse = inverse_map(m);

auto it = inverse.find(value);

if (it == inverse.end()) {

std::cout << "Key with given value not found";

}

else {

std::cout << it->second << " -> " << it->first << std::endl;

}

return 0;

}

Download Run Code

Output:

A -> 65

4. Using `Boost.Bimap` function

Another good solution is to use the Boost.Bimap library for building bidirectional maps in C++. With Boost.Bimap, we can create associative containers in which both types can be used as a key, i.e., bimap<X,Y> can be thought of as a combination of a std::map<X,Y> and a std::map<Y,X>.

#include <iostream>

#include <boost/bimap.hpp>

int main()

{

boost::bimap<char, int> bimap;

bimap.insert({'A', 65});

bimap.insert({'B', 66});

bimap.insert({'C', 67});

bimap.insert({'D', 68});

bimap.insert({'E', 69});

int value = 65;

auto it = bimap.right.find(value);

if (it->first != value) {

std::cout << "Key with given value not found";

}

else {

std::cout << it->second << " -> " << it->first << std::endl;

}

return 0;

}

Download Code

Output:

A -> 65

That’s all about reverse lookup of an STL map.

Reverse lookup of an STL map (Finding map’s key by its value in C++)

1. Using std::for_each function

2. Using std::find_if function

3. Using Inverse Map

4. Using Boost.Bimap function

Share this:

1. Using `std::for_each` function

2. Using `std::find_if` function

4. Using `Boost.Bimap` function