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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Categories

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!