C++ Searching in std::map or in std::multimap


Example

There are several ways to search a key in std::map or in std::multimap.

  • To get the iterator of the first occurrence of a key, the find() function can be used. It returns end() if the key does not exist.

      std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
      auto it = mmp.find(6);
      if(it!=mmp.end())
          std::cout << it->first << ", " << it->second << std::endl; //prints: 6, 5
      else
          std::cout << "Value does not exist!" << std::endl;
    
      it = mmp.find(66);
      if(it!=mmp.end())
          std::cout << it->first << ", " << it->second << std::endl; 
      else
          std::cout << "Value does not exist!" << std::endl; // This line would be executed.
    
  • Another way to find whether an entry exists in std::map or in std::multimap is using the count() function, which counts how many values are associated with a given key. Since std::map associates only one value with each key, its count() function can only return 0 (if the key is not present) or 1 (if it is). For std::multimap, count() can return values greater than 1 since there can be several values associated with the same key.

     std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
     if(mp.count(3) > 0) // 3 exists as a key in map
         std::cout << "The key exists!" << std::endl; // This line would be executed.
     else
         std::cout << "The key does not exist!" << std::endl;
    

    If you only care whether some element exists, find is strictly better: it documents your intent and, for multimaps, it can stop once the first matching element has been found.

  • In the case of std::multimap, there could be several elements having the same key. To get this range, the equal_range() function is used which returns std::pair having iterator lower bound (inclusive) and upper bound (exclusive) respectively. If the key does not exist, both iterators would point to end().

      auto eqr = mmp.equal_range(6);
      auto st = eqr.first, en = eqr.second;
      for(auto it = st; it != en; ++it){
          std::cout << it->first << ", " << it->second << std::endl; 
      }
          // prints: 6, 5
          //         6, 7