std:: inplace_merge

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

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

Mögliche Implementierung

Sehen Sie die Implementierungen in libstdc++ und libc++ .

Hinweise

Diese Funktion versucht, einen temporären Puffer zu allozieren. Falls die Allokation 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