Operatore <e rigoroso ordine debole

Come definire l’ operator< on n-tuple (ad esempio sulla tupla 3) in modo che soddisfi un rigoroso concetto di ordine debole ? So che la libreria boost ha class di tuple con operator< definito correttamente operator< ma per qualche motivo non posso usarlo.

 if (a1 < b1) return true; if (b1 < a1) return false; // a1==b1: continue with element 2 if (a2 < b2) return true; if (b2 < a2) return false; // a2 == b2: continue with element 3 if (a3 < b3) return true; return false; // early out 

Questo ordina gli elementi di a1 essendo il più significativo e il meno significativo.

Questo può essere continuato all'infinito, potresti anche ad esempio applicarlo a un vettore di T, iterando su confronti di un [i]

 while (i 

Ovviamente, se il confronto è costoso, è ansible che si desideri memorizzare nella cache il risultato del confronto.


[modifica] rimosso codice errato

rigoroso ordine debole

Questo è un termine matematico per definire una relazione tra due oggetti.
La sua definizione è:

Due oggetti xey sono equivalenti se sia f (x, y) che f (y, x) sono falsi. Si noti che un object è sempre (dall’invarianza dell’invarianza) equivalente a se stesso.

In termini di C ++ ciò significa che se si hanno due oggetti di un determinato tipo, si dovrebbero restituire i seguenti valori rispetto all’operatore <.

 X a; X b; Condition: Test: Result a is equivalent to b: a < b false a is equivalent to bb < a false a is less than ba < b true a is less than bb < a false b is less than aa < b false b is less than ab < a true 

Il modo in cui definisci l'equivalente / meno dipende totalmente dal tipo di object.

Controlla la pagina SGI sull'argomento:
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

… una nuova risposta a una domanda molto vecchia, ma la risposta esistente manca la soluzione facile da C ++ 11 …

Soluzione C ++ 11

C ++ 11 in poi fornisce std::tuple , che puoi usare per memorizzare i tuoi dati. tuple s hanno un operator< corrispondenza operator< che inizialmente confronta l'elemento più a sinistra, quindi lavora lungo la tupla finché il risultato non è chiaro. Questo è adatto per fornire il severo ordinamento debole previsto per esempio std::set e std::map .

Se si hanno dati in altre variabili (es. Campi in una struct ), si può anche usare std::tie() per creare una tupla di riferimenti , che può essere quindi confrontata con un'altra tupla. Ciò semplifica la scrittura operator< per specifici campi dei dati membro in un tipo di class / struct definito dall'utente:

 struct My_Struct { int a_; double b_; std::string c_; }; bool operator<(const My_Struct& lhs, const My_Struct& rhs) { return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_); } 

Potresti semplicemente usare i vettori a tre elementi, che avranno già l’operatore <() opportunamente definito. Questo ha il vantaggio che si estende a N-elementi senza che tu debba fare nulla.

Il stream di base dovrebbe essere lungo le linee di: se gli elementi di Kth sono diversi, il ritorno che è più piccolo altro va all’elemento successivo . Il codice seguente presuppone che tu non abbia una tupla boost altrimenti useresti get(tuple) e non abbia il problema per cominciare.

 if (lhs.first != rhs.first) return lhs.first < rhs.first; if (lhs.second != rhs.second) return lhs.second< rhs.second; return lhs.third < rhs.third; 

Anche se non puoi usare la versione boost, dovresti essere in grado di scalzare il codice. Ho intaccato questo da std :: pair – una tupla di 3 sarà simile credo.

 return (_Left.first < _Right.first || !(_Right.first < _Left.first) && _Left.second < _Right.second); 

Modifica: come un paio di persone hanno sottolineato, se rubi codice dalla libreria standard da usare nel tuo codice, dovresti rinominare le cose che hanno caratteri di sottolineatura in primo piano in quanto questi nomi sono riservati.