std::ranges::partition_point
| 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:
Después de particionar, v: 2 4 6 8 5 3 7 1 9
El punto de partición se encuentra en 4; v[4] = 5
Primera partición (todos los elementos pares): 2 4 6 8
Segunda partición (todos los elementos nones): 5 3 7 1 9
Véase también
(C++20) |
Comprueba si un rango está ordenado en orden ascendente. (niebloid) |
(C++20) |
Devuelve un iterador al primer elemento no menor que el valor dado. (niebloid) |
(C++11) |
Ubica el punto de partición de un rango particionado. (plantilla de función) |