std::ranges:: inplace_merge

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 vers la séquence et tout entier non négatif n tel que it + n soit un itérateur valide pointant vers 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 (préservant leur ordre d'origine) précèdent les éléments de la seconde plage (préservant leur ordre d'origine).

Les entités de type fonction décrites sur cette page sont des algorithm function objects (informellement appelées niebloids ), c'est-à-dire :

• Les listes d'arguments de template explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
• Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
• Lorsque l'une d'entre elles est trouvée par la 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