std::inplace_merge

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

template< class ExecutionPolicy, class BidirIt >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last );

template< class BidirIt, class Compare >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

template< class ExecutionPolicy, class BidirIt, class Compare >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

Vereinigt zwei aufeinanderfolgende sortierte Bereiche [first, middle) und [middle, last) zu einem sortierten Bereich [first, last).

Diese Mischfunktion ist stabil, d. h. für äquivalente Elemente in den beiden ursprünglichen Bereichen gehen die Elemente aus dem ersten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) den Elementen aus dem zweiten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) voraus.

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

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

Parameter

Komplexität

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

Ausnahmen

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

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

Mögliche Implementierung

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

Hinweise

Diese Funktion versucht, einen temporären Puffer zuzuweisen. Wenn die Zuweisung fehlschlägt, wird der weniger effiziente Algorithmus gewählt.

Beispiel

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

-2 0 1 2 3 7 8 11 11

Siehe auch