std::ranges:: partition

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 de función, la búsqueda dependiente de argumento queda inhibida.

Parámetros

Valor de retorno

Un subrango que comienza con un iterador al primer elemento del segundo grupo y termina con un iterador igual a last . (2) retorna std::ranges::dangling si r es un rvalue de tipo no- borrowed_range .

Complejidad

Dado N = ranges:: distance ( first, last ) , exactamente N aplicaciones del predicado y proyección. Como máximo N / 2 intercambios si I modela ranges::bidirectional_iterator , y como máximo N intercambios en caso contrario.

Implementación posible

struct partition_fn
{
    template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
             std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
    constexpr ranges::subrange<I>
        operator()(I first, S last, Pred pred, Proj proj = {}) const
    {
        first = ranges::find_if_not(first, last, std::ref(pred), std::ref(proj));
        if (first == last)
            return {first, first};
        for (auto i = ranges::next(first); i != last; ++i)
        {
            if (std::invoke(pred, std::invoke(proj, *i)))
            {
                ranges::iter_swap(i, first);
                ++first;
            }
        }
        return {std::move(first), std::move(last)};
    }
    template<ranges::forward_range R, class Proj = std::identity,
             std::indirect_unary_predicate<
                 std::projected<ranges::iterator_t<R>, Proj>> Pred>
    requires std::permutable<ranges::iterator_t<R>>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, Pred pred, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::ref(pred), std::ref(proj));
    }
};
inline constexpr partition_fn partition;

Ejemplo

#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>
namespace ranges = std::ranges;
template<class I, std::sentinel_for<I> S, class Cmp = ranges::less>
requires std::sortable<I, Cmp>
void quicksort(I first, S last, Cmp cmp = Cmp {})
{
    using reference = std::iter_reference_t<I>;
    if (first == last)
        return;
    auto size = ranges::distance(first, last);
    auto pivot = ranges::next(first, size - 1);
    ranges::iter_swap(pivot, ranges::next(first, size / 2));
    auto tail = ranges::partition(first, pivot, [=](reference em)
    {
        return std::invoke(cmp, em, *pivot); // em < pivot
    });
    ranges::iter_swap(pivot, tail.begin());
    quicksort(first, tail.begin(), std::ref(cmp));
    quicksort(ranges::next(tail.begin()), last, std::ref(cmp));
}
int main()
{
    std::ostream_iterator<int> cout {std::cout, " "};
    std::vector<int> v {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << "Vector original:  \t";
    ranges::copy(v, cout);
    auto tail = ranges::partition(v, [](int i) { return i % 2 == 0; });
    std::cout << "\nVector particionado: \t";
    ranges::copy(ranges::begin(v), ranges::begin(tail), cout);
    std::cout << "│ ";
    ranges::copy(tail, cout);
    std::forward_list<int> fl {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    std::cout << "\nLista sin ordenar: \t\t";
    ranges::copy(fl, cout);
    quicksort(ranges::begin(fl), ranges::end(fl), ranges::greater {});
    std::cout << "\nLista ordenada rápidamente: \t";
    ranges::copy(fl, cout);
    std::cout << '\n';
}

Vector original:        0 1 2 3 4 5 6 7 8 9
Vector particionado:    0 8 2 6 4 │ 5 3 7 1 9
Lista no ordenada:      1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Lista ordenada rápidamente: 92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8

Véase también