Ordina vettore in C++

Per ordinare un std::vector in C++, chiama std::sort passando gli iteratori begin() ed end() del vettore. Per impostazione predefinita, gli elementi vengono ordinati usando operator<. Se un tipo richiede un criterio di ordinamento diverso, passa un comparatore che stabilisca se il primo argomento deve precedere il secondo.

Ordinare un vettore con std::sort

std::sort riordina gli elementi nell’intervallo semiaperto che parte dal primo iteratore e arriva fino al secondo, senza includerlo. Un std::vector fornisce gli iteratori ad accesso casuale richiesti dall’algoritmo. Includi <algorithm> per usare std::sort; l’esempio include anche <iostream> per stampare e <vector> per il contenitore. Se non passi un comparatore, l’algoritmo usa il criterio di ordinamento predefinito del tipo degli elementi, comunemente espresso da operator<.

Esegui questo esempio:

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> values{8, 3, 6, 1, 5};
  std::sort(values.begin(), values.end());

  for (std::size_t index = 0; index < values.size(); ++index) {
    if (index != 0) {
      std::cout << ' ';
    }
    std::cout << values[index];
  }
  std::cout << '\n';
}

1 3 5 6 8

Per ordinare l’intero vettore, usa lo stesso intervallo di iteratori; se vuoi ordinare solo una parte, passa gli iteratori che ne delimitano l’intervallo. L’intervallo deve essere valido e l’ultimo iteratore è escluso. Il blocco dei risultati mostra 1 3 5 6 8, senza un’etichetta Output:. L’ordinamento predefinito è utile per i numeri e per i tipi che definiscono già il criterio desiderato. Per i record, seleziona esplicitamente un campo con un comparatore.

Ordinare record con un comparatore lambda

Una lambda permette di tenere una breve regola di confronto accanto all’ordinamento che la usa. In questo esempio, i record Task vengono ordinati in base al campo priority. Il comparatore riceve due record e restituisce true quando il primo deve precedere il secondo. I parametri sono riferimenti a const perché il confronto non richiede di modificare i record.

Esegui questo esempio:

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Task {
  std::string name;
  int priority;
};

int main() {
  std::vector<Task> tasks{{"write", 3}, {"review", 1}, {"build", 2}};
  std::sort(tasks.begin(), tasks.end(),
            [](const Task& left, const Task& right) {
              return left.priority < right.priority;
            });

  for (const Task& task : tasks) {
    std::cout << task.name << ':' << task.priority << '\n';
  }
}

review:1
build:2
write:3

La regola di confronto deve definire un ordinamento debole stretto: deve comportarsi in modo coerente e un elemento non deve essere considerato precedente a sé stesso. Confrontare un campo intero usando < ordina le priorità in senso crescente. Invertendo gli operandi si cambia il verso dell’ordinamento. Se chiami di nuovo std::sort con un comparatore diverso, la nuova chiamata riordina l’intervallo corrente secondo il nuovo criterio; chiamate successive non combinano i criteri in un ordinamento basato su più campi. Quando servono più criteri, esprimi l’intera regola in un unico comparatore.

Usare un comparatore con nome per regole riutilizzabili

Quando la stessa regola viene usata in più punti, assegnale un nome. Un oggetto funzione con un operatore di chiamata const può essere passato a std::sort, proprio come una lambda. Questo esempio ordina le attività per nome, così il comparatore può essere riutilizzato ogni volta che serve quel criterio.

Esegui questo esempio:

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Task {
  std::string name;
  int priority;
};

struct ByName {
  bool operator()(const Task& left, const Task& right) const {
    return left.name < right.name;
  }
};

int main() {
  std::vector<Task> tasks{{"write", 3}, {"review", 1}, {"build", 2}};
  std::sort(tasks.begin(), tasks.end(), ByName{});

  for (const Task& task : tasks) {
    std::cout << task.name << ':' << task.priority << '\n';
  }
}

build:2
review:1
write:3

Un comparatore con nome è utile quando la sua logica merita un nome descrittivo o deve essere condivisa da più chiamate di ordinamento. Mantieni il criterio coerente con i dati e usa parametri come riferimenti a const per i confronti in sola lettura. Per confrontare un singolo campo una tantum, di solito una lambda è più diretta. In entrambi i casi, è il comparatore a determinare l’ordine; il criterio predefinito operator< viene usato solo se non viene fornito alcun comparatore.