CKTIS / C++
std::stable_sort — ordenação estável
std::stable_sort ordena um intervalo preservando a ordem relativa dos elementos equivalentes segundo a comparação. Permite ordenar registos por uma chave sem alterar a ordem anterior dos registos com a mesma chave.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#include <algorithm>
std::stable_sort(first, last);
std::stable_sort(first, last, comp);std::stable_sort, declarado em <algorithm>, reorganiza os elementos de [first, last) e devolve void. A sobrecarga sem comp ordena por ordem crescente usando a comparação predefinida; a sobrecarga com comp usa o comparador fornecido. Ao contrário de std::sort, garante a preservação da ordem relativa dos elementos equivalentes.
Equivalência significa !comp(a, b) && !comp(b, a), não necessariamente a == b. O comparador tem de definir uma ordem estrita fraca: em particular, comp(x, x) tem de ser falso, e tanto a ordem como a equivalência que dela resulta têm de ser transitivas. Não uses <= em vez de < nem modifiques os elementos comparados.
São necessários iteradores de acesso aleatório, e os elementos têm de suportar troca, construção por movimento e atribuição por movimento. Para N = last - first, o número de comparações é O(N log N) quando existe memória adicional suficiente; caso contrário, é, no máximo, O(N log² N). A ordenação modifica a entrada, mas não garante um uso constante de memória auxiliar.
O exemplo compara apenas key: B mantém-se antes de D, e A antes de C. Destina-se a ser executado com uma opção de compilador C++23. O código apresentado foi executado sem alterações num ambiente isolado e o resultado obtido coincidiu com o indicado. Esta verificação não atesta a compatibilidade com o ambiente de execução em produção. O projeto de norma atual associado pode incluir extensões posteriores a C++23; as chamadas apresentadas não precisam delas.
Exemplos
#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
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.