std::sort
| Definiert in Header <algorithm> |
||
| template< class RandomIt > void sort( RandomIt first, RandomIt last ); |
(1) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class RandomIt > void sort( ExecutionPolicy&& policy, |
(2) | (seit C++17) |
| template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp ); |
(3) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class RandomIt, class Compare > void sort( ExecutionPolicy&& policy, |
(4) | (seit C++17) |
Sortiert die Elemente im Bereich [first, last) in nicht absteigender Reihenfolge. Die Reihenfolge gleicher Elemente ist nicht garantiert.
|
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true. |
(bis C++20) |
|
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true. |
(seit C++20) |
Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert
|
(bis C++11) |
|
(seit C++11) |
Inhalt |
[bearbeiten] Parameter
| first, last | - | das Paar von Iteratoren, das den zu sortierenden Bereich von Elementen definiert |
| policy | - | die Ausführungsrichtlinie, die verwendet werden soll |
| comp | - | Vergleichsfunktions-Objekt (d.h. ein Objekt, das die Anforderungen an Compare erfüllt), das true zurückgibt, wenn das erste Argument *weniger* (d.h. *vorher*) als das zweite geordnet ist. Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein bool cmp(const Type1& a, const Type2& b); Obwohl die Signatur nicht unbedingt const& haben muss, darf die Funktion die übergebenen Objekte nicht verändern und muss in der Lage sein, alle Werte vom Typ (möglicherweise const) |
| Typanforderungen | ||
-RandomIt muss die Anforderungen an einen LegacyRandomAccessIterator erfüllen. | ||
-Compare muss die Anforderungen an Compare erfüllen. | ||
[bearbeiten] Komplexität
Gegeben N als last - first
[bearbeiten] Ausnahmen
Die Überladungen mit einem Template-Parameter namens ExecutionPolicy berichten Fehler wie folgt
- Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und
ExecutionPolicyeine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andereExecutionPolicyist das Verhalten implementierungsabhängig. - Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.
[bearbeiten] Mögliche Implementierung
Siehe auch die Implementierungen in libstdc++ und libc++.
[bearbeiten] Hinweise
Vor LWG713 erlaubte die Komplexitätsanforderung, dass sort() nur mittels Quicksort implementiert werden konnte, was im schlimmsten Fall O(N2
) Vergleiche benötigen kann.
Introsort kann alle Fälle mit O(N·log(N)) Vergleichen bewältigen (ohne zusätzlichen Overhead im Durchschnittsfall) und wird daher üblicherweise zur Implementierung von sort() verwendet.
libc++ hat die korrigierte Anforderung an die Zeitkomplexität erst bis LLVM 14 nicht implementiert.
[bearbeiten] Beispiel
#include <algorithm> #include <array> #include <functional> #include <iostream> #include <string_view> int main() { std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; auto print = [&s](std::string_view const rem) { for (auto a : s) std::cout << a << ' '; std::cout << ": " << rem << '\n'; }; std::sort(s.begin(), s.end()); print("sorted with the default operator<"); std::sort(s.begin(), s.end(), std::greater<int>()); print("sorted with the standard library compare function object"); struct { bool operator()(int a, int b) const { return a < b; } } customLess; std::sort(s.begin(), s.end(), customLess); print("sorted with a custom function object"); std::sort(s.begin(), s.end(), [](int a, int b) { return a > b; }); print("sorted with a lambda expression"); }
Ausgabe
0 1 2 3 4 5 6 7 8 9 : sorted with the default operator< 9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object 0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object 9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression
[bearbeiten] Fehlerberichte
Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.
| DR | angewendet auf | Verhalten wie veröffentlicht | Korrigiertes Verhalten |
|---|---|---|---|
| LWG 713 | C++98 | die O(N·log(N)) Zeitkomplexität war nur im Durchschnitt gefordert | sie ist für den schlimmsten Fall gefordert |
[bearbeiten] Siehe auch
| Sortiert die ersten N Elemente eines Bereichs (Funktionstemplate) | |
| Sortiert einen Bereich von Elementen und behält dabei die Reihenfolge zwischen gleichen Elementen bei (Funktionstemplate) | |
| (C++20) |
Sortiert einen Bereich aufsteigend (Algorithmus-Funktionsobjekt) |
