std::stable_sort

Definido en el encabezado `<algorithm>`
template< class RandomIt > void stable_sort( RandomIt first, RandomIt last );	(1)	(constexpr desde C++26)
template< class ExecutionPolicy, class RandomIt > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(desde C++17)
template< class RandomIt, class Compare > void stable_sort( RandomIt first, RandomIt last, Compare comp );	(3)	(constexpr desde C++26)
template< class ExecutionPolicy, class RandomIt, class Compare > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );	(4)	(desde C++17)

Ordena los elementos en el rango [first, last) en orden no descendente. Se garantiza que se preserva el orden de los elementos equivalentes.

1) Los elementos se ordenan con respecto a operator<(hasta C++20)std::less{}(desde C++20).

3) Los elementos se ordenan con respecto a comp.

2,4) Igual que (1,3), pero ejecutado según policy.

Estas sobrecargas participan en la resolución de sobrecarga solo si el valor de la siguiente expresión es true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(hasta C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(desde C++20)

Si alguna de las siguientes condiciones se cumple, el comportamiento no está definido:

El tipo de `*first` no es Swappable.	(hasta C++11)
`RandomIt` no es ValueSwappable. El tipo de `first` no es MoveConstructible. El tipo de `first` no es MoveAssignable.	(desde C++11)

Parámetros

first, last	-	el par de iteradores que define el rango de elementos a ordenar
policy	-	la política de ejecución a utilizar
comp	-	objeto función de comparación (es decir, un objeto que satisface los requisitos de Compare ) que devuelve true si el primer argumento es menor que (es decir, está ordenado antes que) el segundo. La firma de la función de comparación debe ser equivalente a la siguiente: bool cmp ( const Type1 & a, const Type2 & b ) ; Aunque la firma no necesita tener const & , la función no debe modificar los objetos pasados a ella y debe poder aceptar todos los valores de tipo (posiblemente const) `Type1` y `Type2` independientemente de la categoría de valor (por lo tanto, `Type1&` no está permitido , ni tampoco `Type1` a menos que para `Type1` un movimiento sea equivalente a una copia (desde C++11) ). Los tipos Type1 y Type2 deben ser tales que un objeto de tipo RandomIt pueda ser desreferenciado y luego convertido implícitamente a ambos.
Requisitos de tipo
- `RandomIt` debe cumplir con los requisitos de LegacyRandomAccessIterator .
- `Compare` debe cumplir con los requisitos de Compare .

Complejidad

Dado $\scriptsize N$ $N$ como last - first :

1,2)

O(N\cdotlog(N))

comparaciones usando operator < (hasta C++20) std:: less { } (desde C++20) si hay suficiente memoria adicional disponible, de lo contrario

O(N\cdotlog 2 (N))

comparaciones.

3,4)

O(N\cdotlog(N))

aplicaciones del comparador comp si hay suficiente memoria adicional disponible, de lo contrario

O(N\cdotlog 2 (N))

aplicaciones.

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy reportan errores de la siguiente manera:

Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y ExecutionPolicy es uno de los standard policies , std::terminate es llamado. Para cualquier otro ExecutionPolicy , el comportamiento está definido por la implementación.
Si el algoritmo falla al asignar memoria, std::bad_alloc es lanzado.

Implementación posible

Consulte también las implementaciones en libstdc++ y libc++ .

Notas

Esta función intenta asignar un búfer temporal de igual tamaño que la secuencia a ordenar. Si la asignación falla, se elige el algoritmo menos eficiente.

Macro de prueba de características	Valor	Std	Característica
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	constexpr ordenación estable, sobrecargas ( 1 ) , ( 3 )

Ejemplo

Ejecutar este código

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct Employee
{
    int age;
    std::string name; // No participa en las comparaciones
};
bool operator<(const Employee& lhs, const Employee& rhs)
{
    return lhs.age < rhs.age;
}
#if __cpp_lib_constexpr_algorithms >= 202306L
consteval auto get_sorted()
{
    auto v = std::array{3, 1, 4, 1, 5, 9};
    std::stable_sort(v.begin(), v.end());
    return v;
}
static_assert(std::ranges::is_sorted(get_sorted()));
#endif
int main()
{
    std::vector<Employee> v{{108, "Zaphod"}, {32, "Arthur"}, {108, "Ford"}};
    std::stable_sort(v.begin(), v.end());
    for (const Employee& e : v)
        std::cout << e.age << ", " << e.name << '\n';
}

Salida:

32, Arthur
108, Zaphod
108, Ford

Véase también

sort	ordena un rango de elementos (plantilla de función & objeto función de algoritmo)
ranges::sort (C++20)
partial_sort	ordena los primeros N elementos de un rango (plantilla de función & objeto función de algoritmo)
ranges::partial_sort (C++20)
stable_partition	divide los elementos en dos grupos conservando su orden relativo dentro de cada grupo (plantilla de función & objeto función de algoritmo)
ranges::stable_partition (C++20)
ranges::stable_sort (C++20)	ordena un rango de elementos conservando el orden relativo de elementos equivalentes (objeto función de algoritmo)

Soporte del compilador
Independiente y alojado
Lenguaje
Biblioteca estándar
Encabezados de la biblioteca estándar
Requisitos nombrados
Macros de prueba de características (C++20)
Biblioteca de soporte del lenguaje
Biblioteca de conceptos (C++20)
Biblioteca de diagnosis
Biblioteca de gestión de memoria
Biblioteca de metaprogramación (C++11)
Biblioteca de utilidades generales
Biblioteca de contenedores
Biblioteca de iteradores
Biblioteca de rangos (C++20)
Biblioteca de algoritmos
Biblioteca de cadenas
Biblioteca de procesamiento de texto
Biblioteca numérica
Biblioteca de fecha y hora
Biblioteca de entrada/salida
Biblioteca del sistema de archivos (C++17)
Biblioteca de soporte de concurrencia (C++11)
Biblioteca de control de ejecución (C++26)
Especificaciones técnicas
Índice de símbolos
Bibliotecas externas

es.cppreference.net

Namespaces

Variants