Reverse map lookup

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