Bibliothèque d'algorithmes
La bibliothèque d'algorithmes définit des fonctions pour divers usages (par exemple recherche, tri, comptage, manipulation) qui opèrent sur des plages d'éléments.
Algorithmes contraints (depuis C++20)
C++20 fournit des versions contraintes de la plupart des algorithmes dans l'espace de noms std::ranges. Dans ces algorithmes, un intervalle peut être spécifié soit comme une paire itérateur-sentinelle, soit comme un seul argument intervalle, et les projections et les appelables par pointeur sur membre sont pris en charge. De plus, les types de retour de la plupart des algorithmes ont été modifiés pour renvoyer toutes les informations potentiellement utiles calculées lors de l'exécution de l'algorithme.
std::vector<int> v{7, 1, 4, 0, -1};
std::ranges::sort(v); // constrained algorithm
Algorithmes parallèles (depuis C++17)
Un algorithme parallèle est un modèle de fonction dans la bibliothèque d'algorithmes avec un paramètre de modèle nommé ExecutionPolicy ou contraint par execution-policy (depuis C++26). Un tel paramètre de modèle est appelé un paramètre de modèle de politique d'exécution , il décrit la manière dont l'exécution d'un algorithme parallèle peut être parallélisée.
Sauf indication contraire, les algorithmes parallèles sont autorisés à faire des copies arbitraires d'éléments des plages, tant que std::is_trivially_copy_constructible_v<T> et std::is_trivially_destructible_v<T> sont true, où T est le type des éléments.
Politiques d'exécution
Les algorithmes de la bibliothèque standard supportent plusieurs politiques d'exécution, et la bibliothèque fournit des types et des objets de politique d'exécution correspondants. Les utilisateurs peuvent sélectionner une politique d'exécution de manière statique en invoquant un algorithme parallèle avec un objet de politique d'exécution du type correspondant.
Les implémentations de la bibliothèque standard (mais pas les utilisateurs) peuvent définir des politiques d'exécution supplémentaires comme extension. La sémantique des algorithmes parallèles invoqués avec un objet de politique d'exécution de type défini par l'implémentation est définie par l'implémentation.
Défini dans l'en-tête
<execution> | |
Défini dans l'espace de noms
std::execution | |
(C++17)(C++17)(C++17)(C++20) |
types de politique d'exécution (classe) |
(C++17)(C++17)(C++17)(C++20) |
objets globaux de politique d'exécution (constante) |
Défini dans l'espace de noms
std | |
(C++17) |
teste si une classe représente une politique d'exécution (modèle de classe) |
(C++26) |
spécifie qu'un type représente une politique d'exécution (concept d'exposition uniquement*) |
Opérations de séquence non modifiantes
Opérations par lots
Défini dans l'en-tête
<algorithm> | |
| applique un objet fonction unaire aux éléments d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++17) |
applique un objet fonction aux N premiers éléments d'une séquence (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
Opérations de recherche
Défini dans l'en-tête
<algorithm> | |
(C++11)(C++11)(C++11) |
vérifie si un prédicat est true pour tous, certains ou aucun des éléments d'une plage(modèle de fonction & objet fonction d'algorithme) |
(C++20)(C++20)(C++20) |
|
(C++23)(C++23) |
vérifie si la plage contient l'élément ou la sous-plage donné (objet fonction d'algorithme) |
(C++11) |
trouve le premier élément satisfaisant des critères spécifiques (modèle de fonction & objet fonction d'algorithme) |
(C++20)(C++20)(C++20) |
|
(C++23)(C++23)(C++23) |
trouve le dernier élément satisfaisant des critères spécifiques (objet fonction d'algorithme) |
| trouve la dernière séquence d'éléments dans une plage donnée (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| recherche l'un des éléments d'un ensemble (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| trouve les deux premiers éléments adjacents qui sont égaux (ou satisfont un prédicat donné) (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| retourne le nombre d'éléments satisfaisant des critères spécifiques (modèle de fonction & objet fonction d'algorithme) | |
(C++20)(C++20) |
|
| trouve la première position où deux plages diffèrent (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| détermine si deux ensembles d'éléments sont identiques (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| recherche la première occurrence d'une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| recherche la première occurrence d'un nombre de copies consécutives d'un élément dans une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++23) |
vérifie si une plage commence par une autre plage (objet fonction d'algorithme) |
(C++23) |
vérifie si une plage se termine par une autre plage (objet fonction d'algorithme) |
Opérations de repli (depuis C++23)
|
Défini dans l'en-tête
<algorithm>
|
|
|
(C++23)
|
réduit à gauche une plage d'éléments
(objet fonction algorithme) |
|
(C++23)
|
réduit à gauche une plage d'éléments en utilisant le premier élément comme valeur initiale
(objet fonction algorithme) |
|
(C++23)
|
réduit à droite une plage d'éléments
(objet fonction algorithme) |
|
(C++23)
|
réduit à droite une plage d'éléments en utilisant le dernier élément comme valeur initiale
(objet fonction algorithme) |
|
(C++23)
|
réduit à gauche une plage d'éléments et retourne une
paire
(itérateur, valeur)
(objet fonction algorithme) |
|
réduit à gauche une plage d'éléments en utilisant le premier élément comme valeur initiale et retourne une
paire
(itérateur,
optional
)
(objet fonction algorithme) |
|
Opérations de modification de séquence
Opérations de copie
Défini dans l'en-tête
<algorithm> | |
(C++11) |
copie une plage d'éléments vers un nouvel emplacement (modèle de fonction & objet fonction d'algorithme) |
(C++20)(C++20) |
|
(C++11) |
copie un nombre d'éléments vers un nouvel emplacement (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
| copie une plage d'éléments en ordre inverse (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++11) |
déplace une plage d'éléments vers un nouvel emplacement (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
(C++11) |
déplace une plage d'éléments vers un nouvel emplacement en ordre inverse (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
Opérations d'échange
Défini dans l'en‑tête
<algorithm> (jusqu'à C++11) | |
Défini dans l'en‑tête
<utility> (depuis C++11) | |
Défini dans l'en‑tête
<string_view> | |
| échange les valeurs de deux objets (modèle de fonction) | |
Défini dans l'en‑tête
<algorithm> | |
| échange deux plages d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| échange les éléments pointés par deux itérateurs (modèle de fonction) | |
Opérations de transformation
Définie dans l'en-tête
<algorithm> | |
| applique une fonction à une plage d'éléments, stockant les résultats dans une plage de destination (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| remplace toutes les valeurs satisfaisant à des critères spécifiques par une autre valeur (modèle de fonction & objet fonction d'algorithme) | |
(C++20)(C++20) |
|
| copie une plage, en remplaçant les éléments satisfaisant à des critères spécifiques par une autre valeur (modèle de fonction & objet fonction d'algorithme) | |
(C++20)(C++20) |
|
Opérations de génération
Défini dans l'en-tête
<algorithm> | |
| copie-assigne la valeur donnée à chaque élément d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| copie-assigne la valeur donnée à N éléments d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| assigne les résultats d'appels de fonction successifs à chaque élément d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| assigne les résultats d'appels de fonction successifs à N éléments d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
Opérations de suppression
Défini dans l'en-tête
<algorithm> | |
| supprime les éléments satisfaisant des critères spécifiques (modèle de fonction & objet fonction d'algorithme) | |
(C++20)(C++20) |
|
| copie une plage d'éléments en omettant ceux qui satisfont des critères spécifiques (modèle de fonction & objet fonction d'algorithme) | |
(C++20)(C++20) |
|
| supprime les éléments consécutifs en double dans une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| crée une copie d'une plage d'éléments ne contenant aucun doublon consécutif (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
Opérations modifiant l'ordre
Définie dans l'en-tête
<algorithm> | |
| inverse l'ordre des éléments dans une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| crée une copie inversée d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| fait pivoter l'ordre des éléments dans une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| copie et fait pivoter une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++20)(C++20) |
décale les éléments dans une plage (modèle de fonction & objet fonction d'algorithme) |
(C++23)(C++23) |
|
(jusqu'à C++17)(C++11) |
réorganise aléatoirement les éléments dans une plage (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
Opérations d'échantillonnage
Défini dans l'en-tête
<algorithm> | |
(C++17) |
sélectionne N éléments aléatoires d'une séquence (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
Exigences
Certains algorithmes exigent que la séquence représentée par les arguments soit « triée » ou « partitionnée ». Le comportement est indéfini si l'exigence n'est pas satisfaite.
|
Une séquence est triée par rapport à un comparateur |
(jusqu'à C++20) |
|
Une séquence est triée par rapport à Une séquence est triée par rapport à un comparateur |
(depuis C++20) |
Une séquence [start, finish) est partitionnée par rapport à une expression f(e) s'il existe un entier n tel que pour tout i dans [0, std::distance(start, finish)), f(*(start + i))[1] est true si et seulement si i < n.
Opérations de partitionnement
Défini dans l'en-tête
<algorithm> | |
(C++11) |
détermine si la plage est partitionnée selon le prédicat donné (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
| divise une plage d'éléments en deux groupes (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++11) |
copie une plage en divisant les éléments en deux groupes (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
| divise les éléments en deux groupes tout en conservant leur ordre relatif au sein de chaque groupe (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++11) |
localise le point de partitionnement d'une plage partitionnée (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
Opérations de tri
Définie dans l'en-tête
<algorithm> | |
| trie une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| trie une plage d'éléments tout en préservant l'ordre relatif des éléments équivalents (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| trie les N premiers éléments d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| copie et trie partiellement une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++11) |
vérifie si une plage est triée (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
(C++11) |
trouve la plus grande sous-plage triée (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
| trouve le N-ième élément si la plage était triée (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
Opérations de recherche binaire (sur des plages partitionnées)
Défini dans l'en-tête
<algorithm> | |
| trouve le premier élément non inférieur à la valeur donnée en utilisant la recherche binaire (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| trouve le premier élément supérieur à la valeur donnée en utilisant la recherche binaire (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| trouve la plage d'éléments correspondant à la valeur donnée en utilisant la recherche binaire (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| détermine si un élément existe dans une plage en utilisant la recherche binaire (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
Opérations sur les ensembles (sur des plages triées)
Défini dans l'en-tête
<algorithm> | |
| détermine si une séquence est une sous-séquence d'une autre (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| calcule l'union de deux ensembles (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| calcule l'intersection de deux ensembles (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| calcule la différence entre deux ensembles (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| calcule la différence symétrique entre deux ensembles (modèle de fonction & objet fonction d'algorithme) | |
Opérations de fusion (sur des plages triées)
Défini dans l'en-tête
<algorithm> | |
| fusionne deux plages triées (modèle de fonction & objet de fonction d'algorithme) | |
(C++20) |
|
| fusionne deux plages ordonnées en place (modèle de fonction & objet de fonction d'algorithme) | |
(C++20) |
|
Opérations sur les tas
|
Une plage à accès aléatoire |
(jusqu'à C++20) |
|
Une plage à accès aléatoire Une plage à accès aléatoire |
(depuis C++20) |
Un tas peut être créé par std::make_heap et ranges::make_heap(depuis C++20).
Pour plus de propriétés du tas, voir tas max.
Défini dans l'en-tête
<algorithm> | |
| ajoute un élément à un tas max (modèle de fonction & objet de fonction d'algorithme) | |
(C++20) |
|
| supprime le plus grand élément d'un tas max (modèle de fonction & objet de fonction d'algorithme) | |
(C++20) |
|
| crée un tas max à partir d'une plage d'éléments (modèle de fonction & objet de fonction d'algorithme) | |
(C++20) |
|
| transforme un tas max en une plage d'éléments triés en ordre croissant (modèle de fonction & objet de fonction d'algorithme) | |
(C++20) |
|
(C++11) |
vérifie si la plage donnée est un tas max (modèle de fonction & objet de fonction d'algorithme) |
(C++20) |
|
(C++11) |
trouve la plus grande sous-plage qui est un tas max (modèle de fonction & objet de fonction d'algorithme) |
(C++20) |
|
Opérations de minimum/maximum
Défini dans l'en-tête
<algorithm> | |
| renvoie la plus grande des valeurs données (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| renvoie le plus grand élément d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| renvoie la plus petite des valeurs données (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| renvoie le plus petit élément d'une plage (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++11) |
renvoie le plus petit et le plus grand de deux éléments (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
(C++11) |
renvoie le plus petit et le plus grand éléments d'une plage (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
(C++17) |
limite une valeur entre une paire de valeurs limites (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
Opérations de comparaison lexicographique
Définie dans l'en-tête
<algorithm> | |
| compare deux plages lexicographiquement (gabarit de fonction & objet fonction d'algorithme) | |
| compare deux plages en utilisant la comparaison à trois voies (gabarit de fonction) | |
Opérations de permutation
Défini dans l'en-tête
<algorithm> | |
| génère la permutation lexicographique immédiatement supérieure d'une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| génère la permutation lexicographique immédiatement inférieure d'une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++11) |
détermine si une séquence est une permutation d'une autre séquence (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
Opérations numériques
Définie dans l'en-tête
<numeric> | |
(C++11) |
remplit une plage avec des incréments successifs de la valeur de départ (modèle de fonction & objet de fonction d'algorithme) |
(C++23) |
|
| additionne ou plie une plage d'éléments (modèle de fonction) | |
| calcule le produit scalaire de deux plages d'éléments (modèle de fonction) | |
| calcule les différences entre éléments adjacents dans une plage (modèle de fonction) | |
| calcule la somme partielle d'une plage d'éléments (modèle de fonction) | |
(C++17) |
similaire à std::accumulate, sauf dans le désordre (modèle de fonction) |
(C++17) |
similaire à std::partial_sum, exclut le ith élément d'entrée de la ith somme (modèle de fonction) |
(C++17) |
similaire à std::partial_sum, inclut le ith élément d'entrée dans la ith somme (modèle de fonction) |
(C++17) |
applique un invocable, puis réduit dans le désordre (modèle de fonction) |
(C++17) |
applique un invocable, puis calcule le balayage exclusif (modèle de fonction) |
(C++17) |
applique un invocable, puis calcule le balayage inclusif (modèle de fonction) |
Spécialisés <memory> algorithmes
Algorithmes spécialisés <random> algorithmes (depuis C++26)
Défini dans l'en-tête
<random> | |
(C++26) |
remplit une plage avec des nombres aléatoires provenant d'un générateur de bits aléatoires uniforme (objet fonction d'algorithme) |
Notes
| Macro de test de fonctionnalité | Valeur | Std | Fonctionnalité |
|---|---|---|---|
__cpp_lib_algorithm_iterator_requirements
|
202207L
|
(C++23) | Itérateurs Ranges en entrée des algorithmes non-Ranges |
__cpp_lib_clamp
|
201603L
|
(C++17) | std::clamp |
__cpp_lib_constexpr_algorithms
|
201806L
|
(C++20) | Constexpr pour les algorithmes |
202306L
|
(C++26) | Tri stable constexpr | |
__cpp_lib_algorithm_default_value_type
|
202403L
|
(C++26) | Initialisation par liste pour les algorithmes |
__cpp_lib_freestanding_algorithm
|
202311L
|
(C++26) | Fonctionnalités autonomes dans <algorithm> |
__cpp_lib_robust_nonmodifying_seq_ops
|
201304L
|
(C++14) | Rendre les opérations de séquence non modifiantes plus robustes (surcharges à deux plages pour std::mismatch , std::equal et std::is_permutation) |
__cpp_lib_sample
|
201603L
|
(C++17) | std::sample |
__cpp_lib_shift
|
201806L
|
(C++20) | std::shift_left et std::shift_right |
Bibliothèque C
|
Défini dans l'en-tête
<cstdlib>
|
|
|
trie une plage d'éléments de type non spécifié
(fonction) |
|
|
recherche un élément de type non spécifié dans un tableau
(fonction) |
|
Rapports de défauts
Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.
| DR | Appliqué à | Comportement publié | Comportement corrigé |
|---|---|---|---|
| LWG 193 | C++98 | le tas exigeait que * first soit le plus grand élément |
il peut y avoir des éléments
égaux à * first |
| LWG 2150 | C++98 | la définition d'une séquence triée était incorrecte | corrigée |
| LWG 2166 | C++98 |
l'exigence de tas ne correspondait pas
suffisamment à la définition du tas maximum |
exigence améliorée |
Voir aussi
|
Documentation C
pour
Algorithms
|