std::ranges::inplace_merge
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
template< std::bidirectional_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > |
(1) | (seit C++20) (constexpr seit C++26) |
template< ranges::bidirectional_range R, class Comp = ranges::less, class Proj = std::identity > |
(2) | (seit C++20) (constexpr seit C++26) |
Führt die beiden aufeinanderfolgenden *sortierten* Bereiche [first, middle) und [middle, last) zu einem *sortierten* Bereich [first, last) zusammen.
Eine Sequenz gilt als *sortiert* bezüglich des Vergleichers comp und der Projektion proj, wenn für jeden Iterator it, der auf die Sequenz zeigt, und jede nicht-negative ganze Zahl n, so dass it + n ein gültiger Iterator ist, der auf ein Element der Sequenz zeigt, gilt: std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))) zu false ausgewertet wird.
Diese Merge-Funktion ist *stabil*, was bedeutet, dass für äquivalente Elemente in den ursprünglichen beiden Bereichen die Elemente aus dem ersten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) den Elementen aus dem zweiten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) vorausgehen.
r als Bereich, so 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 | - | der Anfang des ersten sortierten Bereichs |
| middle | - | das Ende des ersten Bereichs und der Anfang des zweiten Bereichs |
| last | - | das Ende des zweiten sortierten Bereichs |
| r | - | der Bereich der Elemente, die inplace zusammengeführt werden sollen |
| comp | - | Vergleich, der auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente im Bereich angewendet werden soll |
[edit] Rückgabewert
Ein Iterator, der gleich last ist.
[edit] Komplexität
Genau N − 1 Vergleiche, falls zusätzlicher Speicher verfügbar ist, wobei N = ranges::distance(first, last). Andernfalls 𝓞(N•log(N)) Vergleiche. Zusätzlich doppelt so viele Projektionen wie Vergleiche in beiden Fällen.
[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 zeigt nur den langsameren Algorithmus, der verwendet wird, wenn kein zusätzlicher Speicher verfügbar ist. Siehe auch die Implementierung in MSVC STL und libstdc++.
struct inplace_merge_fn { template<std::bidirectional_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<I, Comp, Proj> constexpr I operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const { I last_it = ranges::next(middle, last); inplace_merge_slow(first, middle, last_it, ranges::distance(first, middle), ranges::distance(middle, last_it), std::ref(comp), std::ref(proj)); return last_it; } template<ranges::bidirectional_range R, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), std::move(middle), ranges::end(r), std::move(comp), std::move(proj)); } private: template<class I, class Comp, class Proj> static constexpr void inplace_merge_slow(I first, I middle, I last, std::iter_difference_t<I> n1, std::iter_difference_t<I> n2, Comp comp, Proj proj) { if (n1 == 0 || n2 == 0) return; if (n1 + n2 == 2 && comp(proj(*middle), proj(*first))) { ranges::iter_swap(first, middle); return; } I cut1 = first, cut2 = middle; std::iter_difference_t<I> d1{}, d2{}; if (n1 > n2) { d1 = n1 / 2; ranges::advance(cut1, d1); cut2 = ranges::lower_bound(middle, last, *cut1, std::ref(comp), std::ref(proj)); d2 = ranges::distance(middle, cut2); } else { d2 = n2 / 2; ranges::advance(cut2, d2); cut1 = ranges::upper_bound(first, middle, *cut2, std::ref(comp), std::ref(proj)); d1 = ranges::distance(first, cut1); } I new_middle = ranges::rotate(cut1, middle, cut2); inplace_merge_slow(first, cut1, new_middle, d1, d2, std::ref(comp), std::ref(proj)); inplace_merge_slow(new_middle, cut2, last, n1 - d1, n2 - d2, std::ref(comp), std::ref(proj)); } }; inline constexpr inplace_merge_fn inplace_merge {}; |
[edit] Beispiel
#include <algorithm> #include <complex> #include <functional> #include <iostream> #include <iterator> #include <vector> void print(auto const& v, auto const& rem, int middle = -1) { for (int i{}; auto n : v) std::cout << (i++ == middle ? "│ " : "") << n << ' '; std::cout << rem << '\n'; } template<std::random_access_iterator I, std::sentinel_for<I> S> requires std::sortable<I> void merge_sort(I first, S last) { if (last - first > 1) { I middle{first + (last - first) / 2}; merge_sort(first, middle); merge_sort(middle, last); std::ranges::inplace_merge(first, middle, last); } } int main() { // custom merge-sort demo std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3}; print(v, ": before sort"); merge_sort(v.begin(), v.end()); print(v, ": after sort\n"); // merging with comparison function object and projection using CI = std::complex<int>; std::vector<CI> r{{0,1}, {0,2}, {0,3}, {1,1}, {1,2}}; const auto middle{std::ranges::next(r.begin(), 3)}; auto comp{std::ranges::less{}}; auto proj{[](CI z) { return z.imag(); }}; print(r, ": before merge", middle - r.begin()); std::ranges::inplace_merge(r, middle, comp, proj); print(r, ": after merge"); }
Ausgabe
8 2 0 4 9 8 1 7 3 : before sort 0 1 2 3 4 7 8 8 9 : after sort (0,1) (0,2) (0,3) │ (1,1) (1,2) : before merge (0,1) (1,1) (0,2) (1,2) (0,3) : after merge
[edit] Siehe auch
| (C++20) |
Führt zwei sortierte Bereiche zusammen (Algorithmus-Funktionsobjekt) |
| (C++20) |
Berechnet die Vereinigung zweier Mengen (Algorithmus-Funktionsobjekt) |
| (C++20) |
Prüft, ob ein Bereich aufsteigend sortiert ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Sortiert einen Bereich aufsteigend (Algorithmus-Funktionsobjekt) |
| Führt zwei sortierte Bereiche an Ort und Stelle zusammen (Funktionstemplate) |
