std::partial_sort
| Definiert in Header <algorithm> |
||
template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last ); |
(1) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class RandomIt > void partial_sort( ExecutionPolicy&& policy, |
(2) | (seit C++17) |
template< class RandomIt, class Compare > void partial_sort( RandomIt first, RandomIt middle, RandomIt last, |
(3) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class RandomIt, class Compare > void partial_sort( ExecutionPolicy&& policy, |
(4) | (seit C++17) |
Ordnet Elemente so an, dass der Bereich [first, middle) die sortierten middle − first kleinsten Elemente im Bereich [first, last) enthält.
Die Reihenfolge von gleichen Elementen muss nicht erhalten bleiben. Die Reihenfolge der verbleibenden Elemente im Bereich [middle, last) ist nicht spezifiziert.
|
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
-
[first,middle)oder[middle,last)ist kein gültiger Bereich.
|
(bis C++11) |
|
(seit C++11) |
Inhalt |
[edit] Parameter
| first, last | - | das Iteratorenpfad, das den zu ordnenden Bereich von Elementen definiert |
| middle | - | der Bereich [first, middle) enthält sortierte Elemente |
| 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. | ||
[edit] Komplexität
Gegeben M als middle - first, N als last - first
[edit] 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.
[edit] Mögliche Implementierung
Siehe auch die Implementierungen in libstdc++ und libc++.
| partial_sort (1) |
|---|
template<typename RandomIt> constexpr //< since C++20 void partial_sort(RandomIt first, RandomIt middle, RandomIt last) { typedef typename std::iterator_traits<RandomIt>::value_type VT; std::partial_sort(first, middle, last, std::less<VT>()); } |
| partial_sort (3) |
namespace impl { template<typename RandomIt, typename Compare> constexpr //< since C++20 void sift_down(RandomIt first, RandomIt last, const Compare& comp) { // sift down element at “first” const auto length = static_cast<std::size_t>(last - first); std::size_t current = 0; std::size_t next = 2; while (next < length) { if (comp(*(first + next), *(first + (next - 1)))) --next; if (!comp(*(first + current), *(first + next))) return; std::iter_swap(first + current, first + next); current = next; next = 2 * current + 2; } --next; if (next < length && comp(*(first + current), *(first + next))) std::iter_swap(first + current, first + next); } template<typename RandomIt, typename Compare> constexpr //< since C++20 void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp) { std::make_heap(first, middle, comp); for (auto i = middle; i != last; ++i) { if (comp(*i, *first)) { std::iter_swap(first, i); sift_down(first, middle, comp); } } } } // namespace impl template<typename RandomIt, typename Compare> constexpr //< since C++20 void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp) { impl::heap_select(first, middle, last, comp); std::sort_heap(first, middle, comp); } |
[edit] Anmerkungen
[edit] Algorithmus
Der verwendete Algorithmus ist typischerweise Heap-Auswahl zur Auswahl der kleinsten Elemente und Heap-Sortierung zur Sortierung der ausgewählten Elemente im Heap aufsteigend.
Zur Auswahl von Elementen wird ein Heap verwendet (siehe Heap). Zum Beispiel wird für operator< als Vergleichsfunktion ein Max-Heap verwendet, um die middle − first kleinsten Elemente auszuwählen.
Heap-Sortierung wird nach der Auswahl verwendet, um die im Bereich [first, middle) ausgewählten Elemente zu sortieren (siehe std::sort_heap).
[edit] Verwendungszweck
std::partial_sort Algorithmen sind dazu gedacht, für *kleine konstante Zahlen* von [first, middle) ausgewählten Elementen verwendet zu werden.
[edit] Beispiel
#include <algorithm> #include <array> #include <functional> #include <iostream> void print(const auto& s, int middle) { for (int a : s) std::cout << a << ' '; std::cout << '\n'; if (middle > 0) { while (middle-- > 0) std::cout << "--"; std::cout << '^'; } else if (middle < 0) { for (auto i = s.size() + middle; --i; std::cout << " ") {} for (std::cout << '^'; middle++ < 0; std::cout << "--") {} } std::cout << '\n'; }; int main() { std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; print(s, 0); std::partial_sort(s.begin(), s.begin() + 3, s.end()); print(s, 3); std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend()); print(s, -4); std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{}); print(s, -5); }
Mögliche Ausgabe
5 7 4 2 8 6 1 9 0 3
0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
^--------
4 3 2 1 0 5 6 7 8 9
^----------[edit] 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 |
|---|---|---|---|
| P0896R4 | C++98 | [first, middle) und [middle, last)mussten keine gültigen Bereiche sein |
das Verhalten ist undefiniert wenn einer davon ungültig war |
[edit] Siehe auch
| Sortiert den gegebenen Bereich teilweise, so dass er durch das gegebene Element partitioniert wird (Funktionstemplate) | |
| Kopiert und sortiert einen Bereich von Elementen teilweise (Funktionstemplate) | |
| Sortiert einen Bereich von Elementen und behält dabei die Reihenfolge zwischen gleichen Elementen bei (Funktionstemplate) | |
| Sortiert einen Bereich aufsteigend (Funktionstemplate) | |
| (C++20) |
Sortiert die ersten N Elemente eines Bereichs (Algorithmus-Funktionsobjekt) |
