Guida C++ interattiva: Ordinamento

Q: Come si ordina un vector in C++?

Includi e chiama sort(v.begin(), v.end()). Così gli elementi vengono ordinati sul posto in ordine crescente usando operator<. Per ordinare un array, passa arr e arr + n (oppure begin(arr) / end(arr)).

Q: Come si ordina in modo decrescente in C++?

Passa un comparatore che restituisce a > b: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Puoi anche usare il comparatore predefinito sort(v.begin(), v.end(), greater ()); da .

Q: Perché il mio comparatore C++ fa andare in crash std::sort?

Il comparatore deve definire uno strict weak ordering: deve restituire false quando i due argomenti sono uguali. Usare = (che restituiscono true per elementi uguali) viola questa regola ed è undefined behavior: std::sort può leggere fuori dai limiti e andare in crash. Confronta sempre con .

L'ordinamento è solo un altro algoritmo

Nella pagina precedente hai visto che la libreria standard offre algoritmi pronti che funzionano su qualsiasi intervallo tramite gli iteratori. L'ordinamento è quello che userai più spesso, e merita una pagina tutta sua perché ha qualche spigolo vivo: ordinamenti personalizzati, stabilità e una regola che, se la violi, ti restituisce undefined behavior invece di una risposta sbagliata.

Il cavallo di battaglia è std::sort da <algorithm>. Gli passi l'inizio e la fine di un intervallo, e lui riordina gli elementi sul posto in ordine crescente:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // crescente, sul posto

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

Non viene fatta alcuna copia: è il vector stesso a essere riordinato. Dietro le quinte std::sort è di solito un introsort (un quicksort che ripiega sull'heapsort), che ti dà O(n log n) in media. È quasi sempre più veloce e molto meno soggetto a errori che scriverti un ordinamento da solo.

Funziona anche sui semplici array C: descrivi l'intervallo con dei puntatori:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // oppure sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Ordine personalizzato con un comparatore

Per default std::sort ordina gli elementi con operator<. Per ordinare diversamente, passa un terzo argomento: un comparatore che riceve due elementi e restituisce true se il primo deve venire prima del secondo.

Una lambda è la scelta naturale. L'ordine decrescente è semplicemente a > b:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a prima di b" quando a è maggiore -> decrescente
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Per il caso comune dell'ordine decrescente sui tipi predefiniti, la libreria fornisce persino un comparatore pronto, greater<T>() da <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // come a > b

Il comparatore è anche il modo per ordinare in base a qualcosa di diverso dal valore stesso, per esempio ordinare stringhe per lunghezza invece che in ordine alfabetico:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // prima le parole più corte
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Ricevi i parametri del comparatore per const& per qualsiasi cosa più grande di un paio di byte (come string): copiare ogni elemento a ogni confronto è puro spreco.

Ordinare struct in base a un campo

Nei programmi reali di solito ordini collezioni di struct in base a uno dei loro campi. Il comparatore si limita ad accedere al campo che ti interessa. Qui ordiniamo le persone per età, dalla più giovane:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Nota che Linus e Dennis hanno entrambi 25 anni. Qui sono usciti nel loro ordine relativo originale, ma std::sort non lo garantisce. Se l'ordine relativo degli elementi uguali conta, usa std::stable_sort, che lo preserva (con un piccolo costo in prestazioni):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus resta prima di Dennis: il loro ordine di input viene preservato
    return 0;
}

Per risolvere le parità in modo voluto, per esempio ordinare per età e poi alfabeticamente per nome, confronta la chiave secondaria solo quando le chiavi primarie sono uguali. std::tie rende la cosa pulita:

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // età, poi nome
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis e Linus 25, in ordine alfabetico
    return 0;
}

La trappola dello strict weak ordering

È l'errore più pericoloso in assoluto nell'ordinamento in C++, perché non ti dà una risposta sbagliata: ti dà undefined behavior, che spesso significa un crash o una lettura fuori dai limiti.

std::sort richiede che il comparatore definisca uno strict weak ordering. La regola pratica: comp(x, x) deve essere false per qualsiasi elemento x. In altre parole, un elemento non viene mai "prima" di se stesso. È esattamente ciò che ti danno < e >, ed esattamente ciò che <= e >= violano:

// BUG: restituisce true quando a == b, violando lo strict weak ordering.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // undefined behavior: può andare in crash con certi input
});

Con <=, il comparatore sostiene che 5 viene prima di un altro 5, il che è contraddittorio. std::sort può allora far avanzare un puntatore oltre la fine dell'intervallo. Con input minuscoli a volte sembra funzionare, ed è questo che rende il bug terrificante: può superare i tuoi test e andare in crash in produzione. La soluzione è semplicemente <:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // corretto: false quando sono uguali
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Una seconda trappola classica: ordinare invalida tutto ciò che punta dentro l'intervallo. Iteratori, puntatori e indici salvati prima dell'ordinamento non si riferiscono più allo stesso elemento logico dopo, perché gli elementi si sono spostati. Ricalcola ogni posizione che ti serve dopo l'ordinamento, mai prima.

Ordinare una parte dell'intervallo

A volte non ti serve tutto ordinato: vuoi solo i primi elementi. Ordinare l'intero vector per leggerne i primi tre è uno spreco. std::partial_sort sistema solo gli elementi che chiedi e lascia il resto in un ordine non specificato, il che costa meno:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Mette i 3 più piccoli, in ordine, all'inizio. Il resto non è specificato.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

E se ti serve solo il singolo elemento che starebbe in una certa posizione, come la mediana, std::nth_element fa ancora meno lavoro: mette l'elemento giusto a quell'indice, con tutti i più piccoli prima e tutti i più grandi dopo, il tutto in O(n) in media.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Usali quando "completamente ordinato" è più di quanto il problema richieda davvero: su grandi quantità di dati fanno risparmiare tempo vero.

Prossimo passo: i template

Hai notato che lo stesso std::sort ha gestito int, string e la tua struct Person, e che greater<int>() poteva altrettanto facilmente essere greater<string>()? Questa generalità non è magia: sono i template, il meccanismo che permette a un unico pezzo di codice di funzionare con qualsiasi tipo che il chiamante vi inserisce. Nella prossima pagina vedremo come scrivere le tue funzioni e classi template, così il tuo codice potrà essere indipendente dai tipi quanto gli algoritmi che hai usato finora.

Domande frequenti

Come si ordina un vector in C++?

Includi <algorithm> e chiama sort(v.begin(), v.end()). Così gli elementi vengono ordinati sul posto in ordine crescente usando operator<. Per ordinare un array, passa arr e arr + n (oppure begin(arr) / end(arr)).

Come si ordina in modo decrescente in C++?

Passa un comparatore che restituisce a > b: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Puoi anche usare il comparatore predefinito sort(v.begin(), v.end(), greater<int>()); da <functional>.

Perché il mio comparatore C++ fa andare in crash std::sort?

Il comparatore deve definire uno strict weak ordering: deve restituire false quando i due argomenti sono uguali. Usare <= o >= (che restituiscono true per elementi uguali) viola questa regola ed è undefined behavior: std::sort può leggere fuori dai limiti e andare in crash. Confronta sempre con < o >.

Concetti correlati