std::ranges:: inplace_merge

Combina dos rangos consecutivos ordenados [ first , middle ) y [ middle , last ) en un único rango ordenado [ first , last ) .

Se dice que una secuencia está ordenada con respecto al comparador comp y la proyección proj si para cualquier iterador it que apunte a la secuencia y cualquier entero no negativo n tal que it + n sea un iterador válido que apunte a un elemento de la secuencia, std:: invoke ( comp, std:: invoke ( proj, * ( it + n ) ) , std:: invoke ( proj, * it ) ) ) evalúa a false .

Esta función de fusión es estable , lo que significa que para elementos equivalentes en los dos rangos originales, los elementos del primer rango (preservando su orden original) preceden a los elementos del segundo rango (preservando su orden original).

Las entidades similares a funciones descritas en esta página son algorithm function objects (conocidas informalmente como niebloids ), es decir:

• No se pueden especificar listas de argumentos de plantilla explícitas al llamar a cualquiera de ellos.
• Ninguno de ellos es visible para la búsqueda dependiente de argumento .
• Cuando cualquiera de ellos es encontrado mediante la búsqueda no calificada normal como el nombre a la izquierda del operador de llamada a función, la búsqueda dependiente de argumento queda inhibida.

Parámetros

Valor de retorno

Un iterador igual a last .

Complejidad

Exactamente N − 1 comparaciones, si hay disponible un búfer de memoria adicional, donde N = ranges:: distance ( first, last ) . De lo contrario, \(\scriptsize \mathcal{O}(N\cdot\log{(N)})\) 𝓞(N•log(N)) comparaciones. Adicionalmente, el doble de proyecciones que comparaciones en ambos casos.

Notas

Esta función intenta asignar un búfer temporal. Si la asignación falla, se elige el algoritmo menos eficiente.

Implementación posible

Esta implementación solo muestra el algoritmo más lento utilizado cuando no hay memoria adicional disponible. Consulte también la implementación en MSVC STL y 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 {};

Ejemplo

#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()
{
    // demostración personalizada de merge-sort
    std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
    print(v, ": antes de ordenar");
    merge_sort(v.begin(), v.end());
    print(v, ": después de ordenar\n");
    // fusión con objeto de función de comparación y proyección
    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, ": antes de fusionar", middle - r.begin());
    std::ranges::inplace_merge(r, middle, comp, proj);
    print(r, ": después de fusionar");
}

8 2 0 4 9 8 1 7 3 : antes de ordenar
0 1 2 3 4 7 8 8 9 : después de ordenar
(0,1) (0,2) (0,3) │ (1,1) (1,2) : antes de fusionar
(0,1) (1,1) (0,2) (1,2) (0,3) : después de fusionar

Véase también