std::merge

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2,
                OutputIt d_first );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 merge( ExecutionPolicy&& policy,
                  ForwardIt1 first1, ForwardIt1 last1,
                  ForwardIt2 first2, ForwardIt2 last2,
                  ForwardIt3 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 );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 merge( ExecutionPolicy&& policy,
                  ForwardIt1 first1, ForwardIt1 last1,
                  ForwardIt2 first2, ForwardIt2 last2,
                  ForwardIt3 d_first, Compare comp );

Mischt zwei sortierte Bereiche [first1, last1) und [first2, last2) zu einem sortierten Bereich 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) vor den Elementen aus dem zweiten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) stehen.

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

Parameter

Rückgabewert

Ein Ausgabeiterator, der auf das Element nach dem letzten kopierten Element zeigt.

Komplexität

Gegeben \(\scriptsize N_1\)N1 als std::distance(first1, last1) und \(\scriptsize N_2\)N2 als std::distance(first2, last2):

Ausnahmen

Die Überladungen mit einem Vorlagenparameter namens ExecutionPolicy melden Fehler wie folgt:

• Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jedes andere ExecutionPolicy ist das Verhalten implementationsdefiniert.
• Wenn der Algorithmus keinen Speicher zuweisen kann, wird std::bad_alloc ausgelöst.

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

Anmerkungen

Dieser Algorithmus führt eine ähnliche Aufgabe aus wie std::set_union. Beide verbrauchen zwei sortierte Eingabebereiche und erzeugen eine sortierte Ausgabe mit Elementen aus beiden Eingaben. Der Unterschied zwischen diesen beiden Algorithmen besteht in der Behandlung von Werten aus beiden Eingabebereichen, die äquivalent vergleichen (siehe Anmerkungen zu LessThanComparable). Wenn äquivalente Werte n Mal im ersten Bereich und m Mal im zweiten vorkamen, 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 <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()
{
    // fill the vectors with random numbers
    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("Originally:\nv1: ", v1);
    print("v2: ", v2);
    
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    
    print("After sorting:\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("After merging:\ndst: ", dst);
}

Originally:
v1: 2 6 5 7 4 2 2 6 7 0
v2: 8 3 2 5 0 1 9 6 5 0
After sorting:
v1: 0 2 2 2 4 5 6 6 7 7
v2: 0 0 1 2 3 5 5 6 8 9
After merging:
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