std::set_union
| Definiert in Header <algorithm> |
||
template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_union( InputIt1 first1, InputIt1 last1, |
(1) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > |
(2) | (seit C++17) |
template< class InputIt1, class InputIt2, class OutputIt, class Compare > |
(3) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, |
(4) | (seit C++17) |
Erzeugt eine sortierte Vereinigung, die bei d_first beginnt und aus der Menge der Elemente besteht, die in einem oder beiden sortierten Bereichen [first1, last1) und [first2, last2) vorhanden sind.
Wenn [first1, last1) m Elemente enthält, die untereinander äquivalent sind, und [first2, last2) n Elemente enthält, die mit diesen äquivalent sind, dann werden alle m Elemente aus [first1, last1) in den Ausgabebereich kopiert, wobei die Reihenfolge beibehalten wird, und dann werden die letzten std::max(n - m, 0) Elemente aus [first2, last2) in den Ausgabebereich kopiert, ebenfalls unter Beibehaltung der Reihenfolge.
[first1, last1) oder [first2, last2) nicht sortiert ist bezüglich operator<(until C++20)std::less{}(since C++20), ist das Verhalten undefiniert.[first1, last1) oder [first2, last2) nicht sortiert ist bezüglich comp, ist das Verhalten undefiniert.|
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 sich der Ausgabebereich mit [first1, last1) oder [first2, last2) überschneidet, ist das Verhalten undefiniert.
Inhalt |
[edit] Parameter
| first1, last1 | - | das Iterator-Paar, das den ersten sortierten Eingabebereich von Elementen definiert bereich |
| first2, last2 | - | das Iterator-Paar, das den zweiten sortierten Eingabebereich von Elementen definiert bereich |
| d_first | - | der Anfang des Ausgabebereichs |
| 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 | ||
-InputIt1, InputIt2 müssen die Anforderungen an LegacyInputIterator erfüllen. | ||
-ForwardIt1, ForwardIt2, ForwardIt3 müssen die Anforderungen von LegacyForwardIterator erfüllen. | ||
-OutputIt muss die Anforderungen an LegacyOutputIterator erfüllen. | ||
-Compare muss die Anforderungen an Compare erfüllen. | ||
[edit] Rückgabewert
Iterator hinter das Ende des erstellten Bereichs.
[edit] Komplexität
Gegeben N1 als std::distance(first1, last1) und N2 als std::distance(first2, last2)
[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
| set_union (1) |
|---|
template<class InputIt1, class InputIt2, class OutputIt> OutputIt set_union(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first) { for (; first1 != last1; ++d_first) { if (first2 == last2) return std::copy(first1, last1, d_first); if (*first2 < *first1) *d_first = *first2++; else { *d_first = *first1; if (!(*first1 < *first2)) ++first2; ++first1; } } return std::copy(first2, last2, d_first); } |
| set_union (3) |
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt set_union(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp) { for (; first1 != last1; ++d_first) { if (first2 == last2) // Finished range 2, include the rest of range 1: return std::copy(first1, last1, d_first); if (comp(*first2, *first1)) *d_first = *first2++; else { *d_first = *first1; if (!comp(*first1, *first2)) // Equivalent => don't need to include *first2. ++first2; ++first1; } } // Finished range 1, include the rest of range 2: return std::copy(first2, last2, d_first); } |
[edit] Hinweise
Dieser Algorithmus erfüllt eine ähnliche Aufgabe wie std::merge. 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 n äquivalente Werte im ersten Bereich und m äquivalente Werte im zweiten Bereich auftreten, würde std::merge alle n + m Vorkommen ausgeben, während `std::set_union` nur std::max(n, m) Ausgaben erzeugen würde. `std::merge` gibt also genau std::distance(first1, last1) + std::distance(first2, last2) Werte aus und `std::set_union` kann weniger erzeugen.
[edit] Beispiel
#include <algorithm> #include <iostream> #include <iterator> #include <vector> void println(const std::vector<int>& v) { for (int i : v) std::cout << i << ' '; std::cout << '\n'; } int main() { std::vector<int> v1, v2, dest; v1 = {1, 2, 3, 4, 5}; v2 = {3, 4, 5, 6, 7}; std::set_union(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend(), std::back_inserter(dest)); println(dest); dest.clear(); v1 = {1, 2, 3, 4, 5, 5, 5}; v2 = {3, 4, 5, 6, 7}; std::set_union(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend(), std::back_inserter(dest)); println(dest); }
Ausgabe
1 2 3 4 5 6 7 1 2 3 4 5 5 5 6 7
[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 |
|---|---|---|---|
| LWG 291 | C++98 | es war nicht spezifiziert, wie äquivalente Elemente in den Eingabebereichen behandelt werden sollen | spezifiziert |
[edit] Siehe auch
| Gibt true zurück, wenn eine Sequenz eine Untersequenz einer anderen ist (Funktionstemplate) | |
| Führt zwei sortierte Bereiche zusammen (Funktionstemplate) | |
| Berechnet die Differenz zwischen zwei Mengen (Funktionstemplate) | |
| Berechnet den Schnitt zweier Mengen (Funktionstemplate) | |
| Berechnet die symmetrische Differenz zwischen zwei Mengen (Funktionstemplate) | |
| (C++20) |
Berechnet die Vereinigung zweier Mengen (Algorithmus-Funktionsobjekt) |
