std::ranges::stable_partition
Von cppreference.com
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
template< std::bidirectional_iterator I, std::sentinel_for<I> S, class Proj = std::identity, |
(1) | (seit C++20) (constexpr seit C++26) |
template< ranges::bidirectional_range R, class Proj = std::identity, std::indirect_unary_predicate< |
(2) | (seit C++20) (constexpr seit C++26) |
1) Ordnet die Elemente im Bereich
[first, last) so um, dass die Projektion proj aller Elemente, für die das Prädikat pred true zurückgibt, der Projektion proj von Elementen vorangeht, für die das Prädikat pred false zurückgibt. Der Algorithmus ist stabil, d.h. die relative Reihenfolge der Elemente wird beibehalten.2) Dasselbe wie (1), verwendet aber r als Bereich, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.
Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.
- Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
- Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
- Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.
Inhalt |
[edit] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der neu anzuordnenden Elemente definiert |
| r | - | der Bereich der neu anzuordnenden Elemente |
| pred | - | Prädikat, das auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[edit] Rückgabewert
1) Ein Objekt, das gleich {pivot, last} ist, wobei
pivot ein Iterator zum ersten Element der zweiten Gruppe ist.2) Dasselbe wie (1), wenn r ein lvalue ist oder vom Typ
borrowed_range. Andernfalls wird std::ranges::dangling zurückgegeben.[edit] Komplexität
Bei N = ranges::distance(first, last) beträgt die Komplexität im schlimmsten Fall N·log(N) Swaps und nur 𝓞(N) Swaps, wenn ein zusätzlicher Speicherpuffer verwendet wird. Genau N Anwendungen des Prädikats pred und der Projektion proj.
[edit] Anmerkungen
Diese Funktion versucht, einen temporären Puffer zu allokieren. Schlägt die Allokation fehl, wird der weniger effiziente Algorithmus gewählt.
| Feature-Test-Makro | Wert | Std | Feature |
|---|---|---|---|
__cpp_lib_constexpr_algorithms |
202306L |
(C++26) | constexpr stabile Sortierung |
[edit] Mögliche Implementierung
Diese Implementierung verwendet keinen zusätzlichen Speicherpuffer und kann daher weniger effizient sein. Siehe auch die Implementierung in MSVC STL und libstdc++.
struct stable_partition_fn { template<std::bidirectional_iterator I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_unary_predicate<std::projected<I, Proj>> Pred> requires std::permutable<I> constexpr ranges::subrange<I> operator()(I first, S last, Pred pred, Proj proj = {}) const { first = ranges::find_if_not(first, last, pred, proj); I mid = first; while (mid != last) { mid = ranges::find_if(mid, last, pred, proj); if (mid == last) break; I last2 = ranges::find_if_not(mid, last, pred, proj); ranges::rotate(first, mid, last2); first = ranges::next(first, ranges::distance(mid, last2)); mid = last2; } return {std::move(first), std::move(mid)}; } template<ranges::bidirectional_range R, class Proj = std::identity, std::indirect_unary_predicate< std::projected<ranges::iterator_t<R>, Proj>> Pred> requires std::permutable<ranges::iterator_t<R>> constexpr ranges::borrowed_subrange_t<R> operator()(R&& r, Pred pred, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(pred), std::move(proj)); } }; inline constexpr stable_partition_fn stable_partition {}; |
[edit] Beispiel
Führen Sie diesen Code aus
#include <algorithm> #include <iostream> #include <iterator> #include <vector> namespace rng = std::ranges; template<std::permutable I, std::sentinel_for<I> S> constexpr void stable_sort(I first, S last) { if (first == last) return; auto pivot = *rng::next(first, rng::distance(first, last) / 2, last); auto left = [pivot](const auto& em) { return em < pivot; }; auto tail1 = rng::stable_partition(first, last, left); auto right = [pivot](const auto& em) { return !(pivot < em); }; auto tail2 = rng::stable_partition(tail1, right); stable_sort(first, tail1.begin()); stable_sort(tail2.begin(), tail2.end()); } void print(const auto rem, auto first, auto last, bool end = true) { std::cout << rem; for (; first != last; ++first) std::cout << *first << ' '; std::cout << (end ? "\n" : ""); } int main() { const auto original = {9, 6, 5, 2, 3, 1, 7, 8}; std::vector<int> vi {}; auto even = [](int x) { return 0 == (x % 2); }; print("Original vector:\t", original.begin(), original.end(), "\n"); vi = original; const auto ret1 = rng::stable_partition(vi, even); print("Stable partitioned:\t", vi.begin(), ret1.begin(), 0); print("│ ", ret1.begin(), ret1.end()); vi = original; const auto ret2 = rng::partition(vi, even); print("Partitioned:\t\t", vi.begin(), ret2.begin(), 0); print("│ ", ret2.begin(), ret2.end()); vi = {16, 30, 44, 30, 15, 24, 10, 18, 12, 35}; print("Unsorted vector: ", vi.begin(), vi.end()); stable_sort(rng::begin(vi), rng::end(vi)); print("Sorted vector: ", vi.begin(), vi.end()); }
Mögliche Ausgabe
Original vector: 9 6 5 2 3 1 7 8 Stable partitioned: 6 2 8 │ 9 5 3 1 7 Partitioned: 8 6 2 │ 5 3 1 7 9 Unsorted vector: 16 30 44 30 15 24 10 18 12 35 Sorted vector: 10 12 15 16 18 24 30 30 35 44
[edit] Siehe auch
| (C++20) |
Teilt einen Bereich von Elementen in zwei Gruppen auf (Algorithmus-Funktionsobjekt) |
| (C++20) |
Kopiert einen Bereich und teilt die Elemente in zwei Gruppen auf (Algorithmus-Funktionsobjekt) |
| (C++20) |
Stellt fest, ob der Bereich durch das gegebene Prädikat partitioniert ist (Algorithmus-Funktionsobjekt) |
| Teilt Elemente in zwei Gruppen auf und behält dabei ihre relative Reihenfolge bei (Funktionstemplate) |
