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

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

 

1. std::for_each

If the given value is mapped to the multiple keys, the recommended approach would be 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:

 

Download   Run Code

Output:

A -> 1
C -> 1

 

2. std::find_if

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

Below code uses std::find_if with lamdbas (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).

 

Download   Run Code

Output:

A -> 65

 

3. 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.

 

Download   Run Code

Output:

A -> 65

 

4. Boost.Bimap

Another good solution is to use 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 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>.

 

Download   Run Code

Output:

A -> 65

 
Thanks for reading.

Please use online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
terribleNoCP
Guest

A programming website to help people but you can’t copy and paste. Terrible!