std:: merge

Führt zwei sortierte Bereiche [ first1 , last1 ) und [ first2 , last2 ) in einem sortierten Bereich zusammen, beginnend bei d_first .

Diese Merge-Funktion ist stabil, was bedeutet, dass für äquivalente Elemente in den beiden ursprünglichen Bereichen die Elemente aus dem ersten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) den Elementen aus dem zweiten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) vorangehen.

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

Parameter

Rückgabewert

Ein Ausgabeiterator für das Element nach dem letzten kopierten Element.

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 allozieren kann, wird std::bad_alloc geworfen.

Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ und libc++ .

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(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;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1))
        {
            *d_first = *first2;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

`- und ``-Tags wurde gemäß den Anforderungen nicht übersetzt. Die Übersetzung beschränkt sich ausschließlich auf die deutschen Linkbeschriftungen "merge (1)" und "merge (3)", die als Teil der Tabellenüberschriften beibehalten wurden, da sie Funktionsbezeichnungen darstellen und gemäß den Vorgaben nicht übersetzt werden sollten.

Hinweise

Dieser Algorithmus führt eine ähnliche Aufgabe aus wie std:: set_union . 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 Hinweise zu LessThanComparable ). Wenn äquivalente Werte n -mal im ersten Bereich und m -mal im zweiten Bereich auftreten, würde std::merge alle n + m Vorkommen ausgeben, während std::set_union nur std:: max ( n, m ) Vorkommen ausgibt. Daher gibt std::merge exakt std:: distance ( first1, last1 ) + std:: distance ( first2, last2 ) Werte aus, während std::set_union möglicherweise weniger erzeugt.

Beispiel

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
auto print = [](const auto rem, const auto& v)
{
    std::cout << rem;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
};
int main()
{
    // Vektoren mit Zufallszahlen füllen
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<> dis(0, 9);
    std::vector<int> v1(10), v2(10);
    std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));
    std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));
    print("Ursprünglich:\nv1: ", v1);
    print("v2: ", v2);
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    print("Nach Sortierung:\nv1: ", v1);
    print("v2: ", v2);
    // merge
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
    print("Nach Zusammenführung:\ndst: ", dst);
}

Ursprünglich:
v1: 2 6 5 7 4 2 2 6 7 0
v2: 8 3 2 5 0 1 9 6 5 0
Nach Sortierung:
v1: 0 2 2 2 4 5 6 6 7 7
v2: 0 0 1 2 3 5 5 6 8 9
Nach Zusammenführung:
dst: 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

Fehlerberichte

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

Siehe auch