Wie implementiere ich klassische Sortieralgorithmen in modernem C ++?

Der std::sortAlgorithmus (und seine Verwandten std::partial_sortund std::nth_element) aus der C ++ - Standardbibliothek ist in den meisten Implementierungen eine komplizierte und hybride Zusammenführung elementarerer Sortieralgorithmen wie Auswahlsortierung, Einfügesortierung, Schnellsortierung, Zusammenführungssortierung oder Heap-Sortierung.

Hier und auf Schwesterseiten wie https://codereview.stackexchange.com/ gibt es viele Fragen zu Fehlern, Komplexität und anderen Aspekten der Implementierung dieser klassischen Sortieralgorithmen. Die meisten der angebotenen Implementierungen bestehen aus Rohschleifen, verwenden Indexmanipulation und konkrete Typen und sind im Allgemeinen nicht trivial in Bezug auf Korrektheit und Effizienz zu analysieren.

Frage : Wie können die oben genannten klassischen Sortieralgorithmen mit modernem C ++ implementiert werden?

• Keine Rohschleifen , sondern Kombination der algorithmischen Bausteine ​​der Standardbibliothek aus<algorithm>
• Iterator-Schnittstelle und Verwendung von Vorlagen anstelle von Indexmanipulation und konkreten Typen
• C ++ 14-Stil , einschließlich der vollständigen Standardbibliothek, sowie syntaktische Rauschunterdrücker wie autoTemplate-Aliase, transparente Komparatoren und polymorphe Lambdas.

Anmerkungen :

• Weitere Referenzen zu Implementierungen von Sortieralgorithmen finden Sie in Wikipedia , Rosetta Code oder http://www.sorting-algorithms.com/.
• Gemäß den Konventionen von Sean Parent (Folie 39) ist eine forRohschleife eine Schleife länger als die Zusammensetzung zweier Funktionen mit einem Operator. Also f(g(x));oder f(x); g(x);oder f(x) + g(x);sind keine Rohschleifen, und die Schleifen sind auch nicht in selection_sortund insertion_sortunter.
• Ich folge der Terminologie von Scott Meyers, um das aktuelle C ++ 1y bereits als C ++ 14 zu bezeichnen, und um C ++ 98 und C ++ 03 beide als C ++ 98 zu bezeichnen, also flamme mich nicht dafür.
• Wie in den Kommentaren von @Mehrdad vorgeschlagen, stelle ich am Ende der Antwort vier Implementierungen als Live-Beispiel bereit: C ++ 14, C ++ 11, C ++ 98 und Boost und C ++ 98.
• Die Antwort selbst wird nur in C ++ 14 dargestellt. Wo relevant, bezeichne ich die syntaktischen und Bibliotheksunterschiede, bei denen sich die verschiedenen Sprachversionen unterscheiden.

Algorithmische Bausteine

Wir beginnen mit dem Zusammenstellen der algorithmischen Bausteine ​​aus der Standardbibliothek:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

• Die Iterator-Tools wie non-member std::begin()/ std::end()sowie with std::next()sind nur ab C ++ 11 und höher verfügbar. Für C ++ 98 muss man diese selbst schreiben. Es gibt Ersatz von Boost.Range in boost::begin()/ boost::end()und von Boost.Utility in boost::next().
• Der std::is_sortedAlgorithmus ist nur für C ++ 11 und höher verfügbar. Für C ++ 98 kann dies std::adjacent_findals handgeschriebenes Funktionsobjekt implementiert werden. Boost.Algorithm bietet auch einen boost::algorithm::is_sortedals Ersatz.
• Der std::is_heapAlgorithmus ist nur für C ++ 11 und höher verfügbar.

Syntaktische Leckereien

C ++ 14 bietet transparente Komparatoren der Form std::less<>, die polymorph auf ihre Argumente einwirken. Dadurch wird vermieden, dass ein Iteratortyp angegeben werden muss. Dies kann in Kombination mit den Standardfunktionsvorlagenargumenten von C ++ 11 verwendet werden , um eine einzelne Überladung für Sortieralgorithmen zu erstellen , die <als Vergleich dienen, und für Algorithmen mit einem benutzerdefinierten Vergleichsfunktionsobjekt.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

In C ++ 11 kann ein wiederverwendbarer Vorlagenalias definiert werden , um den Werttyp eines Iterators zu extrahieren, wodurch die Signaturen der Sortieralgorithmen geringfügig überladen werden:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

In C ++ 98 müssen zwei Überladungen geschrieben und die ausführliche typename xxx<yyy>::typeSyntax verwendet werden

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• Eine weitere syntaktische Besonderheit besteht darin, dass C ++ 14 das Umschließen benutzerdefinierter Komparatoren durch polymorphe Lambdas erleichtert (mit autoParametern, die wie Argumente für Funktionsvorlagen abgeleitet werden).
• C ++ 11 enthält nur monomorphe Lambdas, für die der obige Vorlagenalias verwendet werden muss value_type_t.
• In C ++ 98, entweder man braucht eine eigenständige Funktionsobjekt zu schreiben oder zu der ausführlichen greifen std::bind1st/ std::bind2nd/ std::not1Art der Syntax.
• Boost.Bind verbessert dies mit boost::bindund _1/ oder _2Platzhaltersyntax.
• C ++ 11 und höher haben auch std::find_if_not, während C ++ 98 std::find_ifmit einem std::not1um ein Funktionsobjekt benötigt.

C ++ - Stil

Es gibt noch keinen allgemein akzeptablen C ++ 14-Stil. Zum Guten oder zum Schlechten verfolge ich Scott Meyers Entwurf Effective Modern C ++ und Herb Sutters überarbeitetes GotW genau . Ich verwende die folgenden Stilempfehlungen:

• Herb Sutters Empfehlung "Fast immer automatisch" und Scott Meyers "Auto lieber bestimmten Typdeklarationen vorziehen" , für die die Kürze unübertroffen ist, obwohl ihre Klarheit manchmal umstritten ist .
• Scott Meyers ' "Unterscheiden ()und {}beim Erstellen von Objekten" und wählen Sie konsequent die Klammerinitialisierung {}anstelle der guten alten Klammerinitialisierung ()(um alle Probleme mit der Analyse im generischen Code zu umgehen).
• Scott Meyers ' "Bevorzugen Sie Alias-Deklarationen gegenüber Typedefs" . Für Vorlagen ist dies ohnehin ein Muss, und die Verwendung überall anstelle von typedefZeit spart Zeit und erhöht die Konsistenz.
• Ich verwende for (auto it = first; it != last; ++it)an einigen Stellen ein Muster, um eine Schleifeninvariantenprüfung für bereits sortierte Unterbereiche zu ermöglichen. Im Produktionscode ist die Verwendung von while (first != last)und ++firstirgendwo innerhalb der Schleife möglicherweise etwas besser.

Auswahl sortieren

Die Auswahlsortierung passt sich in keiner Weise an die Daten an, daher ist ihre Laufzeit immerO(N²). Die Auswahlsortierung hat jedoch die Eigenschaft, die Anzahl der Swaps zu minimieren . In Anwendungen, in denen die Kosten für den Austausch von Elementen hoch sind, kann die Auswahlsortierung der Algorithmus der Wahl sein.

Um es mithilfe der Standardbibliothek zu implementieren, verwenden Sie wiederholt std::min_element, um das verbleibende Mindestelement zu finden und iter_swapes auszutauschen:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Beachten Sie, dass selection_sortder bereits verarbeitete Bereich [first, it)als Schleifeninvariante sortiert ist. Die Mindestanforderungen sind Vorwärtsiteratoren im Vergleich zu Iteratoren mit std::sortwahlfreiem Zugriff.

Details weggelassen :

• Die Auswahlsortierung kann mit einem frühen Test if (std::distance(first, last) <= 1) return;(oder für vorwärts- / bidirektionale Iteratoren :) optimiert werden if (first == last || std::next(first) == last) return;.
• Für bidirektionale Iteratoren kann der obige Test mit einer Schleife über das Intervall kombiniert werden [first, std::prev(last)), da das letzte Element garantiert das minimal verbleibende Element ist und keinen Austausch erfordert.

Sortieren durch Einfügen

Obwohl es sich um einen der elementaren Sortieralgorithmen mit O(N²)Worst-Case-Zeit handelt, ist die Einfügungssortierung der Algorithmus der Wahl, entweder wenn die Daten nahezu sortiert sind (weil sie adaptiv sind ) oder wenn die Problemgröße klein ist (weil sie einen geringen Overhead hat). Aus diesen Gründen und weil es auch stabil ist , wird die Einfügesortierung häufig als rekursiver Basisfall (wenn die Problemgröße klein ist) für Sortieralgorithmen mit höherem Overhead-Divide-and-Conquer-Sortier verwendet, z. B. Zusammenführungssortierung oder schnelle Sortierung.

insertion_sortVerwenden Sie std::upper_boundzum Implementieren mit der Standardbibliothek wiederholt die Position, an die das aktuelle Element std::rotateverschoben werden soll , und verschieben Sie die verbleibenden Elemente im Eingabebereich nach oben:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Beachten Sie, dass insertion_sortder bereits verarbeitete Bereich [first, it)als Schleifeninvariante sortiert ist. Die Einfügesortierung funktioniert auch mit Vorwärtsiteratoren.

Details weggelassen :

• Die Einfügesortierung kann mit einem frühen Test if (std::distance(first, last) <= 1) return;(oder für vorwärts / bidirektionale Iteratoren :) if (first == last || std::next(first) == last) return;und einer Schleife über das Intervall optimiert werden [std::next(first), last), da das erste Element garantiert vorhanden ist und keine Drehung erfordert.
• Bei bidirektionalen Iteratoren kann die binäre Suche zum Auffinden der Einfügemarke durch eine umgekehrte lineare Suche unter Verwendung des std::find_if_notAlgorithmus der Standardbibliothek ersetzt werden.

Vier Live-Beispiele ( C ++ 14 , C ++ 11 , C ++ 98 und Boost , C ++ 98 ) für das folgende Fragment:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();

• Für zufällige Eingaben ergibt sich ein O(N²)Vergleich, dies verbessert sich jedoch gegenüber O(N)Vergleichen für fast sortierte Eingaben. Die binäre Suche verwendet immer O(N log N)Vergleiche.
• Bei kleinen Eingabebereichen kann die bessere Speicherlokalität (Cache, Prefetching) einer linearen Suche auch eine binäre Suche dominieren (dies sollte natürlich getestet werden).

Schnelle Sorte

Bei sorgfältiger Implementierung ist die schnelle Sortierung robust und hat O(N log N)Komplexität erwartet, jedoch im O(N²)schlimmsten Fall Komplexität, die mit kontrovers ausgewählten Eingabedaten ausgelöst werden kann. Wenn keine stabile Sortierung benötigt wird, ist die schnelle Sortierung eine ausgezeichnete Allzweck-Sortierung.

Selbst für die einfachsten Versionen ist die schnelle Sortierung mit der Standardbibliothek etwas komplizierter zu implementieren als die anderen klassischen Sortieralgorithmen. Der Ansatz unten verwendet einige Iterator Dienstprogramme die lokalisieren mittlere Element des Eingangsbereichs [first, last)als Drehpunkt, dann zwei Anrufe verwenden , um std::partition(die O(N)) zu Dreiweg-Partition der Eingangsbereich in Segmente von Elementen , die kleiner sind als gleich, bzw. größer als der ausgewählte Drehpunkt. Schließlich werden die beiden äußeren Segmente mit Elementen, die kleiner und größer als der Drehpunkt sind, rekursiv sortiert:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

Eine schnelle Sortierung ist jedoch ziemlich schwierig, um korrekt und effizient zu sein, da jeder der oben genannten Schritte sorgfältig geprüft und für Code auf Produktionsebene optimiert werden muss. Insbesondere für die O(N log N)Komplexität muss der Pivot zu einer ausgeglichenen Partition der Eingabedaten führen, die im Allgemeinen für einen O(1)Pivot nicht garantiert werden kann, die jedoch garantiert werden kann, wenn man den Pivot als O(N)Median des Eingabebereichs festlegt .

Details weggelassen :

• Die obige Implementierung ist besonders anfällig für spezielle Eingaben, z. B. hat sie O(N^2)Komplexität für die Eingabe " Orgelpfeife " 1, 2, 3, ..., N/2, ... 3, 2, 1(da die Mitte immer größer als alle anderen Elemente ist).
• Die Auswahl des Median-of-3- Pivots aus zufällig ausgewählten Elementen aus dem Eingabebereich schützt vor nahezu sortierten Eingaben, bei denen sich die Komplexität sonst verschlechtern würdeO(N^2).
• Die 3-Wege-Partitionierung (Trennen von Elementen, die kleiner, gleich und größer als der Drehpunkt sind), wie durch die beiden Aufrufe an gezeigt,std::partitionist nicht der effizientesteO(N)Algorithmus, um dieses Ergebnis zu erzielen.
• Bei Iteratoren mit wahlfreiem Zugriff kann eine garantierte O(N log N)Komplexität durch Auswahl des Median-Pivots erreicht werden std::nth_element(first, middle, last), gefolgt von rekursiven Aufrufen von quick_sort(first, middle, cmp)und quick_sort(middle, last, cmp).
• Diese Garantie ist jedoch mit Kosten verbunden, da der konstante Faktor der O(N)Komplexität von std::nth_elementteurer sein kann als der der O(1)Komplexität eines Median-of-3-Pivots, gefolgt von einem O(N)Aufruf von std::partition(was eine cachefreundliche einzelne Weiterleitung ist) die Daten).

Zusammenführen, sortieren

Wenn die Verwendung von O(N)zusätzlichem Speicherplatz keine Rolle spielt, ist die Zusammenführungssortierung eine ausgezeichnete Wahl: Es ist der einzige stabile O(N log N) Sortieralgorithmus.

Die Implementierung mit Standardalgorithmen ist einfach: Verwenden Sie einige Iterator-Dienstprogramme, um die Mitte des Eingabebereichs zu lokalisieren, [first, last)und kombinieren Sie zwei rekursiv sortierte Segmente mit std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Die Zusammenführungssortierung erfordert bidirektionale Iteratoren, wobei der Engpass der ist std::inplace_merge. Beachten Sie, dass beim Sortieren verknüpfter Listen für die Zusammenführungssortierung nur O(log N)zusätzlicher Speicherplatz erforderlich ist (für die Rekursion). Der letztere Algorithmus wird von std::list<T>::sortin der Standardbibliothek implementiert .

Haufen sortieren

Die Heap-Sortierung ist einfach zu implementieren, führt eineO(N log N)direkte Sortierung durch, ist jedoch nicht stabil.

Die erste Schleife, die O(N)"Heapify" -Phase, versetzt das Array in die Heap-Reihenfolge. Die zweite Schleife, die O(N log N"Sortdown" -Phase, extrahiert wiederholt das Maximum und stellt die Heap-Reihenfolge wieder her. Die Standardbibliothek macht dies äußerst einfach:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Für den Fall , halten Sie es für „Betrug“ verwenden , std::make_heapund std::sort_heapSie können eine Ebene tiefer gehen und die Funktionen selbst in Bezug auf die schreiben std::push_heapund std::pop_heapjeweils:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

Die Standardbibliothek gibt sowohl push_heapals auch pop_heapals Komplexität an O(log N). Beachten Sie jedoch, dass die äußere Schleife über den Bereich [first, last)zu O(N log N)Komplexität für führt make_heap, während std::make_heapsie nur O(N)Komplexität aufweist. Für die gesamte O(N log N)Komplexität der heap_sortes spielt keine Rolle.

Details weggelassen : O(N)Implementierung vonmake_heap

Testen

Hier sind vier Live-Beispiele ( C ++ 14 , C ++ 11 , C ++ 98 und Boost , C ++ 98 ), in denen alle fünf Algorithmen an einer Vielzahl von Eingaben getestet werden (die nicht erschöpfend oder streng sein sollen). Beachten Sie nur die großen Unterschiede im LOC: C ++ 11 / C ++ 14 benötigt ungefähr 130 LOC, C ++ 98 und Boost 190 (+ 50%) und C ++ 98 mehr als 270 (+ 100%).

Eine andere kleine und ziemlich elegante, die ursprünglich bei der Codeüberprüfung gefunden wurde . Ich dachte, es lohnt sich zu teilen.

Sortierung zählen

Während es eher spezialisiert ist, das Zählen Art ist eine einfache Integer - Algorithmus sortiert und oft sehr schnell werden kann , um die Werte der ganzen Zahlen zu sortieren sind nicht zu weit voneinander entfernt vorgesehen. Es ist wahrscheinlich ideal, wenn man jemals eine Sammlung von einer Million Ganzzahlen sortieren muss, von denen bekannt ist, dass sie beispielsweise zwischen 0 und 100 liegen.

Um eine sehr einfache Zählsortierung zu implementieren, die sowohl mit vorzeichenbehafteten als auch mit vorzeichenlosen Ganzzahlen funktioniert, müssen die kleinsten und größten Elemente in der Sammlung zum Sortieren gefunden werden. Ihr Unterschied gibt die Größe des zuzuordnenden Zählfelds an. Dann wird ein zweiter Durchlauf durch die Sammlung durchgeführt, um die Anzahl der Vorkommen jedes Elements zu zählen. Schließlich schreiben wir die erforderliche Anzahl jeder Ganzzahl zurück in die ursprüngliche Sammlung.

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

Während es nur dann nützlich ist, wenn bekannt ist, dass der Bereich der zu sortierenden Ganzzahlen klein ist (im Allgemeinen nicht größer als die Größe der zu sortierenden Sammlung), würde eine allgemeinere Zählsortierung die besten Fälle verlangsamen. Wenn nicht bekannt ist, dass der Bereich klein ist, kann stattdessen ein anderer Algorithmus wie Radix-Sortierung , ska_sort oder Spreadsort verwendet werden.

Details weggelassen :

• Wir hätten die Grenzen des vom Algorithmus als Parameter akzeptierten Wertebereichs überschreiten können, um den ersten std::minmax_elementDurchgang durch die Sammlung vollständig zu beseitigen . Dies macht den Algorithmus noch schneller, wenn eine nützlich kleine Bereichsgrenze auf andere Weise bekannt ist. (Es muss nicht exakt sein. Das Übergeben einer Konstante von 0 bis 100 ist immer noch viel besser als ein zusätzlicher Durchlauf über eine Million Elemente, um herauszufinden, dass die wahren Grenzen 1 bis 95 sind. Sogar 0 bis 1000 wären es wert zusätzliche Elemente werden einmal mit Null geschrieben und einmal gelesen).

• Das schnelle Wachsen countsist ein weiterer Weg, um einen separaten ersten Durchgang zu vermeiden. Das Verdoppeln der countsGröße jedes Mal, wenn es wachsen muss, ergibt eine amortisierte O (1) -Zeit pro sortiertem Element (siehe Analyse der Einfügekosten für Hash-Tabellen für den Beweis, dass exponentiell gewachsen der Schlüssel ist). Das Wachsen am Ende für ein neues Element maxist einfach std::vector::resize, wenn neue Elemente mit Nullen hinzugefügt werden. Das Ändern minim laufenden Betrieb und das Einfügen neuer Elemente mit Nullen an der Vorderseite kann std::copy_backwardnach dem Wachstum des Vektors erfolgen. Dann std::filldie neuen Elemente auf Null setzen.

• Die countsInkrementschleife ist ein Histogramm. Wenn sich die Daten wahrscheinlich stark wiederholen und die Anzahl der Fächer gering ist, kann es sich lohnen, über mehrere Arrays zu rollen , um den Engpass bei der Serialisierung der Datenabhängigkeit beim Speichern / erneuten Laden in denselben Behälter zu verringern. Dies bedeutet, dass am Anfang mehr Zählungen auf Null und am Ende mehr Schleifen durchgeführt werden müssen. Dies sollte sich jedoch auf den meisten CPUs für unser Beispiel von Millionen von 0 bis 100 Zahlen lohnen, insbesondere wenn die Eingabe möglicherweise bereits (teilweise) sortiert ist und habe lange Läufe der gleichen Anzahl.

• Im obigen Algorithmus verwenden wir eine min == maxPrüfung, um frühzeitig zurückzukehren, wenn jedes Element den gleichen Wert hat (in diesem Fall wird die Sammlung sortiert). Es ist tatsächlich möglich, stattdessen vollständig zu überprüfen, ob die Sammlung bereits sortiert ist, während die Extremwerte einer Sammlung ermittelt werden, ohne dass zusätzliche Zeit verschwendet wird (wenn der erste Durchgang immer noch einen Speicherengpass mit der zusätzlichen Arbeit des Aktualisierens von min und max aufweist). Ein solcher Algorithmus existiert jedoch nicht in der Standardbibliothek, und das Schreiben eines Algorithmus wäre mühsamer als das Schreiben des Restes der Zählsortierung selbst. Es bleibt als Übung für den Leser.

• Da der Algorithmus nur mit ganzzahligen Werten arbeitet, können statische Zusicherungen verwendet werden, um zu verhindern, dass Benutzer offensichtliche Typfehler machen. In einigen Kontexten kann ein Substitutionsfehler mit std::enable_if_tbevorzugt werden.

• Während modernes C ++ cool ist, könnte zukünftiges C ++ noch cooler sein: Strukturierte Bindungen und einige Teile des Ranges TS würden den Algorithmus noch sauberer machen.