72

Is there a way in C++ to search for the mapped value (instead of the key) of a map, and then return the key? Usually, I do someMap.find(someKey)->second to get the value, but here I want to do the opposite and obtain the key (the values and keys are all unique).

CharlesB
  • 86,532
  • 28
  • 194
  • 218
wrongusername
  • 18,564
  • 40
  • 130
  • 214
  • 1
    @Fred: the linked question never received an answer, only an alternative (which seemed to satisfy that particular need, but that's not the point). – Tony Delroy Nov 24 '10 at 05:27
  • Possible duplicate of [Checking value exist in a std::map - C++](http://stackoverflow.com/questions/535317/checking-value-exist-in-a-stdmap-c) – CharlesB Nov 30 '16 at 13:28

6 Answers6

77

Because of how a map is designed, you'll need to do the equivalent of a search on unordered data.

for (auto it = someMap.begin(); it != someMap.end(); ++it)
    if (it->second == someValue)
        return it->first;
Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
  • It's the same thing. He's just dereferencing the pointer instead of calling ->. It probably compiles to exactly the same code. – Falmarri Nov 24 '10 at 05:25
  • That may be exactly what's needed, but just a comment: you return the first key, which may not be the only one mapping to `someValue`. Even if it's then erased or altered so it won't match on the next search, it's not good to unnecessarily restart iteration from begin(), but that initial iterator value could be passed in as a function argument. Hope the poster can sought out such details as they arise. – Tony Delroy Nov 24 '10 at 05:26
  • @Falmarri I know it does the same thing, I'm just wondering if there's a specific reason for doing it that way. It seems to me the code doesn't read as nice as `it (arrow) key` :) – wrongusername Nov 24 '10 at 05:27
  • @tony what's the harm in restarting from `begin()`? – wrongusername Nov 24 '10 at 05:28
  • 1
    @wrong: I'm not sure if it's just syntax flavor or if it does anything different. Sounds like a good question to me... dibs =P – Falmarri Nov 24 '10 at 05:35
  • It's not the same, is it? `*it.key` would be equivalent to `*(it.key)`, while `it->key` would be the same as `(*it).key`. Right? – Fred Larson Nov 24 '10 at 05:36
  • 2
    I don't think there's a `key` member of either the iterator or the `pair` it points to. I think it should be `it->first` (or `(*it).first`). – Fred Larson Nov 24 '10 at 05:40
  • Oh, I was looking at the (*it).second call, instead of say it->second – Falmarri Nov 24 '10 at 05:42
  • @wrongusername: if you're trying to find all the places "value" appears in the map, then restarting from begin() won't work at all unless you remove the matches as they're found. Further, instead of just searching each element once, you'll revisit the first N times, the second (N-1) times, third (N-2) etc. making the whole process of O(N^2) efficiency. It may not matter if there aren't many things in the map, but it never helps and could easily become the dominant performance issue for a program in certain situations. – Tony Delroy Nov 24 '10 at 06:43
  • @tony thanks for the explanation! for this there's only unique values though – wrongusername Nov 24 '10 at 06:53
  • @wrongusername: I'm not really sure why I chose `(*it).first` instead of `it->first`. I've switched it to the arrow operator because it is cleaner. – Bill Lynch Nov 24 '10 at 15:39
32

Using lambdas (C++11 and newer)

//A MAP OBEJCT
std::map<int, int> mapObject;

//INSERT VALUES
mapObject.insert(make_pair(1, 10));
mapObject.insert(make_pair(2, 20));
mapObject.insert(make_pair(3, 30));
mapObject.insert(make_pair(4, 40));

//FIND KEY FOR BELOW VALUE
int val = 20;

auto result = std::find_if(
          mapObject.begin(),
          mapObject.end(),
          [val](const auto& mo) {return mo.second == val; });

//RETURN VARIABLE IF FOUND
if(result != mapObject.end())
    int foundkey = result->first;
Rajesh Negi
  • 103
  • 1
  • 8
Pavan Chandaka
  • 11,671
  • 5
  • 26
  • 34
19

Structured bindings (available since C++17) enable a convenient way of writing the same loop as depicted in Bill Lynch's answer, i.e.

for (const auto& [key, value] : someMap)
    if (value == someValue)
        return key;
lubgr
  • 37,368
  • 3
  • 66
  • 117
17

If you are doing this kind of search frequently in larger maps, then it may be interesting to look at a Bimap, that will index both keys and values. There is an implementation of a Bimap available in Boost: https://www.boost.org/doc/libs/1_77_0/libs/bimap/doc/html/index.html

emmenlau
  • 958
  • 12
  • 20
Paul
  • 2,218
  • 1
  • 15
  • 18
6

We can create a reverseMap which maps values to keys.

Like,

map<key, value>::iterator it;
map<value, key> reverseMap;

for(it = originalMap.begin(); it != originalMap.end(); it++)
     reverseMap[it->second] = it->first;

This also is basically like a linear search but will be useful if you have a number of queries.

Karan Saxena
  • 69
  • 1
  • 1
1
struct test_type
{
    CString str;
    int n;
};


bool Pred( std::pair< int, test_type > tt )
{
    if( tt.second.n == 10 )
        return true;

    return false;
}


std::map< int, test_type > temp_map;

for( int i = 0; i < 25; i++ )

{
    test_type tt;
    tt.str.Format( _T( "no : %d" ), i );
    tt.n = i;

    temp_map[ i ] = tt;
}

auto iter = std::find_if( temp_map.begin(), temp_map.end(), Pred );
이원용
  • 19
  • 2