Reverse map lookup

Question

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.

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.

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

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.

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;
    }