Was führt dazu, dass std::sort() auf Adressen außerhalb des gültigen Bereichs zugreift?

Question

Ich verstehe, dass die Vergleichsfunktion zur Verwendung von std::sort() eine strikte schwache Reihenfolge haben muss, sonst stürzt sie ab, weil der Zugriff auf die Adresse außerhalb des zulässigen Bereichs liegt.(https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)

Warum sollte std::sort() jedoch auf eine Adresse außerhalb der Grenzen zugreifen, wenn die Vergleichsfunktion keine strikte schwache Reihenfolge hat?Was versucht es zu vergleichen?

Außerdem frage ich mich, ob es in STL noch andere Fallstricke gibt, die ich beachten sollte.

Answer 1

Das erste ist, dass der Aufruf des Algorithmus mit einem Komparator, der nicht den Anforderungen entspricht, undefiniertes Verhalten ist und alles geht ...

Abgesehen davon gehe ich jedoch davon aus, dass Sie daran interessiert sind, welche Art von Implementierung bei einem fehlerhaften Komparator letztendlich zu Zugriffen außerhalb der Grenzen führen könnte. Sollte die Implementierung die Grenzen nicht überprüfen, bevor sie überhaupt auf die Elemente zugreift?d.h.bevor Sie den Komparator aufrufen

Die Antwort ist Leistung, und das ist nur eines der möglichen Dinge, die zu solchen Problemen führen können.Es gibt verschiedene Implementierungen von Sortieralgorithmen, aber in den meisten Fällen gilt: std::sort basiert auf einer Variante von Quicksort, die auf einem anderen Sortieralgorithmus wie Mergesort degeneriert, um die Leistung von Quicksort im schlechtesten Fall zu vermeiden.

Die Implementierung von Quicksort wählt einen Pivot aus, verteilt dann die Eingabe um den Pivot herum und sortiert dann beide Seiten unabhängig voneinander.Es gibt verschiedene Strategien zur Auswahl des Pivots, eine gemeinsame Strategie ist jedoch der Median von drei:Der Algorithmus ruft die Werte des ersten, letzten und mittleren Elements ab, wählt den Median der drei aus und verwendet diesen als Pivot-Wert.

Konzeptionell geht die Partition von links aus, bis sie ein Element findet, das nicht kleiner als der Pivot ist. Anschließend geht sie von rechts aus und versucht, ein Element zu finden, das kleiner als der Pivot ist.Treffen die beiden Cursor aufeinander, ist die Partitionierung abgeschlossen.Wenn die fehl am Platz befindlichen Elemente gefunden werden, werden die Werte vertauscht und der Prozess wird in dem von beiden Cursorn festgelegten Bereich fortgesetzt.Die Schleife, die von links ausgeht, um das auszutauschende Element zu finden, würde wie folgt aussehen:

while (pos < end && value(pos) < pivot) { ++pos; }

Während die Partition im Allgemeinen nicht davon ausgehen kann, dass der Wert von Pivot im Bereich liegt, ist QuickSort weiß dass es so ist, schließlich hat es den Drehpunkt aus den Elementen im Bereich ausgewählt.Eine übliche Optimierung besteht in diesem Fall darin, den Wert des Medians so zu vertauschen, dass er sich im letzten Element der Schleife befindet.Das garantiert value(pos) < pivot wird wahr sein Vor pos == end (schlimmsten Fall: pos == end - 1).Die Implikation hier ist, dass wir den Scheck für das Ende des Bereichs weglassen und a verwenden können unchecked_partition (wählen Sie den Namen Ihrer Wahl) mit einer einfacheren, schnelleren Bedingung:

while (/*pos < end &&*/ value(pos) < pivot) ++pos;

Alles perfekt, bis auf das < wird buchstabiert comparator(value(pos), pivot).Wenn nun die comparator falsch implementiert ist, könnte dies enden comparator(pivot,pivot) == true und der Cursor wird außerhalb der Grenzen laufen.

Beachten Sie, dass dies nur ein Beispiel für die Optimierung des Algorithmus ist, mit dem die Grenzenprüfung für die Leistung entfernt werden kann:eine gültige Bestellung vorausgesetzt, ist dies der Fall unmöglich um das Array in der obigen Schleife zu verlassen, wenn Quicksort den Pivot auf das letzte Element setzt Vor Aufrufen dieser geänderten Partition.

Zurück zur Frage:

Sollte die Implementierung die Grenzen nicht überprüfen, bevor sie überhaupt auf die Elemente zugreift?d.h.bevor Sie den Komparator aufrufen

Nein, nicht, wenn die Grenzüberprüfung entfernt wird, indem nachgewiesen wird, dass das Array nicht verlassen wird. Dieser Beweis basiert jedoch auf der Voraussetzung, dass der Komparator gültig ist.

Answer 2

std::sort erfordert tatsächlich, dass der angegebene Komparator eine strikte schwache Reihenfolge feststellt, ansonsten macht die Sortierung nicht wirklich viel Sinn.

Wenn er sich auf den Reichweiten zugreift, ist der von Ihnen gepostete Link zu einem Fehlerbericht, d. H. Es soll dies nicht eigentlich sein. Compiler wie jede andere Software können und werden Fehler haben. Wie von Adam erwähnt, wurde dieser besondere Fehlerbericht abgelehnt, da es nicht wirklich ein Fehler ist.

Was genau passiert, wenn Sie keine strikte schwache Reihenfolge haben, ist nicht vom Standard definiert, es ist nicht sinnvoll, dies zu tun, und wird daher vom Standard ausgelassen. Daher ist es undefiniertes durch Unterlassung. undefined bedeutet, dass alles passieren kann, sogar aus dem Reichweiten zugreifen kann.

as für die Vermeidung von "Fallstricks" sind sich der Anforderungen der von Ihnen verwendeten Algorithmen und Funktionen bewusst. Für C ++ gibt es eine schöne Referenzstelle, die ich normalerweise verwende: cppreference

Welches auf die Seite von std::sort sagt:

Comp - Vergleichsfunktionsobjekt (d. H. Ein Objekt, das die Anforderungen des Vergleichs erfüllt), der true zurückgibt, wenn das erste Argument geringer ist als (d. H. Bestellt zuvor) der zweiten.

mit einem Link zur Beschreibung von Vergleichen