Bevorzugte Implementierung von '<' für multivariable Strukturen

Question

Auf den ersten Blick mag dies zu abstrakt oder philosophisch erscheinen, aber ich bin wirklich daran interessiert zu sehen, ob jemand ein überzeugendes Argument für die eine oder die andere Implementierung hat.

Gegeben operator< para 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;

Meines Erachtens liefern die beiden Implementierungen gleichwertige Ergebnisse. Ist die letztere vorzuziehen, weil sie ausschließlich in Form von operator< ? Oder ist es legitim, davon auszugehen, dass ein Typ, der weniger als vergleichbar ist, auch gleich vergleichbar sein sollte? Sieht noch jemand einen anderen Punkt, der Sie zu der einen oder anderen Entscheidung veranlasst?

Natürlich sollte jede Antwort sowohl generisch als auch erweiterbar sein. Welche Lösung würden Sie also verwenden und warum? Gibt es eine andere Implementierung, die noch besser ist als die oben genannte?

Answer 1

Es ist nicht legitim, anzunehmen, dass für jede Typ, wenn er weniger-als-vergleichbar ist, ist er auch gleich-vergleichbar, denn man kann überladen operator< aber nicht überlasten operator== .

Wenn Sie also davon ausgehen, dass Sie mit benutzerdefinierten Typen umgehen müssen, ist der zweite Ansatz vorzuziehen. Sie sollten jedoch einige Klammern hinzufügen, um die Reihenfolge der Operationen zu verdeutlichen:

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

Answer 2

Die Implementierung ist nicht gleichwertig, wenn operator< eine schwache Ordnung darstellt. Stellen Sie sich zum Beispiel vor, dass die Objekte von T1 Knoten in einem Digraphen sind und T1a < T1d bedeutet "T1a ist ein Vorfahre von T1b im Graphen" (diese Schreibweise ist gar nicht so ungewöhnlich).

Dann: !(T1b < T1a) würde bedeuten "t1b ist kein Vorfahre von t1a", also entweder:

1. t1a ist ein Vorfahre von t1b (ausgeschlossen durch den ersten Test)
2. t1a ist derselbe Knoten wie t1b
3. t1a und t1b sind nicht vergleichbar (d. h. sie sind Geschwister)

Dieser dritte Fall ist wirklich wichtig. In diesem Fall wollen Sie wahrscheinlich, dass operator< für das Paar false zurückgibt, aber vielleicht auch nicht.

(Eine schwache Ordnung für eine Menge von Elementen bedeutet, dass a <= b y b <= a können beide falsch sein.)

Ich persönlich bin kein Freund von Operator-Überladungen, insbesondere wenn sie mit Generika verwendet werden. Programmierer neigen dazu, schöne "arithmetische" Eigenschaften anzunehmen, die nicht immer zutreffen.

Answer 3

Ich würde die zweite Variante wählen, denn das ist es, was die Norm vorschreibt!

Die beiden Definitionen sind, wie bereits erwähnt, gleichwertig, solange < definiert eine Gesamtordnung für beide Typen und == ist vereinbar mit < . Aber wenn eine der beiden Definitionen nicht zutrifft, ist der Unterschied erkennbar, und wenn Sie die erste Definition verwenden würden, wären Sie nicht konform.

EDITAR: Die Standarddefinition ist in einem Punkt besser als Ihre erste Definition: wenn < eine strenge schwache Ordnung sowohl für T1 als auch für T2 definiert, so ergibt die Standarddefinition eine strenge schwache Ordnung für pair<T1, T2> . In Ihrer ersten Definition ist das nicht der Fall, und das kann zu echten Problemen führen. Nehmen wir zum Beispiel an, wir haben x und y so, dass weder x < y noch y < x . Betrachten Sie dann die Reihe von Paaren a[3] = {P(x, 2), P(y, 1), P(x, 1)} . Man sollte eindeutig sagen, dass dieses Array pas in aufsteigender Reihenfolge sortiert, weil a[2] < a[0] . Aber wenn wir Ihre erste Definition verwenden, std::is_sorted würde zu dem Schluss kommen, dass das Array ist sortiert, denn keine zwei fortlaufend Elemente vergleichbar sind. Die Tatsache, dass es sich bei der ersten Definition nicht um eine strenge schwache Ordnung handelt, macht den Algorithmus zunichte. Nach der Standard-Definition, P(y, 1) < P(x, 2) und so erkennt der Algorithmus, dass die Anordnung nicht wie gewünscht sortiert ist.

(Diese Antwort enthielt zuvor eine völlig falsche Analyse dieser Situation - Entschuldigung!)