Utiliser sort() dans la bibliothèque C++ std

Introduction

La fonction sort, intégrée à la bibliothèque standard de C++, offre la capacité de classer les éléments d’un conteneur, qu’il s’agisse d’un ordre ascendant ou descendant. Cette fonctionnalité, définie dans l’en-tête <algorithm>, requiert jusqu’à trois paramètres :

• Un itérateur signalant le début de la plage à traiter.
• Un itérateur indiquant la fin de cette même plage.
• Un comparateur binaire, paramètre optionnel.

Par défaut, sort emploie l’opérateur < pour un tri en ordre croissant. Cependant, il est possible de personnaliser le tri en fournissant un comparateur adapté à des critères spécifiques.

Présentation de la syntaxe

La structure de base de l’appel à sort est la suivante :

cpp
void sort(IterateurDebut, IterateurFin);


Où :

• IterateurDebut désigne un itérateur pointant vers le premier élément à inclure dans le processus de tri.
• IterateurFin est un itérateur qui référence la position juste après le dernier élément à trier.

Il est également possible de spécifier un comparateur binaire pour ajuster le comportement du tri :

cpp
void sort(IterateurDebut, IterateurFin, Comparateur);


Où :

• Comparateur est une instance de std::function<bool(Type1, Type2)> qui définit la logique du tri.

Quelques exemples concrets

Voici quelques illustrations de l’utilisation de la fonction sort :

Tri d’un tableau d’entiers par ordre croissant

cpp
int tableau[] = {5, 3, 1, 2, 4};
std::sort(tableau, tableau + 5);


Tri d’une liste de chaînes de caractères par ordre alphabétique inversé

cpp
std::list<std::string> liste = {"Pomme", "Banane", "Cerise", "Datte"};
std::sort(liste.begin(), liste.end(), [](const std::string& a, const std::string& b) { return a > b; });


Tri d’une collection de paires clé-valeur par clé

cpp
std::map<std::string, int> map = {{"Pomme", 5}, {"Banane", 3}, {"Cerise", 1}, {"Datte", 2}};
std::sort(map.begin(), map.end(), [](const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) { return a.first < b.first; });


Fonctions apparentées

La bibliothèque std propose plusieurs autres fonctions de tri, en plus de sort :

• std::partial_sort : Trie partiellement une plage donnée.
• std::stable_sort : Assure un tri stable, maintenant l’ordre des éléments équivalents.
• std::is_sorted : Permet de vérifier si une plage est déjà triée.
• std::sort_heap : Trie une plage en utilisant un algorithme de tas.

Conclusion

La fonction sort se présente comme un outil efficace pour l’ordonnancement des éléments au sein d’un conteneur selon une logique spécifique. Sa simplicité d’utilisation la rend adaptée au tri de différents types de données. En la combinant avec les autres fonctions de tri fournies par la bibliothèque std, on peut réaliser des opérations de tri d’une grande complexité de manière efficace dans les programmes C++.

Questions fréquentes

1. Comment trier un tableau d’objets par ordre croissant sur la base d’un membre ?

Il suffit de fournir une fonction lambda en tant que comparateur, qui comparera les objets via le membre spécifique :

cpp
std::sort(tableau, tableau + 5, [](const Objet& a, const Objet& b) { return a.membre < b.membre; });


2. Comment réaliser un tri stable sur une plage ?

Utilisez std::stable_sort, qui préserve l’ordre relatif des éléments de valeur égale :

cpp
std::stable_sort(tableau, tableau + 5);


3. Comment déterminer si une plage est déjà triée ?

Employez la fonction std::is_sorted à cet effet :

cpp
if (std::is_sorted(tableau, tableau + 5)) {
// La plage est triée
}


4. Comment trier une plage à l’aide d’un algorithme de tas ?

Utilisez std::sort_heap pour effectuer un tri par tas :

cpp
std::sort_heap(tableau, tableau + 5);


5. Comment trier une plage par ordre décroissant ?

Adoptez std::greater comme comparateur, ce qui inversera l’ordre :

cpp
std::sort(tableau, tableau + 5, std::greater<int>());


6. Comment trier sur la base de plusieurs critères ?

Vous pouvez définir un comparateur personnalisé qui prend en compte plusieurs facteurs :

cpp
struct Comparateur {
bool operator()(const Objet& a, const Objet& b) {
if (a.critère1 == b.critère1) {
return a.critère2 < b.critère2;
}
return a.critère1 < b.critère1;
}
};

std::sort(tableau, tableau + 5, Comparateur());

7. Comment inverser l’ordre d’une plage triée ?

Après le tri, utilisez std::reverse pour inverser l’ordre :

cpp
std::sort(tableau, tableau + 5);
std::reverse(tableau, tableau + 5);


8. Comment gérer les éléments manquants lors du tri ?

Utilisez std::remove pour retirer les éléments indésirables avant de procéder au tri :

cpp
std::remove_if(tableau, tableau + 5, [](const int& élément) { return élément == std::numeric_limits<int>::max(); });
std::sort(tableau, tableau + 5);