std::ranges::partition
De 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 > |
(1) | (desde C++20) |
| template< ranges::forward_range R, class Proj = std::identity, std::indirect_unary_predicate< |
(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.
Contenido |
[editar] 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. |
[editar] 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.
[editar] 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.
[editar] 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; |
[editar] Ejemplo
Ejecuta este código
#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:
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 Ordenada usando quicksort: 92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8
[editar] Véase también
| (C++20) |
Copia un rango, dividiendo los elementos en dos grupos (niebloid) |
| (C++20) |
Determina si el rango está dividido por el predicado dado. (niebloid) |
| (C++20) |
Divide elementos en dos grupos, conservando su orden relativo. (niebloid) |
| Divide un rango de elementos en dos grupos. (plantilla de función) |
