CKTIS / C++
std::set_union — Vereinigung sortierter Bereiche
std::set_union schreibt die sortierte Vereinigung zweier sortierter Bereiche. Die maximale Anzahl gleichwertiger Elemente aus beiden Eingaben bleibt erhalten; das Ergebnis enthält daher nicht unbedingt nur eindeutige Werte.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::set_union(first1, last1, first2, last2, result);
std::set_union(first1, last1, first2, last2, result, comp);std::set_union aus <algorithm> kopiert die Vereinigung der Bereiche [first1, last1) und [first2, last2) zum Ausgabeiterator result. Es sind keine std::set-Container erforderlich. Dieser Eintrag behandelt die gewöhnlichen Iterator-Überladungen ohne Ausführungsrichtlinie; sie geben einen Iterator hinter dem zuletzt geschriebenen Element zurück.
Beide Eingaben müssen nach derselben strikten schwachen Ordnung sortiert sein: standardmäßig nach std::less{} oder nach dem übergebenen comp. Gleichwertigkeit bedeutet !comp(a, b) && !comp(b, a), nicht unbedingt a == b. Werden die Anforderungen an Sortierung oder Nichtüberlappung verletzt, ist das Verhalten undefiniert.
Kommt eine Äquivalenzklasse im ersten Bereich m-mal und im zweiten n-mal vor, enthält das Ergebnis max(m, n) Elemente: alle m aus dem ersten Bereich, gefolgt von den letzten max(n - m, 0) aus dem zweiten, jeweils in ihrer Reihenfolge. Dies ist eine Multimengenvereinigung, keine vollständige Entfernung von Duplikaten.
Der Ausgabebereich darf sich mit keinem Eingabebereich überschneiden und muss alle Schreibvorgänge unterstützen. std::back_inserter(result) vergrößert einen separaten Vektor; reserve() allein erzeugt keine Elemente, die über begin() beschrieben werden können. Die Komplexität beträgt bei Eingabelängen N1 und N2 O(N1 + N2). Das Beispiel zeigt, dass Duplikate erhalten bleiben.
Beispiele
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
const std::vector<int> a{1, 2, 2, 4};
const std::vector<int> b{2, 3, 3, 4};
std::vector<int> result;
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
const char* separator = "";
for (int value : result) {
std::cout << separator << value;
separator = " ";
}
std::cout << '\n';
}
Ergebnis
1 2 2 3 3 4
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.