binary_search con std :: coppia utilizzando un operatore personalizzato

Question

Sto cercando di fare un binary_search tra cui un vettore di coppie di interi e un intero come segue:

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

Il compilatore mi dice che il operator< non è definito:

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

Sto facendo nel modo giusto? Ho provato a cambiare la definizione dell'operatore in molti modi diversi, ma nulla sembra funzionare.

Answer 1

Il motivo per cui questo non funziona è che operator< non viene rilevato dal punto che si chiama binary_search, ma piuttosto più tardi dal suo corpo - e questo è all'interno dello spazio dei nomi std.

Poiché std::pair definisce già relational operators nello spazio dei nomi std, questi nascondono il sovraccarico nell'ambito globale e non vengono mai trovati per la ricerca del nome.

La soluzione è di non utilizzare operator< affatto. Crea la tua classe di comparatori che non si scontri con nulla, sovraccarichi il suo operator() e utilizzi l'altro sovraccarico di binary_search che ti consente di specificare un comparatore personalizzato. Qualcosa di simile a questo:

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

note collaterali:

Il tuo tentativo di operator< era sbagliato, perché si è cambiato l'ordine degli operandi all'interno della funzione. Il contratto per i comparatori per gli ordini deboli rigorosi afferma che deve restituire true se il primo operando arriva prima del secondo (questo vale per tutte le funzioni di confronto in tutta la libreria standard).

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

E come detto sopra nel commento, se gli operandi per il confronto sono di tipi diversi, occorrono due sovraccarichi. Per verificare la presenza di uguaglianza con <, avete bisogno di due test di:

uso

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