Operatore https://stackoverflow.com/questions/979759

Question

Come definire operator< su n-pla (ad esempio il 3-tupla) in modo da soddisfare rigoroso ordinamento debole concetto? So che libreria Boost ha classe tupla con operator< correttamente definito, ma per qualche motivo non posso usarlo.

Answer 1

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 essere più siginificant e a3 meno significativo.

Questo può essere continuato all'infinito, si potrebbe anche es applicarlo a un vettore di T, l'iterazione di confronto di un [i]

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

Naturalmente, se il confronto è costoso, si potrebbe desiderare di memorizzare nella cache il risultato del confronto.

---

[modifica] codice errato rimosso

---

[modifica] se più di un semplice operator< è disponibile, tendo a usare il modello

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

Answer 2

rigoroso ordinamento 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) e f (y, x) sono false. Si noti che un oggetto è sempre (dal invariante irreflexivity) equivalente a se stesso.

In termini di C ++ questo significa che se si dispone di due oggetti di un certo tipo, è necessario restituire i seguenti valori rispetto l'operatore <.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

Come si definisce equivalente / meno è totalmente dipendente dal tipo di oggetto.

definizione formale:
rigoroso ordinamento debole

Informatica:
Strict Debole ordinazione

Come si riferisce agli operatori:
comparatore

Answer 3

... una nuova risposta ad una domanda molto vecchio, ma la risposta esistente perdere la soluzione facile da C ++ 11 ...

C ++ 11 soluzione

C ++ 11 fornisce poi std::tuple<T...> , che può essere utilizzato per memorizzare i dati. tuples hanno una corrispondenza operator< che mette a confronto inizialmente più a sinistra elemento, quindi funziona lungo la tupla fino del chiaro risultato. Questo è adatto per fornire il rigoroso ordinamento debole prevista entro esempio std::set e std::map .

Se si dispone di dati in alcune altre variabili (ad esempio i campi in un struct), si può anche utilizzare std::tie() per crea una tupla di riferimenti , che possono poi essere confrontato ad un altro tale tupla. Che lo rende facile da scrivere operator< per i campi per i membri di dati specifici in un tipo 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_);
}

Answer 4

Si potrebbe semplicemente utilizzare vettori a tre elementi, che hanno già operator <() opportunamente definito. Questo ha il vantaggio che si estende a N-elementi senza dover fare nulla.

Answer 5

Il flusso di base deve essere lungo le linee di: se gli elementi KTH sono differenti, ritorno che è più piccolo altrimenti va al successivo elemento . Il codice seguente presuppone che non ha una tupla spinta altrimenti userebbe get<N>(tuple) e non hanno 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;

Answer 6

Anche se non è possibile utilizzare la versione spinta, si dovrebbe essere in grado di nick il codice. Ho fregato questo da std :: coppia - una tupla 3 sarà simile Credo

.

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

Modifica:. Come un paio di persone hanno fatto notare, se rubi il codice dalla libreria standard da utilizzare nel codice, è necessario rinominare le cose che hanno sottolineature sul fronte come questi nomi sono riservati