CKTIS / C++
std::stable_sort — ordinamento stabile
std::stable_sort ordina un intervallo preservando l’ordine relativo degli elementi equivalenti secondo il confronto. Consente di ordinare i record per chiave senza modificare l’ordine precedente dei record con la stessa chiave.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <algorithm>
std::stable_sort(first, last);
std::stable_sort(first, last, comp);std::stable_sort, dichiarato in <algorithm>, riordina gli elementi di [first, last) e restituisce void. L’overload senza comp ordina in modo crescente usando il confronto predefinito; quello con comp usa il comparatore fornito. A differenza di std::sort, garantisce che l’ordine relativo degli elementi equivalenti venga preservato.
Equivalenza significa !comp(a, b) && !comp(b, a), non necessariamente a == b. Il comparatore deve definire un ordinamento stretto debole: in particolare, comp(x, x) deve essere falso e sia l’ordinamento sia l’equivalenza che ne deriva devono essere transitivi. Non usare <= al posto di < e non modificare gli elementi confrontati.
Sono necessari iteratori ad accesso casuale e gli elementi devono supportare lo scambio, la costruzione per spostamento e l’assegnazione per spostamento. Per N = last - first, il numero di confronti è O(N log N) quando è disponibile memoria aggiuntiva sufficiente; altrimenti è al massimo O(N log² N). L’ordinamento modifica l’input, ma non garantisce un uso costante della memoria ausiliaria.
L’esempio confronta solo key: B rimane prima di D e A prima di C. È pensato per essere eseguito con un’opzione del compilatore C++23. Il codice mostrato è stato eseguito senza modifiche in un ambiente isolato e l’output ottenuto coincideva con quello indicato. Questa verifica non attesta la compatibilità con l’ambiente di esecuzione in produzione. La bozza di lavoro corrente collegata può contenere estensioni successive a C++23; le chiamate mostrate non ne hanno bisogno.
Esempi
#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';
}
}
Risultato
1 B 1 D 2 A 2 C
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.