1. Ordinamento come operazione
Quando diciamo «ordinare», a livello comune suona semplice: «fa' in modo che sia in ordine crescente». Ma per il programmatore è utile formulare più precisamente: l'ordinamento è un algoritmo che riarrangia gli elementi in un certo intervallo [first, last) in modo che siano in un ordine desiderato. Nello standard C++ gli algoritmi di ordinamento sono raggruppati in un'area tematica a sé — e non è un caso: l'ordinamento è uno degli strumenti principali per lavorare con i dati.
Quasi tutti gli ordinamenti della STL seguono lo stesso modello mentale:
- esiste una sequenza di elementi (per esempio, std::vector<Task>);
- esiste una regola «chi deve venire prima» (per impostazione predefinita — tramite operator<);
- l'algoritmo riordina gli elementi in modo che la regola sia rispettata ovunque.
Mini-schema di pensiero
flowchart LR
A["vector<Task> (com'era)"] --> B["regola d'ordine (operator< o comp)"]
B --> C["sort/stable_sort"]
C --> D["vector<Task> (ordinato)"]
2. std::sort: veloce, ma senza promesse per elementi «uguali»
std::sort è il «cavallo da lavoro» della STL. Di solito lo si sceglie per primo: è rapido, familiare e quasi sempre «abbastanza buono». È importante ricordare subito: std::sort non garantisce che gli elementi con la stessa chiave mantengano l'ordine relativo originale. Quindi se avete più elementi «equivalenti per significato» — possono scambiarsi di posto.
Dal punto di vista di un principiante questo sembra un «e quindi?». Dal punto di vista di chi ha debuggato il problema «perché la lista salta all'improvviso» — suona come «ah, ecco il motivo».
Esempio minimale: ordinamento di numeri
Dopo questo sottoparagrafo dovreste avere la sensazione che ordinare nella STL sia letteralmente «una riga». Iniziamo dal più semplice: ordiniamo int. Qui il comparatore non serve: i numeri si confrontano già con <.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{5, 1, 4, 1, 3};
std::sort(v.begin(), v.end());
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // 1 1 3 4 5
}
La sintassi è sempre la stessa: includiamo <algorithm>, passiamo l'inizio e la fine dell'intervallo.
std::sort con comparatore: ordinare in ordine decrescente
Ora complichiamo un po' la cosa: vogliamo l'ordine «al contrario». Per questo std::sort accetta un terzo parametro — il comparatore. Il comparatore è una funzione del tipo bool comp(a, b), che risponde alla domanda «deve a stare prima di b?».
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{5, 1, 4, 1, 3};
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // 5 4 3 1 1
}
Di cosa deve essere il comparatore (e perché un comparatore «leggermente sbagliato» può rompere l'algoritmo) parleremo nella prossima lezione. Per ora è importante: il comparatore definisce l'ordine.
3. Stabilità dell'ordinamento e std::stable_sort
Qui inizia l'idea principale della lezione. La stabilità dell'ordinamento non riguarda «più veloce/più lento», ma il significato del risultato.
Immaginate di avere una lista di task, e ogni task ha una priorità. Se due task hanno la stessa priorità, di solito vogliamo che rimangano nello stesso ordine in cui sono stati aggiunti (o caricati). Questo ordine originale spesso ha senso: «come è arrivato — così mostriamo».
La ordine stabile garantisce: se gli elementi sono considerati «uguali rispetto alla chiave di ordinamento», il loro ordine relativo viene preservato.
Se un ordinamento è non stabile, gli elementi uguali possono mescolarsi arbitrariamente. Non è un bug dell'algoritmo — è semplicemente assenza di garanzia.
std::stable_sort differisce da std::sort per una sola garanzia fondamentale: la stabilità. Per il resto l'interfaccia è la stessa: [begin, end) e un comparatore opzionale.
Un punto pratico importante: la stabilità normalmente «si paga». Spesso ciò significa un po' più di tempo, o memoria addizionale, o entrambi (i dettagli dipendono dall'implementazione). Quindi attivate la stabilità quando è davvero necessaria, non «per ogni evenienza».
Modello di dati per gli esempi: Task
Da questo sottoparagrafo iniziamo a costruire una piccola applicazione: un mini task manager da console. L'abbiamo già visto in varie forme negli argomenti precedenti (contenitori, struct, output), e oggi aggiungeremo l'ordinamento «come nelle applicazioni reali», non «come in un compito in classe».
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{}; // più piccolo = maggiore priorità (0 = urgente)
std::string title;
};
int main() {
std::vector<Task> tasks{
{1, 2, "Buy milk"},
{2, 1, "Send report"},
{3, 2, "Call mom"},
{4, 1, "Fix bug #42"}
};
std::cout << "Tasks loaded: " << tasks.size() << "\n";
}
Per ora sono solo dati. Ora aggiungiamo la stampa e l'ordinamento.
Funzione di stampa dei task
Se non stampiamo il risultato — l'ordinamento resta filosofia. Quindi creiamo una piccola funzione printTasks. Ci servirà oggi e nelle prossime lezioni.
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{};
std::string title;
};
void printTasks(const std::vector<Task>& tasks) {
for (const auto& t : tasks) {
std::cout << "#" << t.id << " p=" << t.priority
<< " " << t.title << '\n';
}
}
Nota: il parametro è const std::vector<Task>&. Non copiamo l'intera lista di task solo per stampare.
Ordinare i task per priorità con std::sort
Ora l'approccio più diretto: «ordiniamo per priority». Scriviamo il comparatore e chiamiamo std::sort.
#include <algorithm>
#include <vector>
void sortByPriority(std::vector<Task>& tasks) {
std::sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority;
});
}
Questo funziona. Ma c'è una sottigliezza: abbiamo due task con priorità 1 e due con priorità 2. L'ordine all'interno di questi gruppi std::sort non è obbligata a preservarlo.
Se siete fortunati — «sulla vostra macchina» sembrerà stabile. Se non lo siete — i task all'interno della stessa priorità inizieranno a cambiare ordine, e l'utente penserà che l'applicazione «si comporta in modo strano».
4. Stabilità in pratica: elementi che «saltano» e la soluzione
La stabilità è utile non per estetica, ma per evitare cattive esperienze d'uso. Imponiamo una regola: entro la stessa priorità i task devono essere mostrati nell'ordine di inserimento (cioè per id, dato che li abbiamo aggiunti in sequenza).
Se usiamo std::sort solo su priority, due task con la stessa priority possono scambiarsi di posto. Formalmente l'algoritmo avrà comunque ragione.
Per rendere la cosa visibile, stampiamo i task prima e dopo.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{};
std::string title;
};
void printTasks(const std::vector<Task>& tasks) {
for (const auto& t : tasks) {
std::cout << "#" << t.id << " p=" << t.priority
<< " " << t.title << '\n';
}
}
int main() {
std::vector<Task> tasks{
{1, 2, "Buy milk"},
{2, 1, "Send report"},
{3, 2, "Call mom"},
{4, 1, "Fix bug #42"}
};
std::cout << "Before:\n";
printTasks(tasks);
std::sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority;
});
std::cout << "\nAfter sort by priority:\n";
printTasks(tasks);
}
Il risultato «dopo» garantisce solo che le priorità siano nell'ordine 1, 1, 2, 2. Quale delle due task con priority == 1 verrà prima — non è garantito.
Ora la stessa operazione, ma stabile. Sostituiamo semplicemente sort con stable_sort. L'interfaccia è identica, la garanzia è diversa.
#include <algorithm>
#include <vector>
void stableSortByPriority(std::vector<Task>& tasks) {
std::stable_sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority;
});
}
Ora la regola «entro la stessa priorità l'ordine rimane com'era» è soddisfatta automaticamente.
Questo è esattamente ciò che ci si aspetta nelle applicazioni: l'utente non ha chiesto di «randomizzare» i task con la stessa priorità. Ha chiesto di «ordinare». La stabilità rende l'ordinamento prevedibile.
5. Quando la stabilità è veramente importante
È facile esagerare: «stable_sort è meglio perché più affidabile». Ma in informatica «meglio» quasi sempre significa «meglio per requisiti specifici». Altrimenti può voler dire «più lento e più esoso di memoria senza vantaggi».
Scenario: l'ordine originale ha significato
Caso molto comune: i dati hanno già un ordine che significa qualcosa. Per esempio, «come arrivano dal server», «come l'utente li ha aggiunti», «come sono nel file». Si vuole ordinare per una chiave ma mantenere l'ordine originale fra gli elementi uguali. Questo è un caso tipico per std::stable_sort.
Il nostro Task è proprio un esempio del genere: se la priorità è uguale, vogliamo mantenere l'ordine di inserimento.
Scenario: ordinamento multistep
Questo scenario è particolarmente istruttivo perché mostra perché la stabilità è utile anche a chi «non pensa a UX ma ad algoritmi».
Supponiamo di voler l'ordine: prima per priorità, e dentro la stessa priorità — per titolo. Si può scrivere un unico comparatore «se le priorità sono uguali confronta title» — e ne parleremo nella prossima lezione (comparatore corretto e ordine totale).
C'è però un altro approccio: fare l'ordinamento in due passaggi, e qui la stabilità diventa lo strumento. Prima ordiniamo per la chiave secondaria (title), poi stabilmente ordiniamo per la chiave primaria (priority). La stabilità garantisce che, dentro la stessa priorità, rimanga l'ordine già stabilito in base al title.
#include <algorithm>
#include <string>
#include <vector>
void sortByPriorityThenTitle(std::vector<Task>& tasks) {
std::sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.title < b.title; // chiave secondaria
});
std::stable_sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority; // chiave primaria
});
}
Questa tecnica si usa spesso quando le chiavi sono molte e non si vuole scrivere un comparatore enorme. Sì, in termini di prestazioni sono due passaggi O(N log N), quindi va usata con criterio. Ma come concetto è molto utile.
6. sort vs stable_sort: confronto «a occhio»
Ora è utile riassumere le differenze in una tabella. Non tratta dell'implementazione interna, ma di quali garanzie ottieni come utente dell'algoritmo.
| Criterio | |
|
|---|---|---|
| Garanzia di stabilità | No (gli elementi uguali possono cambiare ordine) | Sì (preserva l'ordine degli elementi uguali rispetto alla chiave) |
| Scelta tipica di default | Sì | Solo se serve stabilità |
| Memoria/costo | Di solito più economico | Di solito più costoso (spesso richiede memoria aggiuntiva) |
| Dove è più utile | «Semplicemente ordinare» | Liste per UX, report, ordinamenti multistep |
La formulazione sorted with respect to comp è un'idea importante dello standard: dopo l'ordinamento l'intervallo deve essere «ordinato rispetto al comparatore», non semplicemente «in qualche modo più ordinato».
7. Integrazione nell'applicazione: modalità di ordinamento
Per rendere concreto l'esempio, aggiungiamo in main un interruttore: ordinare con l'algoritmo normale o con quello stabile. Somiglia già a un programma reale: l'utente sceglie la modalità e voi mostrate il risultato.
Dopo questo sottoparagrafo dovreste acquisire una buona abitudine: incapsulare l'ordinamento in piccole funzioni (sortBy...) e lasciare in main solo lo scenario d'uso.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{};
std::string title;
};
void printTasks(const std::vector<Task>& tasks) {
for (const auto& t : tasks) {
std::cout << "#" << t.id << " p=" << t.priority
<< " " << t.title << '\n';
}
}
void sortByPriority(std::vector<Task>& tasks, bool stable) {
auto comp = [](const Task& a, const Task& b) {
return a.priority < b.priority;
};
if (stable) {
std::stable_sort(tasks.begin(), tasks.end(), comp);
} else {
std::sort(tasks.begin(), tasks.end(), comp);
}
}
int main() {
std::vector<Task> tasks{
{1, 2, "Buy milk"},
{2, 1, "Send report"},
{3, 2, "Call mom"},
{4, 1, "Fix bug #42"}
};
std::cout << "Before:\n";
printTasks(tasks);
sortByPriority(tasks, true);
std::cout << "\nAfter stable sort by priority:\n";
printTasks(tasks);
}
Qui abbiamo fatto una cosa importante: lo stesso comparatore (comp) viene usato per entrambi gli algoritmi, e la logica di scelta è nascosta in un unico punto.
8. Errori tipici usando sort e stable_sort
Errore n.1: aspettarsi stabilità da std::sort.
Trappola molto comune: ordinate su un campo e «sembra» che gli elementi uguali mantengano l'ordine. Poi cambia il compilatore, i dati o le ottimizzazioni — e l'ordine interno agli uguali comincia a «saltare». Se l'ordine degli uguali è semanticamente importante (UI, report, liste di task) — usate std::stable_sort, non sperate nella fortuna.
Errore n.2: pensare che la stabilità sia sempre «meglio».
La stabilità è una garanzia aggiuntiva e le garanzie hanno un costo. Se l'ordine relativo degli elementi uguali non vi interessa, std::sort è più semplice e spesso più economico. Buona pratica ingegneristica: pagate solo per le garanzie di cui avete realmente bisogno.
Errore n.3: confondere il significato del comparatore.
I principianti a volte scrivono il comparatore come se rispondesse «a deve essere maggiore di b?» o addirittura «sono uguali?». Nel contesto dell'ordinamento il comparatore si legge come «a deve venire prima di b». Le regole di correttezza del comparatore (inclusi i casi spiacevoli in cui l'algoritmo può comportarsi in modo strano) le affronteremo nella prossima lezione — è un punto in cui è meglio non improvvisare.
Errore n.4: fare un ordinamento in due passaggi ma dimenticare la stabilità nel secondo passo.
Errore classico: prima ordinate per la chiave secondaria, poi fate il secondo passaggio con il normale std::sort sulla chiave primaria e vi meravigliate che l'ordine secondario sia sparito. Nello schema a due passaggi il secondo passo deve essere stabile, altrimenti rovina il risultato del primo.
Errore n.5: ordinare «dentro la print» o in punti sparsi del codice.
A volte l'ordinamento viene inserito appena prima della stampa, dentro la funzione di output, o ripetuto in più punti. Poi compaiono «fantasmi»: i dati sembrano gli stessi, ma l'ordine cambia. È meglio tenere l'ordinamento in un unico posto, in una funzione separata, ed evocarlo in modo esplicito — così controllate il momento in cui i dati vengono «riordinati».
GO TO FULL VERSION