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

Fusiona dos rangos ordenados consecutivos [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 apuntando 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 objetos función de algoritmo (conocidos informalmente como niebloids), es decir:

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

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