std::inplace_merge

Definiert in Header `<algorithm>`
template< class BidirIt > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );	(1)	(constexpr seit C++26)
template< class ExecutionPolicy, class BidirIt > void inplace_merge( ExecutionPolicy&& policy, BidirIt first, BidirIt middle, BidirIt last );	(2)	(seit C++17)
template< class BidirIt, class Compare > void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );	(3)	(constexpr seit C++26)
template< class ExecutionPolicy, class BidirIt, class Compare > void inplace_merge( ExecutionPolicy&& policy, BidirIt first, BidirIt middle, BidirIt last, Compare comp );	(4)	(seit C++17)

Führt zwei aufeinanderfolgende sortierte Bereiche [first, middle) und [middle, last) zu einem sortierten Bereich [first, last) zusammen.

1) Wenn [first, middle) oder [middle, last) nicht sortiert ist bezüglich operator<(bis C++20)std::less{}(seit C++20), ist das Verhalten undefiniert.

3) Wenn [first, middle) oder [middle, last) 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 Zusammenführungsfunktion ist stabil, was bedeutet, dass für gleichwertige 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 eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert

[first, middle) oder [middle, last) ist kein gültiger Bereich.

Der Typ von *first ist nicht Swappable.	(bis C++11)
`BiditIt` ist nicht ValueSwappable. Der Typ von first ist nicht MoveConstructible. Der Typ von first ist kein MoveAssignable.	(seit C++11)

[edit] Parameter

first	-	der Anfang des ersten sortierten Bereichs
middle	-	das Ende des ersten sortierten Bereichs und der Anfang des zweiten
last	-	das Ende des zweiten sortierten Bereichs
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 ein Objekt vom Typ BidirIt dereferenziert und dann implizit in beide konvertiert werden kann.
Typanforderungen
- `BidirIt` muss die Anforderungen von LegacyBidirectionalIterator erfüllen.
- `Compare` muss die Anforderungen an Compare erfüllen.

[edit] Komplexität

Gegeben sei $\scriptsize N$ $N$ als std::distance(first, last).

1) Genau

N-1

Vergleiche mit operator<(bis C++20)std::less{}(seit C++20), wenn genügend zusätzlicher Speicher verfügbar ist,

O(N\cdotlog(N))

Vergleiche andernfalls.

2)

O(N\cdotlog(N))

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

3) Genau

N-1

Anwendungen der Vergleichsfunktion comp, wenn genügend zusätzlicher Speicher verfügbar ist,

O(N\cdotlog(N))

Anwendungen andernfalls.

4)

O(N\cdotlog(N))

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 die Implementierungen in libstdc++ und libc++.

[edit] Hinweise

Diese Funktion versucht, einen temporären Puffer zu allokieren. Schlägt die Allokation fehl, wird der weniger effiziente Algorithmus gewählt.

Feature-Test-Makro	Wert	Std	Feature
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	constexpr inplace merging (1), (3)

[edit] Beispiel

Der folgende Code ist eine Implementierung von Merge-Sort.

Führen Sie diesen Code aus

#include <algorithm>
#include <iostream>
#include <vector>
 
template<class Iter>
void merge_sort(Iter first, Iter last)
{
    if (last - first > 1)
    {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::inplace_merge(first, middle, last);
    }
}
 
int main()
{
    std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for (const auto& n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

Ausgabe

-2 0 1 2 3 7 8 11 11

[edit] Siehe auch

merge	Führt zwei sortierte Bereiche zusammen (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::inplace_merge (C++20)	Führt zwei sortierte Bereiche an Ort und Stelle 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