WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

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.

Quellen