binary_search mit std :: Paar mit einem benutzerdefinierten Operator

Question

Ich versuche, eine binary_search mit einem Vektor von ganzzahligen Paaren und einer ganzen Zahl zu tun, wie folgt:

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

Der Compiler sagt mir, dass die operator< nicht definiert ist:

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

Mache ich es richtig? Ich habe versucht, die Definition des Operators auf viele verschiedene Arten zu ändern, aber nichts scheint zu funktionieren.

Answer 1

Der Grund dies nicht funktioniert, ist, dass operator< nicht von dem Punkt, den Sie binary_search nennen nachgeschlagen, sondern später aus dem Inneren seines Körpers - und das ist innerhalb Namespace std.

Seit std::pair definiert bereits relational operators in Namespace std, verbergen Sie Ihre Überladung im globalen Bereich und es wird nie durch Namenssuche gefunden.

Die Lösung ist operator< überhaupt nicht zu verwenden. Erstellen Sie Ihre eigene Vergleichsklasse, die nicht mit irgendetwas kollidiert, überladen Sie operator(), und verwenden Sie die andere Überladung von binary_search, mit der Sie einen benutzerdefinierten Vergleicher angeben können. Etwas wie folgt aus:

#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 Hinweise:

Ihr Versuch operator< war falsch, weil Sie die Reihenfolge der Operanden innerhalb der Funktion geschaltet. Der Vertrag für Komparatoren für strikt schwache Reihenfolge besagt, dass es True zurückgeben muss, wenn erster Operand vor dem zweiten kommt (dies gilt für alle Vergleichsfunktionen in der Standardbibliothek).

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

Und wie oben im Kommentar gesagt, wenn die Operanden für den Vergleich unterschiedlicher Typen sind, benötigen Sie zwei Überladungen. Um zu überprüfen, für die Gleichstellung mit <, müssen Sie zwei Test:

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