CKTIS / C++
std::stable_sort — ordenación estable
std::stable_sort ordena un rango y conserva el orden relativo de los elementos equivalentes según la comparación. Permite ordenar registros por una clave sin cambiar el orden previo de los registros que tienen la misma clave.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
std::stable_sort(first, last);
std::stable_sort(first, last, comp);std::stable_sort, declarado en <algorithm>, reorganiza los elementos de [first, last) y devuelve void. La sobrecarga sin comp ordena de forma ascendente usando la comparación predeterminada; la que lleva comp usa el comparador proporcionado. A diferencia de std::sort, garantiza que se conserve el orden relativo de los elementos equivalentes.
Equivalencia significa !comp(a, b) && !comp(b, a), y no necesariamente a == b. El comparador debe definir un orden débil estricto: en particular, comp(x, x) debe ser falso, y tanto el orden como la equivalencia inducida deben ser transitivos. No uses <= en lugar de < ni modifiques los elementos que se comparan.
Se requieren iteradores de acceso aleatorio, y los elementos deben admitir intercambio, construcción por movimiento y asignación por movimiento. Para N = last - first, el número de comparaciones es O(N log N) si hay suficiente memoria adicional; de lo contrario, es como máximo O(N log² N). La ordenación modifica la entrada, pero no garantiza un uso constante de memoria auxiliar.
El ejemplo compara solo key: B permanece antes que D, y A antes que C. Está pensado para ejecutarse con una opción de compilador C++23. El código mostrado se ejecutó sin cambios en un entorno aislado y la salida obtenida coincidió con la indicada. Esta verificación no acredita la compatibilidad con el entorno de ejecución en producción. El borrador de trabajo actual enlazado puede incluir extensiones posteriores a C++23; las llamadas mostradas no las necesitan.
Ejemplos
#include <algorithm>
#include <iostream>
#include <vector>
struct Item {
int key;
char id;
};
int main() {
std::vector<Item> items{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};
std::stable_sort(items.begin(), items.end(),
[](const Item& a, const Item& b) {
return a.key < b.key;
});
for (const Item& item : items) {
std::cout << item.key << ' ' << item.id << '\n';
}
}
Resultado
1 B 1 D 2 A 2 C
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.