std::merge

Definiert in Header `<algorithm>`
template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );	(1)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );	(2)	(seit C++17)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );	(3)	(constexpr seit C++20)
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 );	(4)	(seit C++17)

Führt zwei sortierte Bereiche [first1, last1) und [first2, last2) zu einem einzigen sortierten Bereich zusammen, der bei d_first beginnt.

1) Wenn [first1, last1) oder [first2, last2) nicht sortiert ist in Bezug auf operator<(bis C++20)std::less{}(seit C++20), ist das Verhalten undefiniert.

3) Wenn [first1, last1) oder [first2, last2) nicht sortiert ist bezüglich comp, ist das Verhalten undefiniert.

2,4) Dasselbe wie (1,3), aber ausgeführt gemäß policy.

Diese Überladungen nehmen an der Auflösungsauflösung teil, nur wenn alle folgenden Bedingungen erfüllt sind

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true.	(bis C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true.	(seit C++20)

Diese Merge-Funktion ist stabil, was bedeutet, dass für äquivalente Elemente in den ursprünglichen beiden 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 sich der Ausgabebereich mit [first1, last1) oder [first2, last2) überschneidet, ist das Verhalten undefiniert.

[edit] Parameter

first1, last1	-	das Iteratorenpaar, das den ersten zu mergenden Bereich von Elementen definiert
first2, last2	-	das Iteratorenpaar, das den zweiten zu mergenden Bereich von Elementen definiert
d_first	-	der Anfang des Zielbereichs
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
comp	-	Vergleichsfunktions-Objekt (d.h. ein Objekt, das die Anforderungen an Compare erfüllt), das true zurückgibt, wenn das erste Argument weniger (d.h. vorher) als das zweite geordnet ist. Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein bool cmp(const Type1& a, const Type2& b); Obwohl die Signatur nicht unbedingt const& haben muss, darf die Funktion die übergebenen Objekte nicht verändern und muss in der Lage sein, alle Werte vom Typ (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie zu akzeptieren (daher ist `Type1&` nicht erlaubt, ebenso wenig `Type1`, es sei denn, für `Type1` ist ein Move äquivalent zu einem Kopieren(since C++11)). Die Typen Type1 und Type2 müssen so beschaffen sein, dass Objekte der Typen InputIt1 und InputIt2 dereferenziert und dann implizit in sowohl Type1 als auch Type2 konvertiert werden können.
Typanforderungen
- `InputIt1, InputIt2` müssen die Anforderungen an LegacyInputIterator erfüllen.
- `ForwardIt1, ForwardIt2, ForwardIt3` müssen die Anforderungen von LegacyForwardIterator erfüllen.
- `OutputIt` muss die Anforderungen an LegacyOutputIterator erfüllen.
- `Compare` muss die Anforderungen an Compare erfüllen.

[edit] Rückgabewert

Ein Ausgabiterator auf das Element nach dem letzten kopierten Element.

[edit] Komplexität

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

1) Maximal

N 1 +N 2 -1

Vergleiche mit operator<(bis C++20)std::less{}(seit C++20).

2)

O(N 1 +N 2)

Vergleiche mit operator<(bis C++20)std::less{}(seit C++20).

3) Maximal

N 1 +N 2 -1

Anwendungen der Vergleichsfunktion comp.

4)

O(N 1 +N 2)

Anwendungen der Vergleichsfunktion comp.

[edit] Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy berichten 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 jede andere ExecutionPolicy ist das Verhalten implementierungsabhängig.
Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.

[edit] Mögliche Implementierung

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

merge (1)

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

merge (3)

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

[edit] Hinweise

Dieser Algorithmus führt eine ähnliche Aufgabe aus wie std::set_union. Beide verbrauchen zwei sortierte Eingabebereiche und erzeugen einen sortierten Ausgabebereich mit Elementen aus beiden Eingaben. Der Unterschied zwischen diesen beiden Algorithmen liegt im Umgang mit Werten aus beiden Eingabebereichen, die äquivalent vergleichen werden (siehe Hinweise zu LessThanComparable). Wenn äquivalente Werte n Mal im ersten Bereich und m Mal im zweiten Bereich vorkamen, würde std::merge alle n + m Vorkommen ausgeben, während std::set_union nur std::max(n, m) Vorkommen ausgeben würde. Somit gibt std::merge genau std::distance(first1, last1) + std::distance(first2, last2) Werte aus, und std::set_union kann weniger erzeugen.

[edit] Beispiel

Führen Sie diesen Code aus

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

Mögliche Ausgabe

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

[edit] Fehlerberichte

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

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 780	C++98	die Merge-Operation war nicht definiert	defined

[edit] Siehe auch

inplace_merge	Führt zwei sortierte Bereiche an Ort und Stelle zusammen (Funktionstemplate) [edit]
is_sorted (C++11)	Prüft, ob ein Bereich aufsteigend sortiert ist (Funktionstemplate) [edit]
set_union	Berechnet die Vereinigung zweier Mengen (Funktionstemplate) [edit]
sort	Sortiert einen Bereich aufsteigend (Funktionstemplate) [edit]
stable_sort	Sortiert einen Bereich von Elementen und behält dabei die Reihenfolge zwischen gleichen Elementen bei (Funktionstemplate) [edit]
ranges::merge (C++20)	Führt zwei sortierte Bereiche zusammen (Algorithmus-Funktionsobjekt)[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