Introduction aux algorithmes de la STL
Un algorithme est une procédure de résolution d'une classe de problèmes. La STL contient une multitude d'algorithmes que vous pouvez utiliser dans vos programmes.
Étant donné que de nombreuses personnes très intelligentes ont consacré beaucoup de temps à s'assurer que ces algorithmes sont corrects et efficaces, vous ne devriez généralement pas essayer, par exemple, d'écrire votre propre algorithme de tri.
L'utilisation d'algorithmes de la bibliothèque STL permet d'économiser du temps, des efforts, du code et est très fiable.
STL fournit différents types d'algorithmes qui peuvent être implémentés sur n'importe quel conteneur à l'aide d'itérateurs. Ainsi, nous n'avons plus besoin de définir des algorithmes complexes, mais nous utilisons simplement les fonctions intégrées fournies par la bibliothèque d'algorithmes STL.
L'en-tête <algorithm> définit une collection de fonctions spécialement conçues pour être utilisées sur des collections.
Une collection est une séquence d'objets accessible via des itérateurs ou des pointeurs, comme un tableau ou une instance de certains des conteneurs STL (vector, deque, list, etc.).
Notez cependant que les algorithmes fonctionnent via des itérateurs directement sur les valeurs, n'affectant en aucune façon la structure de tout conteneur possible (cela n'affecte jamais la taille ou l'allocation de stockage du conteneur).
Types d'algorithmes
Algorithmes de tri
sort, stable_sort, partial_sort, nth_element, etc.
Algorithmes de recherche dichotomique
binary_search, lower_bound, upper_bound, equal_range
Algorithmes en lecture seule
find, find_if, count, for_each, all_of, any_of, none_of
Algorithmes de lecture-écriture
copy, fill, generate, transform, replace, remove
Algorithmes numériques
accumulate, partial_sum, adjacent_difference, iota
Minimum et maximum
min, max, minmax, min_element, max_element
Politiques d'exécution (C++17 et ultérieur)
Certains algorithmes, ceux que l'on appelle communément algorithmes parallèles, peuvent diviser un problème afin que des entités indépendantes puissent travailler simultanément sur différentes parties du problème.
De nombreux algorithmes STL vous permettent de spécifier le parallélisme avec une politique d'exécution. Une politique d'exécution indique le parallélisme autorisé pour un algorithme.
Du point de vue de la STL, un algorithme peut être exécuté :
- Séquentiellement : une seule entité travaille sur le problème à la fois.
- En parallèle : de nombreuses entités travaillent de concert pour résoudre le problème.
De plus, les algorithmes parallèles peuvent être :
- Vectorisés : permettent aux entités d'effectuer des travaux dans un ordre non spécifié, permettant même à une seule entité de travailler simultanément sur plusieurs parties du problème.
- Non vectorisés : ordre d'exécution plus contraint.
Un algorithme qui nécessite une synchronisation entre les entités est généralement non vectorisable car la même entité peut tenter d'acquérir un verrou plusieurs fois, entraînant un blocage.
Les trois politiques d'exécution
Trois politiques d'exécution existent dans l'en-tête <execution> :
| Politique | Description | Utilisation |
|---|---|---|
| std::execution::seq | Exécution séquentielle (non parallèle) | Comportement par défaut |
| std::execution::par | Exécution parallèle (multi-thread) | Algorithmes parallélisables |
| std::execution::par_unseq | Exécution parallèle et vectorisée | Algorithmes pouvant être vectorisés |
Pour les algorithmes qui prennent en charge une politique d'exécution, la valeur par défaut est seq, ce qui signifie que vous devez opter pour le parallélisme et les avantages de performances associés.
La norme C++ ne précise pas la signification précise de ces politiques d'exécution car différentes plates-formes gèrent le parallélisme différemment.
Lorsque vous fournissez une politique d'exécution non séquentielle, vous déclarez simplement que "cet algorithme peut être parallélisé en toute sécurité".
Exemple d'utilisation des politiques d'exécution
#include <algorithm>
#include <execution>
#include <vector>
int main() {
std::vector<int> v = {9, 4, 1, 5, 7, 3, 8, 2, 6};
// Tri séquentiel (explicite)
std::sort(std::execution::seq, v.begin(), v.end());
// Tri parallèle
std::sort(std::execution::par, v.begin(), v.end());
// Tri parallèle et vectorisé
std::sort(std::execution::par_unseq, v.begin(), v.end());
return 0;
}Explication :
std::execution::seq: version classique, une seule thread.std::execution::par: le compilateur peut paralléliser le tri sur plusieurs threads.std::execution::par_unseq: permet en plus la vectorisation (instructions SIMD).
Avantages des algorithmes STL
Les algorithmes STL sont testés et éprouvés par des milliers de développeurs. Ils sont corrects et robustes.
Optimisés par des experts, ils offrent souvent les meilleures performances possibles (tri en O(N log N), etc.).
Fonctionnent avec tous les conteneurs STL via les itérateurs. Un même algorithme fonctionne sur vector, deque, list, etc.
Le code utilisant les algorithmes STL est plus expressif et plus facile à comprendre que des boucles manuelles.
Depuis C++17, possibilité d'utiliser le parallélisme simplement en ajoutant une politique d'exécution.
Moins de risques d'erreurs (dépassements, off-by-one) par rapport à des implémentations manuelles.
Identifier le bon en-tête
Pour chacun des algorithmes suivants, indiquez quel en-tête il faut inclure et à quelle catégorie il appartient :
std::sort()std::find()std::accumulate()std::lower_bound()std::min()std::for_each()
Question bonus : Que faut-il ajouter pour utiliser la version parallèle de std::sort() ?
| Algorithme | En-tête | Catégorie |
|---|---|---|
std::sort() | <algorithm> | Tri |
std::find() | <algorithm> | Lecture seule |
std::accumulate() | <numeric> | Numérique |
std::lower_bound() | <algorithm> | Recherche dichotomique |
std::min() | <algorithm> | Min/Max |
std::for_each() | <algorithm> | Lecture seule |
Question bonus : Pour utiliser la version parallèle, il faut :
- Inclure l'en-tête
<execution> - Ajouter une politique d'exécution en premier paramètre :
std::execution::seq(séquentiel)std::execution::par(parallèle)std::execution::par_unseq(parallèle et vectorisé)
#include <algorithm>
#include <execution>
#include <vector>
std::vector<int> v = {9, 4, 1, 5, 7, 3, 8, 2, 6};
std::sort(std::execution::par, v.begin(), v.end()); // version parallèle- Les algorithmes STL sont des fonctions prêtes à l'emploi, testées et optimisées.
- Ils sont définis principalement dans l'en-tête <algorithm> (et <numeric> pour les algorithmes numériques).
- Ils fonctionnent sur des collections via des itérateurs, indépendamment du type de conteneur.
- Six grandes catégories : tri, recherche dichotomique, lecture seule, lecture-écriture, numérique, min/max.
- Depuis C++17, on peut spécifier une politique d'exécution pour le parallélisme.
- Trois politiques : seq (séquentiel), par (parallèle), par_unseq (parallèle et vectorisé).
- L'utilisation d'algorithmes STL rend le code plus fiable, lisible et performant.
- Il est généralement déconseillé de réinventer la roue en implémentant ses propres algorithmes de base.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.