Bevorzugte Implementierung von '<' für multi-variable Strukturen

Question

Dies mag zunächst abstrakt oder philosophisch erscheinen, aber ich bin wirklich interessiert zu sehen, ob jemand ein überzeugendes Argument für eine Implementierung gegenüber der anderen hat.

Da operator< für std::pair<T1, T2>, was die bessere Umsetzung wäre:

return x.first < y.first || 
     x.first == y.first && x.second < y.second; 

oder:

return x.first < y.first || 
     !(y.first < x.first) && x.second < y.second; 

Mein Verständnis ist, dass die beiden Implementierungen zu vergleichbaren Ergebnissen führen. Wird Letzteres bevorzugt, weil es ausschließlich in Bezug auf operator< definiert ist? Oder ist es legitim anzunehmen, dass ein Typ, der weniger als vergleichbar ist, auch gleichwertig sein sollte? Sieht jemand anderes einen anderen Punkt, der Sie zwischen dem einen oder anderen hin und her schwingen lässt?

Natürlich sollte jede Antwort sowohl generisch als auch erweiterbar sein. Also welchen würdest du benutzen und warum? Gibt es eine andere Implementierung, die sogar besser ist als die oben genannten?

Answer 1

Es ist nicht legitim, dass jeder Typen für zu übernehmen, wenn es weniger als vergleichbar ist, ist es auch Gleichheit vergleichbar ist, da man operator< Überlastung kann aber nicht operator== überlasten.

Wenn Sie also erwarten, dass Sie mit benutzerdefinierten Typen umgehen müssen, ist der zweite Ansatz vorzuziehen. Sie sollten jedoch einige Klammern fügen Sie die Reihenfolge der Vorgänge zu klären:

return x.first < y.first || 
     (!(y.first < x.first) && x.second < y.second); 

Answer 2

Die Implementierung sind nicht gleichwertig, wenn Betreiber < eine schwache Ordnung darstellt. Stellen Sie sich zum Beispiel vor, dass Objekte von T1 Knoten in einem Digraphen sind und T1a < T1d bedeutet "T1a ist ein Vorgänger von T1b in der Grafik" (dies ist keine so ungewöhnliche Notation).

Dann: !(T1b < T1a) würde bedeuten "t1b nicht ein Vorfahre von T1A" so entweder:

1. T1a ist ein Vorfahre von T1b (durch den ersten Test ausgeschlossen)
2. T1a ist der gleiche Knoten wie T1b
3. T1a und T1b sind nicht vergleichbar (dh sie Geschwister sind)

Dieser dritte Fall ist wirklich wichtig. In diesem Fall möchten Sie wahrscheinlich, dass der Operator < für das Paar false zurückgibt, aber möglicherweise nicht.

(A schwache Ordnung auf einer Reihe von Elementen bedeutet, dass a <= b und b <= a beide falsch sein können.)

Ich persönlich bin nicht der Betreiber Überlastung gern, vor allem, wenn sie mit Generika verwendet. Programmierer neigen dazu, nette "arithmetische" Eigenschaften anzunehmen, die nicht immer gelten.

Answer 3

Ich würde die zweite verwenden, weil das ist, was der Standard angibt!

Die beiden Definitionen sind, wie andere bereits erwähnt haben, äquivalent, solange < eine Gesamtordnung für beide Typen definiert und == mit < übereinstimmt.Aber wenn beides nicht wahr ist, ist der Unterschied beobachtbar, und wenn Sie die erste Definition verwenden, würden Sie sich nicht anpassen.

EDIT: Die Standardauflösung ist besser als Ihre erste Definition in einem gewissen Sinne: wenn < eine strenge schwache Ordnung sowohl T1 und T2 definiert, dann ist die Standard-Definition gibt eine strenge schwache Ordnung auf pair<T1, T2>. Ihre erste Definition nicht, und das kann echte Probleme verursachen. Nehmen wir zum Beispiel an, dass wir x und y so haben, dass weder x < y noch y < x. Betrachten Sie dann das Array der Paare a[3] = {P(x, 2), P(y, 1), P(x, 1)}. Natürlich sollten wir sagen, dieses Array ist nicht aufsteigend sortiert, da a[2] < a[0]. Aber wenn wir Ihre erste Definition verwenden, würde std::is_sorted daraus schließen, dass das Array sortiert ist, weil keine zwei aufeinander folgenden Elemente vergleichbar sind. Die Tatsache, dass die erste Definition keine streng schwache Ordnung ist, bricht den Algorithmus. Unter der Standarddefinition P(y, 1) < P(x, 2) erkennt der Algorithmus, dass das Array nicht wie gewünscht sortiert ist.

(Diese Antwort zuvor eine völlig falsche Analyse dieser Situation hatte - sorry)