Für geeignete Datentypen kann eine gute Radix-Sortierung die Vergleichssorten um Längen unterbieten, aber std::sort wird normalerweise als Introsort implementiert. Gibt es einen Grund, nicht radix sort zu verwenden, um std::sort zu implementieren? Die Radix-Sortierung reicht nicht aus, um std::sort zu implementieren, da std::sort nur Typen benötigt, die vergleichbar sind, aber für Typen, bei denen Vergleich und Radix-basierte Sortierung die gleiche Antwort liefert (zB int ), scheint dies eine tief hängende Frucht zu sein unplucked.
Wäre es legal, std::sort mit Überladungen zu implementieren, die bei Bedarf eine Radix-Sortierung verwenden? Gibt es etwas über die Anforderungen von std::sort , die dies grundsätzlich verhindern?
Bearbeiten: Ich hätte etwas klarer sein sollen. Ich frage, ob dies für eine Implementierung der Standardbibliothek legal wäre. Ich frage nicht, ob ein Benutzer einer Standardbibliotheksimplementierung irgendetwas im Namensraum std platziert. Ich weiß, dass dies außer in bestimmten Fällen illegal ist.
Die Kommentare enthalten eine "Als-ob" -Regel. Das ist eigentlich nicht nötig. std::sort wird nicht angegeben "als ob Introsort verwendet wird". Die Spezifikation für std::sort ist kurz und erfordert nur einen Effekt (sortiert) und Komplexität (O (N log N)) für die Anzahl der Vergleiche. Radix sort trifft beides.
25.4.1.1 Sortieren
template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);1 Effekte : Sortiert die Elemente im Bereich [first, last].
2 Benötigt : RandomAccessIterator muss die Anforderungen von ValueSwappable (17.6.3.2) erfüllen. Der Typ von * first muss die Anforderungen von MoveConstructible (Tabelle 20) und von MoveAssignable (Tabelle 22) erfüllen.
3 Komplexität : O (N log (N)) (mit N == letzter - erster) Vergleich.
In der Praxis ist der Vergleich von zwei Werten für die Registerbreite a<b eine viel schnellere Operation als das Extrahieren von Ziffern und das Vergleichen einer Sequenz dieser Ziffern, selbst wenn wir Bits oder hexadezimale Ziffern verwenden würden. Sicher, es ist ein konstanter Faktorunterschied, aber das Extrahieren und Vergleichen von 32 einzelnen Bits wird ungefähr 100 mal langsamer als ein direkter Vergleich sein. Das übertrifft die meisten theoretischen Bedenken, zumal log N auf heutigen Computern nicht wirklich 100 sein kann.
Tags und Links c++ language-lawyer sorting standard-library