std::partition_point
| Definido en el archivo de encabezado <algorithm>
|
||
| template< class ForwardIt, class UnaryPred > ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPred p ); |
(desde C++11) (constexpr desde C++20) |
|
Examina el rango particionado [first, last) y ubica el final de la primera partición, es decir, el primer elemento que no satisface p o last si todos los elementos satisfacen p.
Si los elementos elem de [first, last) no están particionados con respecto a la expresión bool(p(elem)), el comportamiento no está definido.
Contenido |
[editar] Parámetros
| first, last | - | El rango particionado de elementos a examinar. |
| p | - | Predicado unario que devuelve true para los elementos que se encuentran al principio del rango. La expresión p(v) debe ser convertible a bool para cada argumento |
| Requisitos de tipo | ||
-ForwardIt debe satisfacer los requisitos de ForwardIterator.
| ||
-UnaryPred debe satisfacer los requisitos de Predicate.
| ||
[editar] Valor de retorno
El iterador después del final de la primera partición dentro de [first, last) o last si todos los elementos satisfacen p.
[editar] Complejidad
Dada N como std::distance(first, last), realiza O(log(N)) aplicaciones del predicado p.
[editar] Notas
Este algoritmo es una forma más general de std::lower_bound, que se puede expresar en términos de std::partition_point con el predicado [&](const auto& e) { return e < value; });.
[editar] Posible implementación
template<class ForwardIt, class UnaryPred> constexpr //< desde C++20 ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPred p) { for (auto length = std::distance(first, last); 0 < length; ) { auto half = length / 2; auto middle = std::next(first, half); if (p(*middle)) { first = std::next(middle); length -= (half + 1); } else length = half; } return first; } |
[editar] Ejemplo
#include <algorithm> #include <array> #include <iostream> #include <iterator> auto imprimir_secuencia = [](auto rem, auto first, auto last) { for (std::cout << rem; 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::partition(v.begin(), v.end(), es_par); imprimir_secuencia("Después de particionar, v: ", v.cbegin(), v.cend()); const auto pp = std::partition_point(v.cbegin(), v.cend(), es_par); const auto i = std::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: 8 2 6 4 5 3 7 1 9 El punto de partición se encuentra en 4; v[4] = 5 Primera partición (todos los elementos pares): 8 2 6 4 Segunda partición (todos los elementos nones): 5 3 7 1 9
[editar] Véase también
| (C++11) |
Encuentra el primer elemento que satisfaga un criterio específico. (plantilla de función) |
| (C++11) |
Comprueba si un rango se clasifican en orden ascendente Original: checks whether a range is sorted into ascending order The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (plantilla de función) |
| Devuelve un iterador al primer elemento no menor que el valor dado. (plantilla de función) | |
| (C++20) |
Localiza el punto de partición de un rango particionado (niebloid) |
