CKTIS / C++
std::stable_partition — partición estable de un rango
std::stable_partition reorganiza un rango para que los elementos que cumplen un predicado queden antes que los demás. Conserva el orden relativo dentro de ambos grupos y devuelve un iterador a la frontera de partición.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(
BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
// Usage:
auto boundary = std::stable_partition(first, last, pred);std::stable_partition, declarado en <algorithm>, modifica [first, last): los elementos para los que pred devuelve true quedan antes que los demás. El orden relativo se conserva por separado en ambos grupos. Esto no es una ordenación; std::partition no garantiza esta estabilidad.
El iterador devuelto boundary apunta al primer elemento del segundo grupo. Es igual a last cuando todos los elementos cumplen el predicado y a first cuando ninguno lo cumple. Si el rango está vacío, la función devuelve first; en ese caso se cumple first == last. Se requieren iteradores bidireccionales y elementos intercambiables, construibles mediante movimiento y asignables mediante movimiento. El predicado no debe modificar los elementos que examina.
Para la sobrecarga mostrada, sin política de ejecución, un rango de N elementos requiere exactamente N aplicaciones del predicado. Se realizan como máximo N log₂ N intercambios, o O(N) si hay suficiente memoria adicional. Por tanto, reorganizar el rango existente no implica una garantía de memoria auxiliar constante.
El ejemplo conserva el orden de los números pares 2, 4, 6 y los impares 5, 7, 1; la segunda línea de salida es el tamaño del primer grupo. La declaración mostrada está dirigida a C++23. La fuente es un borrador de trabajo en evolución que también incluye cambios posteriores; sus anotaciones constexpr no deben aplicarse automáticamente a C++23.
Ejemplos
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::vector<int> values{5, 2, 7, 4, 1, 6};
const auto boundary = std::stable_partition(
values.begin(), values.end(),
[](int value) { return value % 2 == 0; });
for (auto it = values.begin(); it != values.end(); ++it) {
if (it != values.begin()) {
std::cout << ' ';
}
std::cout << *it;
}
std::cout << '\n' << std::distance(values.begin(), boundary) << '\n';
}
Resultado
2 4 6 5 7 1 3
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.