std:: set_union

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

Wenn [ first1 , last1 ) m Elemente enthält, die zueinander äquivalent sind, und [ first2 , last2 ) n Elemente enthält, die zu diesen äquivalent sind, dann werden alle m Elemente aus [ first1 , last1 ) in den Ausgabebereich kopiert, wobei die Reihenfolge erhalten bleibt, und anschließend die letzten std:: max ( n - m, 0 ) Elemente aus [ first2 , last2 ) in den Ausgabebereich kopiert, ebenfalls unter Beibehaltung der Reihenfolge.

Wenn der Ausgabebereich sich mit [ first1 , last1 ) oder [ first2 , last2 ) überschneidet, ist das Verhalten undefiniert.

Parameter

Rückgabewert

Iterator hinter das Ende des konstruierten Bereichs.

Komplexität

Gegeben \(\scriptsize N_1\) N 1 als std:: distance ( first1, last1 ) und \(\scriptsize N_2\) N 2 als std:: distance ( first2, last2 ) :

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

• Wenn die Ausführung einer als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
• Wenn der Algorithmus keinen Speicher allokieren kann, wird std::bad_alloc geworfen.

Mögliche Implementierung

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);
}

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)
            // Bereich 2 abgeschlossen, Rest von Bereich 1 einfügen:
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1))
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!comp(*first1, *first2)) // Äquivalent => *first2 muss nicht eingefügt werden.
                ++first2;
            ++first1;
        }
    }
    // Bereich 1 abgeschlossen, Rest von Bereich 2 einfügen:
    return std::copy(first2, last2, d_first);
}

Hinweise

Dieser Algorithmus führt eine ähnliche Aufgabe aus wie std::merge es tut. Beide verarbeiten 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 als äquivalent verglichen werden (siehe Anmerkungen zu LessThanComparable ). Wenn äquivalente Werte n Mal im ersten Bereich und m Mal im zweiten auftraten, würde std::merge alle n + m Vorkommen ausgeben, während std::set_union nur std:: max ( n, m ) ausgeben würde. Also gibt std::merge genau std:: distance ( first1, last1 ) + std:: distance ( first2, last2 ) Werte aus und std::set_union kann weniger erzeugen.

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);
}

1 2 3 4 5 6 7 
1 2 3 4 5 5 5 6 7

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

Siehe auch