Ich bin mir bewusst, dass assoziative STL-Container (und andere Container, die sortiert werden, würde ich raten) das Sortierkriterium verwenden, um auf Gleichheit zu prüfen.
Das Sortierkriterium für Container lautet standardmäßig st :: less, so dass der Gleichheitstest für einen Container erfolgen würde:
%Vor%oder etwas Ähnliches. Ich hatte ein paar Fragen dazu ...
Zunächst scheint es, als wäre es ein seltsam ineffizienter Vergleich für Gleichheit - warum macht die STL das so? Ich hätte erwartet, dass STL-Container stattdessen nur einen zusätzlichen Standardparameter für die Gleichheit verwenden.
Meine zweite Frage betrifft eher die Bewertung der obigen if-Aussage. In C ++, wie viel von dieser Aussage würde ausgewertet werden (lhs & gt; rhs) war wahr? Würde es aufhören zu versuchen nach der Bewertung der Seite, die fehlgeschlagen ist und somit etwas Effizienz gespart? Wenn ja, welcher Teil des Ausdrucks wird zuerst ausgewertet?
In "Effective STL" hat Scott Meyers eine ausführliche Diskussion darüber in Item 19 :
Verstehen Sie den Unterschied zwischen Gleichheit und Äquivalenz.
Gleichheit basiert, wie Sie vielleicht erwarten, auf operator== .
Äquivalenz "basiert auf der relativen Anordnung von Objektwerten in einem sortierten Bereich ... Zwei Objekte haben äquivalente Werte in einem Container c , wenn keiner in c dem anderen vorangeht Sortierreihenfolge. "
Meyers drückt es so aus:
%Vor%Meyers wiederholt dann:
Das macht Sinn: zwei Werte sind äquivalent (in Bezug auf einige Bestellkriterium), wenn keiner dem anderen vorausgeht (nach dem Kriterium.)
Warum die STL das so macht:
Durch Verwendung nur einer einzigen Vergleichsfunktion und durch Verwendung von Gleichwertigkeit als der Schiedsrichter dessen, was es bedeutet "gleich" zu sein Standard assoziative Container ... vermeiden Sie die Art von Verwirrung, die würde aus der Vermischung von Anwendungen der Gleichheit und Äquivalenz innerhalb entstehen Standard assoziative Container.
Lesen Sie Punkt 19 (der den besseren Teil von 6 Seiten umfasst), damit Sie den vollen Geschmack erhalten.
STL assoziative Container
Sie meinen: Standard C ++ sortierte assoziative Container.
Ich hätte erwartet, dass STL-Container stattdessen einen zusätzlichen Standardparameter für die Gleichheit verwenden würden.
Was würde das erreichen? In Ihrem Lehrbuch Rot-Schwarz-Baum-Algorithmus statt
%Vor%hättest du
%Vor%so noch zwei Vergleiche im schlimmsten Fall.
Auf die Kommentare zu dieser Antwort antwortend: Wenn nur ein Kleiner-als-Operator zur Verfügung steht, sind die Container wesentlich einfacher zu verwenden, da es nicht notwendig ist, Konsistenz zwischen weniger als und gleich zu halten. Stellen wir uns vor, Sie haben ein Programm, das Gleitkommazahlen speichert. Eines Tages entscheidet jemand, die bitweise Gleichheit float_equals -Funktion zu ersetzen, die zufälligerweise zufällig von einigen Containern , aber auch von ihrem Code verwendet wird. Wenn diese Person die float_less -Funktion nicht aktualisiert, weil ihr Code diese Funktion nicht verwendet , bricht Ihr Containercode auf mysteriöse Weise zusammen.
(Oh und im gezeigten Beispielcode gilt wie immer Kurzschluss.)
C ++ bewertet if () von links nach rechts für Ihren Fall mit ||. Evaluiert die linke Seite (lhs & lt; rhs) - Wenn es wahr ist und es keine zusammengesetzte Aussage ist (es ist nicht in Ihrem Fall), wertet es das Ganze als wahr aus, ohne die rechte Seite zu überprüfen. (Dann gibt es tatsächlich einen negierten Wert zurück, da es nicht davor steht.) Wenn es falsch ist, dann geht es auf die rechte Seite (rechts & lt; lhs) und wertet das und dann den ganzen Ausdruck aus.
Zunächst scheint es, als wäre es ein seltsam ineffizienter Vergleich für Gleichheit
Ja, aber sortierte Container machen diesen Test relativ selten.
Eine Vergleichsfunktion wie strcmp wäre besser. Die Verwendung von "Kleiner als" und "Vergleich" wäre immer noch besser.
In C ++, wie viel dieser Aussage (lhs & gt; rhs) wäre wahr?
In C und in C ++ werden a && b , a || b , a, b , a ? b : c von links nach rechts ausgewertet, wobei nur der nützliche rechte Teil ausgewertet wird (außer überladen ) && , || , , Operatoren in C ++).
Dies ermöglicht mehrere nützliche kurze Tests wie: p != NULL && *p > 2