std::ranges:: inplace_merge

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

Eine Sequenz wird als sortiert bezüglich des Komparators comp und der Projektion proj bezeichnet, wenn für jeden Iterator it , der auf die Sequenz zeigt, und jede nicht-negative Ganzzahl n , sodass 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 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) vor den Elementen aus dem zweiten Bereich (unter Beibehaltung ihrer ursprünglichen Reihenfolge) stehen.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithm Function Objects (informell bekannt als Niebloids ), das heißt:

• Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keiner von ihnen ist sichtbar für argument-dependent lookup .
• Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup 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