std::ranges::set_union, std::ranges::set_union_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, 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 set_union_result<I1, I2, O> set_union( I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(seit C++20)
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 set_union_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O> set_union( R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(seit C++20)
Hilfstypen
template< class I1, class I2, class O > using set_union_result = ranges::in_in_out_result<I1, I2, O>;	(3)	(seit C++20)

Konstruiert eine sortierte Vereinigung, beginnend bei result, bestehend aus der Menge der Elemente, die in einem oder beiden sortierten Eingabebereichen [first1, last1) und [first2, last2) vorhanden sind.

Wenn ein Element m Mal in [first1, last1) und n Mal in [first2, last2) gefunden wird, dann werden alle m Elemente aus [first1, last1) unter Beibehaltung der Reihenfolge nach result kopiert, und dann werden genau max(n - m, 0) Elemente aus [first2, last2) ebenfalls unter Beibehaltung der Reihenfolge nach result kopiert.

Das Verhalten ist undefiniert, wenn

die Eingabebereiche sind nicht sortiert bezüglich comp und proj1 bzw. proj2, oder
der Ergebnisbereich überschneidet sich mit einem der Eingabebereiche.

1) Elemente werden mit der gegebenen binären Vergleichsfunktion comp verglichen.

2) Gleiches wie (1), verwendet aber r1 als erstes und r2 als zweites Gebiet, als ob ranges::begin(r1) als first1, ranges::end(r1) als last1, ranges::begin(r2) als first2 und ranges::end(r2) als last2 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.

[edit] Parameter

first1, last1	-	das Iterator-Sentinel-Paar, das den ersten sortierten Eingabebereich von Elementen definiert
first2, last2	-	das Iterator-Sentinel-Paar, das den zweiten sortierten Eingabebereich von Elementen definiert
r1	-	der erste sortierte Eingabebereich
r2	-	der zweite sortierte Eingabebereich
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 $\scriptsize 2\cdot(N_1+N_2)-1$ $2\cdot(N 1 +N 2)-1$ Vergleiche und Anwendungen jeder Projektion, wobei $\scriptsize N_1$ $N 1$ und $\scriptsize N_2$ $N 2$ ranges::distance(first1, last1) und ranges::distance(first2, last2) sind.

[edit] Hinweise

Dieser Algorithmus führt eine ähnliche Aufgabe aus wie ranges::merge. Beide verbrauchen zwei sortierte Eingabebereiche und erzeugen eine sortierte Ausgabe mit Elementen aus beiden Eingaben. Der Unterschied zwischen diesen beiden Algorithmen liegt in der Handhabung von Werten aus beiden Eingabebereichen, die als äquivalent verglichen werden (siehe Hinweise zu LessThanComparable). Wenn irgendwelche äquivalenten Werte n Mal im ersten Bereich und m Mal im zweiten Bereich vorkommen, würde ranges::merge alle n+m Vorkommen ausgeben, während ranges::set_union nur std::max(n, m) davon ausgibt. Daher gibt ranges::merge genau $\scriptsize (N_1+N_2)$ $(N 1 +N 2)$ Werte aus und ranges::set_union kann weniger produzieren.

[edit] Mögliche Implementierung

struct set_union_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::set_union_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(proj1, *first1), 
                                  std::invoke(proj2, *first2)))
            {
                *result = *first1;
                ++first1;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
            {
                *result = *first2;
                ++first2;
            }
            else
            {
                *result = *first1;
                ++first1;
                ++first2;
            }
        }
        auto res1 = ranges::copy(std::move(first1), std::move(last1), std::move(result));
        auto res2 = ranges::copy(std::move(first2), std::move(last2), std::move(res1.out));
        return {std::move(res1.in), std::move(res2.in), std::move(res2.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::set_union_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 set_union_fn set_union {};

[edit] Beispiel

Führen Sie diesen Code aus

#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 << "} ∪ { ";
    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::set_union(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::set_union(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 4 5 6 7 }
 
{ 1 2 3 4 5 5 5 } ∪ { 3 4 5 6 7 } =
{ 1 2 3 4 5 5 5 6 7 }

[edit] Siehe auch

ranges::set_difference (C++20)	Berechnet die Differenz zwischen zwei Mengen (Algorithmus-Funktionsobjekt)[edit]
ranges::set_intersection (C++20)	Berechnet den Schnitt zweier Mengen (Algorithmus-Funktionsobjekt)[edit]
ranges::set_symmetric_difference (C++20)	Berechnet die symmetrische Differenz zwischen zwei Mengen (Algorithmus-Funktionsobjekt)[edit]
ranges::merge (C++20)	Führt zwei sortierte Bereiche zusammen (Algorithmus-Funktionsobjekt)[edit]
ranges::includes (C++20)	Gibt true zurück, wenn eine Sequenz eine Untersequenz einer anderen ist (Algorithmus-Funktionsobjekt)[edit]
set_union	Berechnet die Vereinigung zweier Mengen (Funktionstemplate) [edit]

Compiler-Unterstützung
Freestanding und gehostet
Sprache
Standardbibliothek
Header der Standardbibliothek
Benannte Anforderungen
Feature-Test-Makros (C++20)
Bibliothek für Sprachunterstützung
Konzepte-Bibliothek (C++20)
Diagnostik-Bibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogramme-Bibliothek
Container-Bibliothek
Iterator-Bibliothek
Ranges-Bibliothek (C++20)
Algorithmen-Bibliothek
Bibliothek für Zeichenketten
Textverarbeitungsbibliothek
Numerik-Bibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabe-Bibliothek
Dateisystembibliothek (C++17)
Unterstützung für nebenläufige Programmierung (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolverzeichnis
Externe Bibliotheken

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen