std::ranges::partition_point - cppreference.com

De cppreference.com

Definido en el archivo de encabezado `<algorithm>`

Signatura de la llamada
`template< std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_unary_predicate<std::projected<I, Proj>> Pred > constexpr I partition_point( 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 > constexpr ranges::borrowed_iterator_t<R> partition_point( R&& r, Pred pred, Proj proj = {} );`	(2)	(desde C++20)

Examina el rango particionado (como por ranges::partition) [first, last) o r y ubica el final de la primera partición, es decir, el elemento proyectado que no satisface pred o last si todos los elementos proyectados satisfacen pred.

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	-	Iterador centinela que define el rango parcialmente ordenado a examinar.
r	-	El rango parcialmente ordenado a examinar.
pred	-	Predicado a aplicar a los elementos proyectados.
proj	-	Proyección a aplicar los elementos.

Valor de retorno

El iterador más allá del final de la primera partición dentro de [first, last) o el iterador igual a last si todos los elementos proyectados satisfacen pred.

Complejidad

Dada N = ranges::distance(first, last), realiza O(log N) aplicaciones del predicado pred y la proyección proj.

Sin embargo, si los centinelas no modelan std::sized_sentinel_for<I>, el número de incrementos de iterador es O(N).

Notas

Este algoritmo es una forma más general de ranges::lower_bound, que se puede expresar en términos de ranges::partition_point con el predicado [&](auto const& e) { return std::invoke(pred, e, value); });.

Ejemplo

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

auto imprimir_secuencia = [](auto comentario, auto first, auto last)
{
    for (std::cout << comentario; first != last; std::cout << *first++ << ' ') {}
    std::cout << '\n';
};

int main()
{
    std::array v {1, 2, 3, 4, 5, 6, 7, 8, 9};

    auto es_par = [](int i) { return i % 2 == 0; };

    std::ranges::partition(v, es_par);
    imprimir_secuencia("Después de particionar, v: ", v.cbegin(), v.cend());

    const auto pp = std::ranges::partition_point(v, es_par);
    const auto i = std::ranges::distance(v.cbegin(), pp);
    std::cout << "El punto de partición se encuentra en " << i << "; v[" << i << "] = " << *pp << '\n';

    imprimir_secuencia("Primera partición (todos los elementos pares): ", v.cbegin(), pp);
    imprimir_secuencia("Segunda partición (todos los elementos nones): ", pp, v.cend());
}

Posible salida: