Geek Answers Handbook

On a C ++ map, is there a way to search for a key with a given value?

In C ++, is std::mapthere a way to search for a key based on the displayed value? Example:

I have this card:

map<int,string> myMap;
myMap[0] = "foo";

Is there a way to find the appropriate intone given the meaning "foo"?

cout << myMap.some_function("foo") <<endl;

Output: 0
+4
source share
5 answers

std::map does not provide a (quick) way to search for a key of a given value.

, , " " "". Boost ​​ . , "" ( std::map ). Boost .

Boost, , , :

std::map<int, string> myMapForward;
std::map<string, int> myMapBackward;    // maybe even std::set

// insertion becomes:
myMapForward.insert(std::make_pair(0, "foo"));
myMapBackward.insert(std::make_pair("foo", 0));

// forward lookup becomes:
myMapForwar[0];

// backward lookup becomes:
myMapBackward["foo"];

, , , . , . , .

, std::map , , .

+5

, .

- , , . , , O (n).

, for(), std::find_if(). find_if(), . ++ 11 lambda:

typedef std::map <unsigned, Student> MyMap;
MyMap myMap; 

// ...

const string targetName = "Jones";
find_if (myMap.begin(), myMap.end(), [&targetName] (const MyMap::value_type& test)
{
  if (test.second.mName == targetName)
    return true;
});

++ 03, :

struct MatchName
: public std::unary_function <bool, MyMap::value_type>
{
  MatchName (const std::string& target) : mTarget (target) {}
  bool operator() (const MyMap::value_type& test) const
  {
    if (test.second.mName == mTarget)
      return true;
    return false;
  }
private:
  const std::string mTarget;
};


// ...

find_if (myMap.begin(), myMap.end(), MatchName (target));

- . , , , - , , - - .

, Student, , - , . , , (, multimap), - . , Student.

. , ( ) . , , , -, , . , , , .

+2

, , - . , , , , . !

0

, , O(n) time. , O(n) space.

:

std::map<int, string> fmap;

for (std::map<int,string>::iterator it=fmap.begin(); it!=fmap.end(); ++it)
    if (strcmp(it->second,"foo"))
        break;

:

std::map<int, string> fmap;
std::map<string, int> bmap;

fmap.insert(std::make_pair(0, "foo"));
bmap.insert(std::make_pair("foo", 0));

fmap[0]; // original map lookup

bmap["foo"]; //reverse map lookup
0

No, you cannot do this. You just need to iterate over the map and match each value with the element you want to match, and return the corresponding key, and this will cost you complex time complexity equal to O (n).

0
source

More articles:


All Articles