CODEWITHSUNDEEP
c++stldictionary
user620189
user620189

Reputation: 2693

Reverse map lookup

I have a 1 to 1 map. What's the best way to find keys from values,

i.e.

For examples if the map is this

KEY VALUE

a    1
b    2
c    3 
d    4

I want to be able to find that key corresponding to 3 is C.

Thanks!

Upvotes: 59

Views: 63755

Answers (8)

cdiggins
cdiggins

Reputation: 18213

Given a std::map from keys to values, the following function will return a reverse lookup table, a std::map from values to keys.

    /// Given a map from keys to values, creates a new map from values to keys 
    template<typename K, typename V>
    static map<V, K> reverse_map(const map<K, V>& m) {
        map<V, K> r;
        for (const auto& kv : m)
            r[kv.second] = kv.first;
        return r;
    }

Upvotes: 9

Eugen Constantin Dinca
Eugen Constantin Dinca

Reputation: 9140

Another solution would be to use (the less known?) Boost.Bimap:

Boost.Bimap is a bidirectional maps library for C++. With Boost.Bimap you can create associative containers in which both types can be used as key. A bimap<X,Y> can be thought of as a combination of a std::map<X,Y> and a std::map<Y,X>. The learning curve of bimap is almost flat if you know how to use standard containers. A great deal of effort has been put into mapping the naming scheme of the STL in Boost.Bimap. The library is designed to match the common STL containers.

Upvotes: 7

Yannick Lange
Yannick Lange

Reputation: 131

I know this is a really old question but this codeproject article (http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map) is a pretty good example of a bidirectional map.

This is an example program that shows how easy it is:

 #pragma warning(disable:4503)

    #include "bimap.h"
    #include <iostream>
    #include <string>

    using codeproject::bimap;

    int main(void)
    {
      bimap<int,std::string> bm;

      bm[1]="Monday";
      bm[2]="Tuesday";
      bm[3]="Wednesday";
      bm[4]="Thursday";
      bm[5]="Friday";
      bm[6]="Saturday";
      bm[7]="Sunday";

      std::cout<<"Thursday occupies place #"<<bm["Thursday"]<<
                 " in the week (european style)"<<std::endl;
      return 0;
    }

Upvotes: 3

WXB13
WXB13

Reputation: 1126

A variation on @Robᵩ's answer above that uses a lambda:

map<char, int> m = {{'a', 1}, {'b', 2}, {'c', 3}, {'d', 4}, {'e', 5}};

int findVal = 3;
auto it = find_if(m.begin(), m.end(), [findVal](const Pair & p) {
    return p.second == findVal;
});
if (it == m.end()) {
    /*value not found*/
    cout << "*value not found*";
}
else {
    Pair v = *it;
    cout << v.second << "->" << v.first << "\n";
}

(thanks to @Nawaz for his/her contribution here: https://stackoverflow.com/a/19828596/1650814)

Upvotes: 6

Amit
Amit

Reputation: 131

Say you have a map<X,Y>. Build a second structure, perhaps a map<Y*,X*,Deref> that enables the reverse lookup but avoids doubling the storage overhead, because, using pointers, there's no need to store each X and Y twice. The second structure simply has pointers into the first.

Upvotes: 13

user405725
user405725

Reputation:

There isn't much you can do about it. Your have options to work with two maps, use multi-key map like one from Boost Multi-Index library, or do linear search.

UPDATE: The most lightweight out of the box solution seems to be Boost.Bimap, which stands for bi-directional map.

Upvotes: 38

Robᵩ
Robᵩ

Reputation: 168626

Unless the map is huge, or you have some other way of knowing that linear search is too slow, I'd start with linear search:

#include <iostream>
using std::cout;

#include <map>
using std::map;

#include <algorithm>
using std::find_if;

#include <boost/assign/list_of.hpp>
using boost::assign::map_list_of;

typedef map<char, int> Map;
typedef Map::key_type Key;
typedef Map::value_type Pair;
typedef Map::mapped_type Value;


struct finder {
    const Value v;
    finder(const Value& v) : v(v) {}
    bool operator()(const Pair& p) {
        return p.second == v;
    }
};

Map m = map_list_of('a', 1)('b', 2)('c', 3)('d', 4)('e', 5);

int main() {
    Pair v = *find_if(m.begin(), m.end(), finder(3));
    cout << v.second << "->" << v.first << "\n";
}

Upvotes: 4

MAK
MAK

Reputation: 26586

The most direct way would be to maintain a parallel map where the values and keys are reversed (since the relationship is one to one).

Upvotes: 12

Related Questions