Reverse map lookup
C++StlMapC++ Problem Overview
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!
C++ Solutions
Solution 1 - C++
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.
Solution 2 - C++
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.
Solution 3 - C++
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).
Solution 4 - C++
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.
Solution 5 - C++
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;
}
Solution 6 - C++
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";
}
Solution 7 - C++
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)
Solution 8 - C++
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;
}