std::ranges::partition - cppreference.com

Definido en el archivo de encabezado `<algorithm>`

Signatura de la llamada
`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> partition( I first, S last, Pred pred, Proj proj = {} );`	(1)	(desde C++20)
`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> partition( R&& r, Pred pred, Proj proj = {} );`	(2)	(desde C++20)

1) Reordena los elementos en el rango [first, last) de tal manera que la proyección proj de todos los elementos para los que el predicado pred devuelve true preceden la proyección proj de todos los elementos para los que el predicado pred devuelve false. No se conserva el orden relativo de los elementos.

2) Igual que (1), pero usa r como el rango fuente, como si usara ranges::begin(r) como first y ranges::end(r) como last.

Las entidades similares a funciones descritas en esta página son niebloids, es decir:

Las listas de argumentos de plantilla explícitas no se pueden especificar al llamar a cualquiera de ellas.
Ninguna de ellas es visible para la búsqueda dependiente de argumentos.
Cuando alguna de ellas se encuentra mediante la búsqueda normal no calificada como el nombre a la izquierda del operador de llamada a función, se inhibe la búsqueda dependiente de argumentos.

En la práctica, pueden implementarse como objetos función o con extensiones de compilador especiales.

Parámetros

first, last	-	El rango de los elementos a reordenar.
r	-	El rango de los elementos a reordenar
pred	-	El predicado a aplicar a los elementos proyectados.
proj	-	La proyección a aplicar a los elementos.

Valor de retorno

Un subrango que comienza con un iterador hasta el primer elemento del segundo grupo y termina con un iterador igual a last. (2) devuelve std::ranges::dangling si r es un r-valor de tipo distinto de borrowed_range.

Complejidad

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

Posible implementación

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: ";
    ranges::copy(v, cout);

    auto tail = ranges::partition(v, [](int i) { return i % 2 == 0; });

    std::cout << "\nVector particionado:";
    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 no ordenada: ";
    ranges::copy(fl, cout);

    quicksort(ranges::begin(fl), ranges::end(fl), ranges::greater {});
    std::cout << "\nOrdenada usando quicksort: ";
    ranges::copy(fl, cout);

    std::cout << '\n';
}

Posible salida: