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.

Advertisements
Tagged with: , , ,

Sorting using STL Algorithms

Posted in Programming by tux4life on June 23, 2009

After a long hibernation, I’m back with a post on how to use STL Algorithms to sort (virtually anything).

The following code snippet shows how to sort a vector of integers in ascending and descending order.  The same idea can be used to sort a vector, set etc.

Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

typedef std::vector<int> IntVector;
void print(const IntVector &);

int main()
{
IntVector intVector;
intVector.push_back(10);
intVector.push_back(13);
intVector.push_back(4);
intVector.push_back(11);
intVector.push_back(2);

print(intVector);

//Sort in ascending order
sort(intVector.begin(), intVector.end());
print(intVector);

//Sort in descending order
sort(intVector.begin(), intVector.end(), std::greater<int>());
print(intVector);
}

void print(const IntVector &vec)
{
IntVector::const_iterator itr = vec.begin();
for( ; itr != vec.end(); ++itr )
std::cout << *itr << ” “;

std::cout << std::endl;
}

Output

Original Vector: 10 13 4 11 2
Sorted Ascending:  2 4 10 11 13
Sorted Descending: 13 11 10 4 2

After inserting few elements into the vector, we can use the “sort” algorithm provided by STL to sort the vector.  The first two arguments are iterations to the starting position and ending position of the vector.

We can also specify the comparison function that is to be used for comparison while sorting.  By default the std::less function object is used.  So the first sort call sorts the vector in ascending order.

To the second sort call, the std::greater function object is used.  So, the vector is sorted in descending order.

There are various function objects available in STL and they can be used as we need them.  You can find a comprehensive list of function objects here.

PS: WordPress is not letting me format the code snippet.  I will find a workaround soon.

Tagged with: , , ,