std::ranges::merge, std::ranges::merge_result
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, |
(1) | (seit C++20) |
| template< ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, |
(2) | (seit C++20) |
| Hilfstypen |
||
| template< class I1, class I2, class O > using merge_result = ranges::in_in_out_result<I1, I2, O>; |
(3) | (seit C++20) |
Führt zwei *sortierte* Bereiche [[first1, last1) und [first2, last2) zu einem *sortierten* Bereich zusammen, der bei result beginnt.
Eine Sequenz gilt bezüglich des Komparators comp als *sortiert*, 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, std::invoke(comp, std::invoke(proj2, *(it + n)), std::invoke(proj1, *it))) zu false ausgewertet wird.
Das Verhalten ist undefiniert, wenn der Zielbereich mit einem der Eingabebereiche überlappt (die Eingabebereiche dürfen sich überlappen).
Diese Merge-Funktion ist *stabil*, was bedeutet, dass für äquivalente Elemente in den beiden ursprünglichen Bereichen die Elemente aus dem ersten Bereich (in ihrer ursprünglichen Reihenfolge) vor den Elementen aus dem zweiten Bereich (in ihrer ursprünglichen Reihenfolge) stehen.
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
| first1, last1 | - | das Iterator-Sentinel-Paar, das den ersten sortierten Eingabebereich der zu mergenden Elemente definiert |
| first2, last2 | - | das Iterator-Sentinel-Paar, das den zweiten sortierten Eingabebereich der zu mergenden Elemente definiert |
| Ergebnis | - | der Anfang des Ausgabebereichs |
| comp | - | Vergleich, der auf die projizierten Elemente angewendet wird |
| proj1 | - | Projektion, die auf die Elemente im ersten Bereich angewendet wird |
| proj2 | - | Projektion, die auf die Elemente im zweiten Bereich angewendet wird |
[edit] Rückgabewert
{last1, last2, result_last}, wobei result_last das Ende des konstruierten Bereichs ist.
[edit] Komplexität
Höchstens N − 1 Vergleiche und Anwendungen jeder Projektion, wobei N = ranges::distance(first1, last1) + ranges::distance(first2, last12).
[edit] Hinweise
Dieser Algorithmus führt eine ähnliche Aufgabe aus wie ranges::set_union. Beide verbrauchen zwei sortierte Eingabebereiche und erzeugen eine sortierte Ausgabe mit Elementen aus beiden Eingaben. Der Unterschied zwischen diesen beiden Algorithmen liegt im Umgang mit Werten aus beiden Eingabebereichen, die äquivalent verglichen werden (siehe Hinweise zu LessThanComparable). Wenn in dem ersten Bereich n und in dem zweiten Bereich m äquivalente Werte vorkamen, würde ranges::merge alle n + m Vorkommen ausgeben, während ranges::set_union nur max(n, m) Vorkommen ausgeben würde. ranges::merge gibt also genau N Werte aus, während ranges::set_union weniger produzieren kann.
[edit] Mögliche Implementierung
struct merge_fn { template<std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity> requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<I1, I2, O> operator()(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { for (; !(first1 == last1 or first2 == last2); ++result) { if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1))) *result = *first2, ++first2; else *result = *first1, ++first1; } auto ret1{ranges::copy(std::move(first1), std::move(last1), std::move(result))}; auto ret2{ranges::copy(std::move(first2), std::move(last2), std::move(ret1.out))}; return {std::move(ret1.in), std::move(ret2.in), std::move(ret2.out)}; } template<ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity> requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O> operator()(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { return (*this)(ranges::begin(r1), ranges::end(r1), ranges::begin(r2), ranges::end(r2), std::move(result), std::move(comp), std::move(proj1), std::move(proj2)); } }; inline constexpr merge_fn merge {}; |
[edit] Beispiel
#include <algorithm> #include <iostream> #include <iterator> #include <vector> void print(const auto& in1, const auto& in2, auto first, auto last) { std::cout << "{ "; for (const auto& e : in1) std::cout << e << ' '; std::cout << "} +\n{ "; for (const auto& e : in2) std::cout << e << ' '; std::cout << "} =\n{ "; while (!(first == last)) std::cout << *first++ << ' '; std::cout << "}\n\n"; } int main() { std::vector<int> in1, in2, out; in1 = {1, 2, 3, 4, 5}; in2 = {3, 4, 5, 6, 7}; out.resize(in1.size() + in2.size()); const auto ret = std::ranges::merge(in1, in2, out.begin()); print(in1, in2, out.begin(), ret.out); in1 = {1, 2, 3, 4, 5, 5, 5}; in2 = {3, 4, 5, 6, 7}; out.clear(); out.reserve(in1.size() + in2.size()); std::ranges::merge(in1, in2, std::back_inserter(out)); print(in1, in2, out.cbegin(), out.cend()); }
Ausgabe
{ 1 2 3 4 5 } +
{ 3 4 5 6 7 } =
{ 1 2 3 3 4 4 5 5 6 7 }
{ 1 2 3 4 5 5 5 } +
{ 3 4 5 6 7 } =
{ 1 2 3 3 4 4 5 5 5 5 6 7 }[edit] Siehe auch
| (C++20) |
Führt zwei sortierte Bereiche an Ort und Stelle zusammen (Algorithmus-Funktionsobjekt) |
| (C++20) |
Prüft, ob ein Bereich aufsteigend sortiert ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Berechnet die Vereinigung zweier Mengen (Algorithmus-Funktionsobjekt) |
| (C++20) |
Sortiert einen Bereich aufsteigend (Algorithmus-Funktionsobjekt) |
| (C++20) |
Sortiert einen Bereich von Elementen und behält dabei die Reihenfolge zwischen gleichen Elementen bei (Algorithmus-Funktionsobjekt) |
| Führt zwei sortierte Bereiche zusammen (Funktionstemplate) |
