weniger oder less_equal

Question

setzen wir die Verwendung einer Funktion als < (weniger) Operator STL Datenstrukturen wie set, multiset passieren kann, map, priority_queue, ...

Gibt es ein Problem, wenn unsere Funktion wie <= wirkt (weniger gleich)

Answer 1

Von effektive STL -> Artikel 21. Lassen Sie immer Vergleichsfunktionen für gleiche Werte gleich 0 zurückgeben.

einen Satz erstellen, in dem less_equal der Vergleichstyp ist, dann 10 in den Satz einfügen:

set<int, less_equal<int> > s; // s is sorted by "<=" 
s.insert(10); //insert the value 10 

versucht nun 10 wieder eingefügt:

s.insert(10); 

Für diesen Aufruf einzufügen, muss die eingestellte um herauszufinden, ob 10 bereits vorhanden ist. Wir wissen , dass es ist. aber das Set ist dumm wie Toast, also muss es überprüfen. Um es einfacher zu machen, zu verstehen, was passiert, wenn das Set dies tut, rufen wir die 10, die ursprünglich war eingefügt 10A und die 10, die wir versuchen, 10B einfügen.Das Set durchläuft seine internen Datenstrukturen auf der Suche nach der Platz zum Einfügen von 10B. Letztendlich muss es 10B überprüfen, um zu sehen, ob es dasselbe wie 10A ist. Die Definition von "gleich" für assoziative Container ist Äquivalenz, so dass der Satz prüft, ob 10B entspricht 10A. Bei diesem Test wird natürlich die Vergleichsfunktion des Sets verwendet. In diesem Beispiel ist das der Operator < =, weil wir less_equal als Vergleichsfunktion des Satzes angegeben haben und less_equal Operatoren bedeutet. Der Satz prüft also, ob dieser Ausdruck wahr ist:

!(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence 

Nun, 10A und 10B sind beide 10, so dass es klar ist wahr, dass 10A < = 10B. Ebenso klar, 10B < = 10A. Der obige Ausdruck vereinfacht somit

!!(true)&&!(true) 

und vereinfacht zu

false && false 

die einfach falsch ist. Das heißt, der Satz folgert, dass 10A und 10B nicht äquivalent sind, daher ist das nicht dasselbe, und es geht somit darum, 10B in den Behälter neben 10A einzufügen. Technisch führt diese Aktion zu undefiniertem Verhalten, aber das fast universelle Ergebnis ist, dass das Set mit zwei Kopien des Wertes 10 endet, und das bedeutet, dass es nicht länger gesetzt ist. Mit less_equal als Vergleichstyp haben wir den Container beschädigt! Darüber hinaus wird jede Vergleichsfunktion, bei der gleiche Werte wahr ergeben, dasselbe tun. Gleiche Werte sind definitionsgemäß nicht gleichwertig!

Answer 2

Es gibt tatsächlich ein Problem.

Die Vergleichsfunktion sollte strict weak ordering erfüllen, was <= nicht tut.

Answer 3

Ja, es gibt ein Problem.

Formal muss die Vergleichsfunktion eine strenge schwache Reihenfolge definieren, und <= tut das nicht.

Genauer gesagt wird die < auch Äquivalenz bestimmen (x und y sind äquivalent iff !(x < y) && !(y < x)). Dies gilt nicht für <= (mit diesem Operator würde Ihr Satz glauben, dass Objekte sind nie gleichwertig)