7

次のように、整数ペアのベクトルと整数を含む binary_search を実行しようとしています。

#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);
}

コンパイラは、operator<が定義されていないことを教えてくれます。

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

私はそれを正しい方法でやっていますか？さまざまな方法で演算子の定義を変更しようとしましたが、何も機能していないようです。

4

1 に答える 1

9

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))
于 2013-08-23T15:59:41.817 に答える