std::ranges::partition
Von cppreference.com
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| template< std::permutable I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_unary_predicate<std::projected<I, Proj>> Pred > |
(1) | (seit C++20) |
| template< ranges::forward_range R, class Proj = std::identity, std::indirect_unary_predicate< |
(2) | (seit C++20) |
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, für die das Prädikat pred false zurückgibt, vorangeht. Die relative Reihenfolge der Elemente wird nicht beibehalten.2) Dasselbe wie (1), aber verwendet r als Quellbereich, 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 |
[bearbeiten] 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 |
[bearbeiten] Rückgabewert
Ein Teilbereich, der mit einem Iterator zum ersten Element der zweiten Gruppe beginnt und mit einem Iterator endet, der gleich last ist. (2) gibt std::ranges::dangling zurück, wenn r ein rvalue eines Typs ist, der kein borrowed_range ist.
[bearbeiten] Komplexität
Gegeben N = ranges::distance(first, last), genau N Anwendungen des Prädikats und der Projektion. Höchstens N / 2 Vertauschungen, wenn I ranges::bidirectional_iterator modelliert, und höchstens N Vertauschungen andernfalls.
[bearbeiten] Mögliche Implementierung
struct partition_fn { template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_unary_predicate<std::projected<I, Proj>> Pred> constexpr ranges::subrange<I> operator()(I first, S last, Pred pred, Proj proj = {}) const { first = ranges::find_if_not(first, last, std::ref(pred), std::ref(proj)); if (first == last) return {first, first}; for (auto i = ranges::next(first); i != last; ++i) { if (std::invoke(pred, std::invoke(proj, *i))) { ranges::iter_swap(i, first); ++first; } } return {std::move(first), std::move(last)}; } template<ranges::forward_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::ref(pred), std::ref(proj)); } }; inline constexpr partition_fn partition; |
[bearbeiten] Beispiel
Führen Sie diesen Code aus
#include <algorithm> #include <forward_list> #include <functional> #include <iostream> #include <iterator> #include <ranges> #include <vector> namespace ranges = std::ranges; template<class I, std::sentinel_for<I> S, class Cmp = ranges::less> requires std::sortable<I, Cmp> void quicksort(I first, S last, Cmp cmp = Cmp {}) { using reference = std::iter_reference_t<I>; if (first == last) return; auto size = ranges::distance(first, last); auto pivot = ranges::next(first, size - 1); ranges::iter_swap(pivot, ranges::next(first, size / 2)); auto tail = ranges::partition(first, pivot, [=](reference em) { return std::invoke(cmp, em, *pivot); // em < pivot }); ranges::iter_swap(pivot, tail.begin()); quicksort(first, tail.begin(), std::ref(cmp)); quicksort(ranges::next(tail.begin()), last, std::ref(cmp)); } int main() { std::ostream_iterator<int> cout {std::cout, " "}; std::vector<int> v {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; std::cout << "Original vector: \t"; ranges::copy(v, cout); auto tail = ranges::partition(v, [](int i) { return i % 2 == 0; }); std::cout << "\nPartitioned vector: \t"; ranges::copy(ranges::begin(v), ranges::begin(tail), cout); std::cout << "│ "; ranges::copy(tail, cout); std::forward_list<int> fl {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92}; std::cout << "\nUnsorted list: \t\t"; ranges::copy(fl, cout); quicksort(ranges::begin(fl), ranges::end(fl), ranges::greater {}); std::cout << "\nQuick-sorted list: \t"; ranges::copy(fl, cout); std::cout << '\n'; }
Mögliche Ausgabe
Original vector: 0 1 2 3 4 5 6 7 8 9 Partitioned vector: 0 8 2 6 4 │ 5 3 7 1 9 Unsorted list: 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 Quick-sorted list: 92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8
[bearbeiten] Siehe auch
| (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) |
| (C++20) |
Teilt Elemente in zwei Gruppen auf und behält dabei ihre relative Reihenfolge bei (Algorithmus-Funktionsobjekt) |
| Teilt einen Bereich von Elementen in zwei Gruppen auf (Funktionstemplate) |
