Finding elements in a STL multimap

Posted in Programming by tux4life on June 24, 2009

Working more and more with STL is helping me learn some subtle nuances of STL.  One such nuance that I learnt today was how to search for an element in a multimap.

Trust me, this slightly more complicated than just using the find method.  Yes, the find method returns an iterator to the matching element.  But remember, this is a multimap.  So, what if there is more than one element with the same key.

We would ideally want to retrieve all the elements with the search key.  But what “find” method does not give is an iterator to the end position to the last instance of the matching key.  So, if you loop through till end of the map, you will go through the matched elements and also the elements that follow the matched elements till the last element in the map.

Fortunately, STL provides a method “equals_range” to get ONLY the items that match the key.  Usage of this function is illustrated below.

Code

#include <iostream>
#include <map>

typedef std::multimap<int, std::string> IntToStringMap;
typedef std::pair<int, std::string> IntStrPair;

int main()
{
IntToStringMap theMap;

//Add elements into the map by constructing pairs
theMap.insert( IntStrPair(1, “ONE”) );
theMap.insert( IntStrPair(3, “THREE”) );
theMap.insert( IntStrPair(2, “TWO”) );
theMap.insert( IntStrPair(2, “ANOTHER TWO”) );
theMap.insert( IntStrPair(2, “YET ANOTHER TWO!”) );

//Use the equal_range function to get a pair of iterators
//pair.first has the iterator pointing to the first key match
//pair.second has the iterator pointing to the last element with matching key
std::pair<IntToStringMap::iterator, IntToStringMap::iterator> itrPair =
theMap.equal_range(2);

IntToStringMap::const_iterator itr = itrPair.first;
if ( itr == theMap.end() ) {
//Search key not found
std::cout<<“Element Not Found”<<std::endl;
}
else {
//Search key found, perhaps more than once
//Loop through till the last match
for ( ; itr != itrPair.second; ++itr)
std::cout << itr->first << “–>” << itr->second << std::endl;
}

return 0;
}

Output

2–>TWO
2–>ANOTHER TWO
2–>YET ANOTHER TWO!

As explained in the comments, the equal_range function returns a pair of iterators.  The first pointing to the first instance of the match and the second pointing to the last instance of the match.  We can use these iterators to loop through our matches.

If there are better solutions for this, please let me know.

Tagged with: , , ,