Ordinamento solo utilizzando l'operatore inferiore a quello di una funzione di confronto Trivalue

Question

Nell'ordinamento C ++/STL viene eseguito utilizzando solo l'operatore tutt'altro che. Tuttavia, non ho idea di come siano effettivamente implementati gli algoritmi di smistamento, presumo che le altre operazioni siano create implicita:

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

Rispetto all'utilizzo di una funzione Trivalue* Confronta, come ad esempio Java, è buono per le prestazioni o perché questa decisione di progettazione è stata presa?

La mia ipotesi è che qualsiasi funzione di confronto Trivalue debba ancora implementare questi confronti in sé, con conseguenti prestazioni.

** Per funzione di confronto TrivaLUE, intendo una funzione di confronto che restituisce -1, 0 e 1 a meno di, uguale e superiore a*

Aggiornare:Sembra un'astronave <=> L'operatore sta arrivando in C ++ 20, quindi ovviamente il comitato pensava che ci fossero aspetti negativi dell'uso solo operator<.

Answer 1

In un certo senso gli altri due sono impliciti, ma più accurati sarebbe dire che un tipo di confronto non è effettivamente bisogno Un comparatore a tre valori e tipi di C ++ sono implementati in un modo che non ne usa uno per ridurre al minimo il comportamento richiesto dal comparatore.

Sarebbe sbagliato per Std :: Ordine definire e usare esclusivamente qualcosa del genere:

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

... perché finiresti con un algoritmo inefficiente in termini di numero di chiamate a lessthan. Se il tuo algoritmo non fa nulla di utile con la differenza tra un ritorno 1 e un ritorno 0, allora hai sprecato un confronto.

C ++ si riferisce a "rigorosi ordini deboli". Se < è un rigoroso ordinamento debole e !(a < b) && !(b < a), no necessariamente Seguilo a == b. Sono solo "nello stesso posto" nell'ordinamento e !(a < b) && !(b < a) è una relazione di equivalenza. Quindi il comparatore richiesto da sort ordini Classi di equivalenza di oggetti, non fornisce un ordine totale.

L'unica differenza che fa è quello che dici quando !(a < b). Per un ordine totale rigoroso, dedurresti b <= a, leggi "meno o uguale a". Per un rigoroso ordine debole, non puoi definire b <= a dire b < a || b == a e avere questo essere vero. C ++ è pedante su questo, e poiché consente all'operatore di sovraccaricare praticamente, dal momento che le persone che sovraccaricano gli operatori hanno bisogno del gergo per dire agli utenti del loro codice cosa possono aspettarsi in termini di come si collegano gli operatori. Java parla del comparatore e dell'hashcode coerente con gli eguali, che è tutto ciò che serve. C ++ deve affrontare <,>, ==, <=,> =, la post-condizione dell'assegnazione e così via.

C ++ adotta un approccio matematico piuttosto puro a questo nell'API, quindi tutto è definito in termini di una singola relazione binaria. Java è più amichevole per alcuni aspetti e preferisce confronti a tre vie in cui la definizione dell'unità fondamentale (il confronto) è un po 'più complessa, ma la logica che porta da essa è più semplice. Significa anche che l'algoritmo di ordinamento ottiene maggiori informazioni per confronto, che occasionalmente è utile. Ad esempio, consulta l'ottimizzazione QuickSort "Flag olandese", che è un vantaggio quando ci sono molti duplicati "nello stesso posto" nei dati.

In tal caso, un comparatore a tre valori è un guadagno di velocità. Ma C ++ usa una definizione coerente di comparatore per la sorto e anche per set e map, lower_bound E così via, che a malapena beneficia di un comparatore a tre valore (forse salva un confronto, forse no). Immagino che abbiano deciso di non complicare la loro bella interfaccia generale nell'interesse di guadagni di efficienza potenziale specifici o limitati.

Answer 2

La mia ipotesi in C ++ è stata fatta solo per ridurre la duplicazione del codice: una volta definita un confronto op su una classe/tipo, non sei solo in grado di confrontare quegli oggetti semplicemente scrivendo un <b, ma acquisisci anche la capacità di ordinare le serie di tali oggetti.

Per quanto riguarda l'ordinamento, abbiamo solo bisogno di un operatore tutt'altro che per introdurre cose aggiuntive? :)

Answer 3

Se ti riferisci a std :: sort (), è solo un operatore di meno () perché non è necessario preservare l'ordinamento relativo di elementi equivalenti, quindi avrà bisogno di solo meno () operatore e implicitamente più grande () operatore.

Mentre Std :: stable_sort lo preserverà, ma è più lento. Ha bisogno di meno () operatore e iteratore bidirezionale in cambio dell'operatore uguale () per costruire la funzione di confronto "trivalue"