Sortieren nur mit dem weniger als als Bediener im Vergleich zu einer Tribale-Vergleichenfunktion

Question

In C ++/STL erfolgt die Sortierung nur mit dem weniger als weniger als Operator. Ich habe keine Ahnung, wie die Sortieralgorithmen tatsächlich implementiert werden. Ich gehe davon aus, dass die anderen Operationen impliziten erstellt werden:

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

Ist dies im Vergleich zur Verwendung eines TRIVALUE* -Vergleichungsfunktion, wie zum Beispiel Java, so gut für die Leistung oder warum wurde diese Entwurfsentscheidung getroffen?

Ich gehe davon aus, dass jede Tribale -Vergleichsfunktion diese Vergleiche in sich selbst implementieren muss, was zu derselben Leistung führt.

** Mit TRIVALUE -VERGRAFFUNGSFUNKTION Ich meine eine Vergleichenfunktion, die -1, 0 und 1 für weniger als, gleich und höher und höher als*

Aktualisieren:Es scheint ein Raumschiff <=> Betreiber kommen in C ++ 20 operator<.

Answer 1

In gewissem Sinne sind die anderen beiden implizit, aber genauer gesagt zu sagen brauchen Ein dreiwertiger Vergleicher und C ++ werden in einer Weise implementiert, bei der keines verwendet wird, um das Verhalten des Vergleichs zu minimieren.

Es wäre falsch, dass std :: so etwas definiert und ausschließlich verwendet wird:

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

... weil Sie einen ineffizienten Algorithmus in Bezug auf die Anzahl der Anrufe zu haben würden lessthan. Wenn Ihr Algorithmus mit dem Unterschied zwischen einer 1 -Rückgabe und einer 0 -Rückgabe nichts Nützliches tut, haben Sie einen Vergleich verloren.

C ++ bezieht sich auf "strenge schwache Ordnung". Wenn < ist eine strenge schwache Ordnung und !(a < b) && !(b < a), es tut es nicht Notwendig Folge dem a == b. Sie sind nur "am selben Ort" in der Bestellung, und !(a < b) && !(b < a) ist eine Äquivalenzbeziehung. Also der Komparator von verpflichtet von sort Aufträge Äquivalenzklassen Von Objekten liefert es keine Gesamtreihenfolge.

Der einzige Unterschied, den es macht, ist das, was Sie sagen, wenn Sie sagen !(a < b). Für eine strenge Gesamtbestellung würden Sie sich abgeben b <= a, lesen Sie "weniger als oder gleich". Für eine strenge schwache Reihenfolge können Sie nicht definieren b <= a meinen b < a || b == a Und haben Sie das wahr. C ++ ist dazu pedantisch, und da es den Bediener überlastet, muss das Überladen von Bediener so ziemlich sein, da Menschen den Operatoren überladen, um den Jargon zu überladen, um den Benutzern von ihrem Code zu informieren, was sie in Bezug auf die Beziehung zwischen den Betreibern erwarten können. Java spricht über den Komparator und den HashCode, der mit Gleichen übereinstimmt, was alles ist, was Sie brauchen. C ++ muss sich mit <,>, ==, <=,> =, der Post-Kondition der Zuordnung usw. befassen.

C ++ verfolgt dies in der API einen ziemlich reinen mathematischen Ansatz, sodass alles in Bezug auf die einzelne binäre Beziehung definiert ist. Java ist in gewisser Hinsicht freundlicher und bevorzugt Drei-Wege-Vergleiche, bei denen die Definition der Grundeinheit (der Vergleich) etwas komplexer ist, aber die von ihr führende Logik ist einfacher. Dies bedeutet auch, dass der Sortieralgorithmus pro Vergleich mehr Informationen erhält, was gelegentlich nützlich ist. In einem Beispiel sehen Sie die QuickSort -Optimierung "Dutch Flag", was ein Vorteil ist, wenn es viele "an derselben Stelle" -Duplikate in den Daten gibt.

In diesem Fall ist ein Drei-Werte-Vergleiche ein Geschwindigkeitsgewinn. C ++ verwendet jedoch eine konsistente Definition eines Komparators für Sortier und auch für set und map, lower_bound und so weiter, die kaum von einem Dreierwertvergleich profitieren (vielleicht einen Vergleich sparen, vielleicht auch nicht). Ich würde vermuten, dass sie beschlossen haben, ihre nette, allgemeine Schnittstelle im Interesse spezifischer oder begrenzter potenzieller Effizienzgewinne nicht zu komplizieren.

Answer 2

Ich vermute in C ++, es wurde nur durchgeführt, um die Code -Duplikation zu reduzieren: Sobald Sie ein Vergleich OP auf einer Klasse/einem Typ definieren, können Sie diese Objekte nicht nur vergleichen, indem Sie einfach ein <b schreiben, sondern auch die Fähigkeit erhalten, Mengen von Sortieren von Sortieren zu sortieren Solche Objekte.

Was das Sortieren betrifft, brauchen wir nur weniger als Bediener. Warum sollten Sie zusätzliche Dinge einführen? :)

Answer 3

Wenn Sie sich auf std :: sort () beziehen, verwendet es nur weniger () Bediener, da er nicht die relative Reihenfolge des äquivalenten Elements bewahren muss, sodass er nur weniger () Operator und implizit Greater () Operator benötigt.

Während stable_sort es bewahren wird, aber es ist langsamer. Es benötigt weniger () Operator und bidirektional