C++ Tip: lower_bound and functors

Here's an interesting thing I learned recently via necessity. Let's assume you have a vector of string/int combinations.

vector<pair<string, int> > myvec;

Now, lets assume we add data to the vector, in sorted order (based on the string).

myvec.push_back( make_pair( string("A"), 0 ) );
myvec.push_back( make_pair( string("B"), 1 ) );
myvec.push_back( make_pair( string("C"), 2 ) );
myvec.push_back( make_pair( string("D"), 3 ) );

Finally, we want to search for a string key in the sorted vector using lower_bound.
We can't do the following:

lower_bound( myvec.begin(), myvec.end(), 
             string( "C" ) );

It will complain that there is not an operator<(std::pair<std::string,int>, std::string). Well, that is annoying, but we can write one. However, it is usually better to not clutter the global namespace with such functions and instead we choose to create a comparator function.

bool pair_str_less(const pair<
                     string,int>& lhs, 
                   const string& rhs)
{
   return lhs.first < rhs;
}

Now we pass in the comparator function

lower_bound( myvec.begin(), myvec.end(), 
             string("C"), pair_str_less );

Ouch! Now it complains that there is no pair_str_less( std::string, std::pair<std::string, int> ). It needs both permutations of function arguments! Unfortunately, we can only pass in one comparator! Perhaps it is not meant to be? Maybe we should just write our own version of lower bound? Or perhaps we should create a dummy std::pair from the string? Or, perhaps we can use functors!

struct pair_str_less
{
   bool operator()( const pair< 
                      string, int>& lhs, 
                    const string& rhs ) const 
   { /*...*/ }
   bool operator()( const string& rhs, 
                    const pair< 
                      string, int >& rhs ) const 
   { /*...*/ }
};

Now, we can use the pair_str_less function like

lower_bound( myvec.begin(), myvec.end(), 
             string("C"), pair_str_less() );

and the right version of operator() is chosen each way. Yeah!