std::ranges::inplace_merge

template< std::bidirectional_iterator I, std::sentinel_for<I> S,
          class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
    I inplace_merge( I first, I middle, S last,
                     Comp comp = {}, Proj proj = {} );

template< ranges::bidirectional_range R, class Comp = ranges::less,
          class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
ranges::borrowed_iterator_t<R>
    inplace_merge( R&& r, ranges::iterator_t<R> middle,
                   Comp comp = {}, Proj proj = {} );

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

Eine Sequenz heißt in Bezug auf den Komparator sortiert comp und die Projektion proj sortiert, wenn für jeden Iterator it, der auf die Sequenz zeigt, und jede nicht-negative ganze Zahl n, so dass it + n ein gültiger Iterator ist, der auf ein Element der Sequenz zeigt, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))) zu false ausgewertet wird.

Diese Zusammenführungsfunktion 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.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:

• Explizite Vorlagenargumentlisten können bei keinem Aufruf angegeben werden.
• Keine von ihnen ist für argumentabhängige Suche sichtbar.
• Wenn eine von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Suche unterdrückt.

Parameter

Rückgabewert

Ein Iterator gleich last .

Komplexität

Genau N − 1 Vergleiche, wenn ein zusätzlicher Speicherpuffer verfügbar ist, wobei N = ranges:: distance ( first, last ) . Andernfalls \(\scriptsize \mathcal{O}(N\cdot\log{(N)})\) 𝓞(N•log(N)) Vergleiche. Zusätzlich in beiden Fällen doppelt so viele Projektionen wie Vergleiche.

Hinweise

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

Mögliche Implementierung

Diese Implementierung zeigt nur den langsameren Algorithmus, der verwendet wird, wenn kein zusätzlicher Speicher verfügbar ist. Siehe auch die Implementierung in MSVC STL und libstdc++ .

struct inplace_merge_fn
{
    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr I operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const
    {
        I last_it = ranges::next(middle, last);
        inplace_merge_slow(first, middle, last_it,
                           ranges::distance(first, middle),
                           ranges::distance(middle, last_it),
                           std::ref(comp), std::ref(proj));
        return last_it;
    }
    template<ranges::bidirectional_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, ranges::iterator_t<R> middle,
                   Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
private:
    template<class I, class Comp, class Proj>
    static constexpr void inplace_merge_slow(I first, I middle, I last,
                                             std::iter_difference_t<I> n1,
                                             std::iter_difference_t<I> n2,
                                             Comp comp, Proj proj)
    {
        if (n1 == 0 || n2 == 0)
            return;
        if (n1 + n2 == 2 && comp(proj(*middle), proj(*first)))
        {
            ranges::iter_swap(first, middle);
            return;
        }
        I cut1 = first, cut2 = middle;
        std::iter_difference_t<I> d1{}, d2{};
        if (n1 > n2)
        {
            d1 = n1 / 2;
            ranges::advance(cut1, d1);
            cut2 = ranges::lower_bound(middle, last, *cut1,
                                       std::ref(comp), std::ref(proj));
            d2 = ranges::distance(middle, cut2);
        }
        else
        {
            d2 = n2 / 2;
            ranges::advance(cut2, d2);
            cut1 = ranges::upper_bound(first, middle, *cut2,
                                       std::ref(comp), std::ref(proj));
            d1 = ranges::distance(first, cut1);
        }
        I new_middle = ranges::rotate(cut1, middle, cut2);
        inplace_merge_slow(first, cut1, new_middle, d1, d2,
                           std::ref(comp), std::ref(proj));
        inplace_merge_slow(new_middle, cut2, last, n1 - d1, n2 - d2,
                           std::ref(comp), std::ref(proj));
    }
};
inline constexpr inplace_merge_fn inplace_merge {};

Beispiel

#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
void print(auto const& v, auto const& rem, int middle = -1)
{
    for (int i{}; auto n : v)
        std::cout << (i++ == middle ? "│ " : "") << n << ' ';
    std::cout << rem << '\n';
}
template<std::random_access_iterator I, std::sentinel_for<I> S>
requires std::sortable<I>
void merge_sort(I first, S last)
{
    if (last - first > 1)
    {
        I middle{first + (last - first) / 2};
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::ranges::inplace_merge(first, middle, last);
    }
}
int main()
{
    // benutzerdefinierte Merge-Sort-Demo
    std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
    print(v, ": vor der Sortierung");
    merge_sort(v.begin(), v.end());
    print(v, ": nach der Sortierung\n");
    // Zusammenführen mit Vergleichsfunktionsobjekt und Projektion
    using CI = std::complex<int>;
    std::vector<CI> r{{0,1}, {0,2}, {0,3}, {1,1}, {1,2}};
    const auto middle{std::ranges::next(r.begin(), 3)};
    auto comp{std::ranges::less{}};
    auto proj{[](CI z) { return z.imag(); }};
    print(r, ": vor dem Zusammenführen", middle - r.begin());
    std::ranges::inplace_merge(r, middle, comp, proj);
    print(r, ": nach dem Zusammenführen");
}

8 2 0 4 9 8 1 7 3 : vor der Sortierung
0 1 2 3 4 7 8 8 9 : nach der Sortierung
(0,1) (0,2) (0,3) │ (1,1) (1,2) : vor dem Zusammenführen
(0,1) (1,1) (0,2) (1,2) (0,3) : nach dem Zusammenführen

Siehe auch