std::partition
De es.cppreference.net
| Definido en el encabezado <algorithm>
|
||
template< class ForwardIt, class UnaryPred >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPred p );
|
(1) | (constexpr desde C++20) |
template< class ExecutionPolicy, class ForwardIt, class UnaryPred >
ForwardIt partition( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, UnaryPred p );
|
(2) | (desde C++17) |
1) Reordena los elementos en el rango
[first, last) de manera que todos los elementos para los cuales el predicado p devuelve true preceden a todos los elementos para los cuales el predicado p devuelve false. El orden relativo de los elementos no se conserva. 2) Igual que (1), pero ejecutado de acuerdo con
policy. Esta sobrecarga participa en la resolución de sobrecarga solo si el valor de la siguiente expresión es
true:
|
|
(hasta C++20) |
|
|
(desde C++20) |
Si el tipo de *first no es Swappable(hasta C++11)ForwardIt no es ValueSwappable(desde C++11), el comportamiento no está definido.
Parámetros
| first, last | - | el par de iteradores que definen el rango de elementos a reordenar |
| policy | - | la política de ejecución a usar |
| p | - | predicado unario que devuelve true si el elemento debe ordenarse antes que otros elementos. La expresión |
| Requisitos de tipo | ||
-ForwardIt debe cumplir con los requisitos de LegacyForwardIterator.
| ||
-UnaryPred debe cumplir con los requisitos de Predicate.
| ||
Valor de retorno
Iterador al primer elemento del segundo grupo.
Complejidad
Dado N como std::distance(first, last):
1) Exactamente N aplicaciones de
p. Como máximo N/2 intercambios si
ForwardIt cumple con los requisitos de LegacyBidirectionalIterator, y como máximo N intercambios en caso contrario.2) O(N) aplicaciones de
p. O(N·log(N)) intercambios.
Excepciones
La sobrecarga con un parámetro de plantilla llamado ExecutionPolicy reporta errores de la siguiente manera:
- Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y
ExecutionPolicyes una de las políticas estándar, std::terminate se llama. Para cualquier otroExecutionPolicy, el comportamiento está definido por la implementación. - Si el algoritmo falla al asignar memoria, std::bad_alloc se lanza.
Posible implementación
Implementa la sobrecarga (1) preservando la compatibilidad con C++11.
template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred p)
{
first = std::find_if_not(first, last, p);
if (first == last)
return first;
for (auto i = std::next(first); i != last; ++i)
if (p(*i))
{
std::iter_swap(i, first);
++first;
}
return first;
}
|
Ejemplo
Ejecutar este código
#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <vector>
template<class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if (first == last)
return;
auto pivot = *std::next(first, std::distance(first, last) / 2);
auto middle1 = std::partition(first, last, [pivot](const auto& em)
{
return em < pivot;
});
auto middle2 = std::partition(middle1, last, [pivot](const auto& em)
{
return !(pivot < em);
});
quicksort(first, middle1);
quicksort(middle2, last);
}
int main()
{
std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::cout << "Original vector: ";
for (int elem : v)
std::cout << elem << ' ';
auto it = std::partition(v.begin(), v.end(), [](int i) {return i % 2 == 0;});
std::cout << "\nPartitioned vector: ";
std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
std::cout << "* ";
std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
std::forward_list<int> fl {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
std::cout << "\nUnsorted list: ";
for (int n : fl)
std::cout << n << ' ';
quicksort(std::begin(fl), std::end(fl));
std::cout << "\nSorted using quicksort: ";
for (int fi : fl)
std::cout << fi << ' ';
std::cout << '\n';
}
Posible salida:
Original vector: 0 1 2 3 4 5 6 7 8 9
Partitioned vector: 0 8 2 6 4 * 5 3 7 1 9
Unsorted list: 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Sorted using quicksort: -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92
Informes de defectos
Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a estándares C++ previamente publicados.
| DR | Aplicado a | Comportamiento según lo publicado | Comportamiento correcto |
|---|---|---|---|
| LWG 498 | C++98 | std::partition requería que first ylast fueran LegacyBidirectionalIterator
|
solo se requería que fueran LegacyForwardIterator |
| LWG 2150 | C++98 | std::partition solo se requería colocar un elementoque satisface p antes de un elemento que no satisface p
|
corrigió el requisito |
Véase también
(C++11) |
determina si el rango está particionado por el predicado dado (plantilla de función & objeto función de algoritmo) |
(C++20) |
|
| divide los elementos en dos grupos mientras conserva su orden relativo dentro de cada grupo (plantilla de función & objeto función de algoritmo) | |
(C++20) |
|
(C++20) |
divide un rango de elementos en dos grupos (objeto función de algoritmo) |