binary_search with std::pair using a custom operator

Question

I am trying to do a binary_search including a vector of integer pairs and an integer as follows:

#include <vector>
#include <algorithm>
using namespace std;

typedef vector<pair<size_t,size_t> > int_pairs;

bool operator<(const size_t& l, const pair<size_t,size_t>& r)
    {return r.first < l;} // useful for binary search

int main(){
    int_pairs pairs_vec;
    pairs_vec.push_back(pair <size_t,size_t>(1,2));
    pairs_vec.push_back(pair <size_t,size_t>(2,2));
    size_t i(2);
    binary_search(pairs_vec.begin(),pairs_vec.end(),i);
}

The compiler tells me that the operator< is not defined:

erreur: no match for ‘operator<’ (operand types are ‘const long unsigned int’ and ‘std::pair<long unsigned int, long unsigned int>’)

Am I doing it the right way? I tried to change the definition of the operator in many different ways, but nothing seems to work.

Answer 1

The reason this doesn't work is that operator< isn't looked up from the point you call binary_search, but rather later from inside its body - and that's inside namespace std.

Since std::pair already defines relational operators in namespace std, these hide your overload in global scope and it's never found by name lookup.

The solution is to not use operator< at all. Create your own comparator class that doesn't clash with anything, overload its operator(), and use the other overload of binary_search that lets you specify custom comparator. Something like this:

#include <vector>
#include <algorithm>
using namespace std;

typedef pair<size_t, size_t> my_pair;
typedef vector<pair<size_t,size_t> > int_pairs;

struct Comp {
    // important: we need two overloads, because the comparison
    // needs to be done both ways to check for equality

    bool operator()(my_pair p, size_t s) const
    { return p.first < s; }
    bool operator()(size_t s, my_pair p) const
    { return s < p.first; }
};

int main(){
    int_pairs pairs_vec;
    pairs_vec.push_back(pair <size_t,size_t>(1,2));
    pairs_vec.push_back(pair <size_t,size_t>(2,2));
    size_t i(2);
    binary_search(pairs_vec.begin(),pairs_vec.end(),i, Comp());
}

Side notes:

Your attempt at operator< was wrong, because you switched the order of operands inside the function. The contract for comparators for strict weak ordering says that it must return true if first operand comes before the second (this goes for all comparison functions throughout the standard library).

bool operator<(const size_t& l, const pair<size_t,size_t>& r)
{
    return r.first < l; // Wrong!
}

And as said above in the comment, if the operands for the comparison are of different types, you'll need two overloads. To check for equality with <, you need two test:

(!(a < b) && (!b < a))