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 = {} );

Fusionne deux plages triées consécutives [first, middle) et [middle, last) en une seule plage triée [first, last).

Une séquence est dite triée par rapport au comparateur comp et à la projection proj si pour tout itérateur it pointant sur la séquence et tout entier non négatif n tel que it + n soit un itérateur valide pointant sur un élément de la séquence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))) s'évalue à false.

Cette fonction de fusion est stable, ce qui signifie que, pour les éléments équivalents dans les deux plages d'origine, les éléments de la première plage (conservant leur ordre original) précèdent les éléments de la seconde plage (conservant leur ordre original).

Les entités de type fonction décrites sur cette page sont des objets fonctions d'algorithmes (informellement appelés niebloids), c'est-à-dire :

• Les listes d'arguments de modèle explicites ne peuvent pas être spécifiées lors de l'appel de l'un d'entre eux.
• Aucun d'entre eux n'est visible par recherche dépendante des arguments.
• Lorsque l'un d'entre eux est trouvé par recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

Un itérateur égal à last .

Complexité

Exactement N − 1 comparaisons, si une mémoire tampon supplémentaire est disponible, où N = ranges:: distance ( first, last ) . Sinon, \(\scriptsize \mathcal{O}(N\cdot\log{(N)})\) 𝓞(N•log(N)) comparaisons. De plus, deux fois plus de projections que de comparaisons dans les deux cas.

Notes

Cette fonction tente d'allouer un tampon temporaire. Si l'allocation échoue, l'algorithme moins efficace est choisi.

Implémentation possible

Cette implémentation montre uniquement l'algorithme plus lent utilisé lorsqu'aucune mémoire supplémentaire n'est disponible. Voir également l'implémentation dans MSVC STL et 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 {};

Exemple

#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()
{
    // démonstration de tri fusion personnalisé
    std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
    print(v, ": avant tri");
    merge_sort(v.begin(), v.end());
    print(v, ": après tri\n");
    // fusion avec objet de comparaison et projection
    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, ": avant fusion", middle - r.begin());
    std::ranges::inplace_merge(r, middle, comp, proj);
    print(r, ": après fusion");
}

8 2 0 4 9 8 1 7 3 : avant tri
0 1 2 3 4 7 8 8 9 : après tri
(0,1) (0,2) (0,3) │ (1,1) (1,2) : avant fusion
(0,1) (1,1) (0,2) (1,2) (0,3) : après fusion

Voir aussi