Partager via

<algorithm>

  • Article

Définit les fonctions de modèle du conteneur de bibliothèque C++ Standard qui exécutent des algorithmes.

Syntaxe

(see links below for specific algorithm syntax)

Remarque

La <algorithm> bibliothèque utilise également l’instruction #include <initializer_list> .

Notes

Les algorithmes de bibliothèque standard C++ peuvent fonctionner sur différentes structures de données. Les structures de données sur lesquelles ils peuvent fonctionner incluent non seulement les classes de conteneur de bibliothèque standard C++ telles que vector et list, mais également les structures de données définies par l’utilisateur et les tableaux d’éléments, tant qu’elles répondent aux exigences d’un algorithme particulier. Ces algorithmes de la bibliothèque C++ Standard atteignent ce niveau de généralité en parcourant les éléments d’un conteneur indirectement via des itérateurs.

Les algorithmes de la bibliothèque C++ Standard traitent des plages d’itérateurs qui sont généralement spécifiées par leur position de début ou de fin. Les plages référencées doivent être valides dans le sens où tous les itérateurs des plages doivent être déréférencementables et, dans les séquences de chaque plage, la dernière position doit être accessible à partir du premier en incrémentant l’itérateur.

À compter de C++20, la plupart des algorithmes définis sont <algorithm> également disponibles dans un formulaire qui prend un range. Par exemple, plutôt que d’appeler sort(v1.begin(), v1.end(), greater<int>());, vous pouvez appeler ranges::sort(v1, greater<int>());

Les algorithmes de bibliothèque standard C++ peuvent utiliser différents types d’objets conteneur en même temps. Deux suffixes ont été utilisés pour transmettre des informations sur l’objectif des algorithmes :

  • Le _if suffixe indique que l’algorithme est utilisé avec des objets de fonction qui opèrent sur les valeurs des éléments plutôt que sur les éléments eux-mêmes. Par exemple, l’algorithme find_if recherche des éléments dont les valeurs répondent au critère spécifié par un objet de fonction, tandis que l’algorithme find recherche une valeur particulière.

  • Le _copy suffixe indique que l’algorithme modifie généralement les valeurs copiées au lieu de copier des valeurs modifiées. En d’autres termes, ils ne modifient pas les éléments de la plage source, mais placent les résultats dans une plage de sortie/itérateur. Par exemple, l’algorithme reverse inverse l’ordre des éléments dans une plage, tandis que l’algorithme reverse_copy copie le résultat inversé dans une plage de destination.

Les algorithmes de bibliothèque standard C++ sont souvent classés en groupes pour indiquer leur objectif ou leurs exigences. Il s’agit notamment de modifier des algorithmes qui modifient la valeur des éléments par rapport aux algorithmes qui ne modifient pas. Les algorithmes de mutation modifient l'ordre des éléments, mais pas leurs valeurs. Les algorithmes de suppression peuvent éliminer les éléments d'une plage ou d'une copie d'une plage. Les algorithmes de tri réorganisent les éléments d’une plage de différentes façons et les algorithmes de plage triés agissent uniquement sur les plages dont les éléments ont été triés d’une manière particulière.

Les algorithmes numériques de la bibliothèque standard C++ fournis pour le traitement numérique ont leur propre fichier d’en-tête <numeric>, et les objets de fonction et les adaptateurs sont définis dans l’en-tête <functional>. Les objets de fonction qui retournent des valeurs booléennes sont appelés prédicats. Le prédicat binaire par défaut est le operator< de comparaison. En général, les éléments classés doivent être inférieurs à comparables afin que, compte tenu de deux éléments, il peut être déterminé qu’ils sont équivalents (dans le sens où aucun n’est inférieur à l’autre) ou qu’un élément est inférieur à l’autre. Cela entraîne un tri des éléments non équivalents.

Algorithmes

Nom Description
adjacent_find Recherche deux éléments adjacents qui ont la même valeur ou qui répondent à une condition spécifiée.
all_of Retourne true lorsqu'une condition est remplie pour chaque élément de la plage spécifiée.
any_of Retourne true lorsqu'une condition est remplie au moins une fois dans la plage d'éléments spécifiée.
binary_search Teste si un élément d’une plage triée est égal à une valeur spécifiée ou équivalent, selon une condition spécifiée par un prédicat binaire.
clamp
copy Assigne les valeurs des éléments d'une plage source à une plage de destination, en procédant à une itération via la séquence source d'éléments et en leur assignant de nouvelles positions, du haut vers le bas.
copy_backward Assigne les valeurs des éléments d'une plage source à une plage de destination, en procédant à une itération via la séquence source d'éléments et en leur assignant de nouvelles positions vers le haut.
copy_if Copie tous les éléments d'une plage donnée qui testent true pour une condition spécifiée.
copy_n Copie un nombre spécifié d'éléments.
count Retourne le nombre d'éléments d'une plage dont les valeurs correspondent à une valeur spécifiée.
count_if Retourne le nombre d'éléments d'une plage dont les valeurs correspondent à une condition spécifiée.
equal Compare deux plages, élément par élément, à la recherche d’une égalité ou d’une équivalence, selon une condition spécifiée par un prédicat binaire.
equal_range Recherche une paire de positions dans une plage triée. La première inférieure ou équivalente à la position d’un élément spécifié, et la deuxième supérieure à la position de cet élément. L’équivalence ou le tri utilisés pour établir des positions dans la séquence peuvent être spécifiés par un prédicat binaire.
fill Affecte la même nouvelle valeur à chaque élément d'une plage spécifiée.
fill_n Assigne une nouvelle valeur à un nombre spécifié d'éléments d'une plage qui commence par un élément particulier.
find Recherche la position de la première occurrence d'un élément d'une plage ayant une valeur spécifiée.
find_end Recherche dans une plage la dernière sous-séquence qui est identique à une séquence spécifiée ou qui est équivalente, selon une condition spécifiée par un prédicat binaire.
find_first_of Recherche la première occurrence parmi plusieurs valeurs d’une plage cible, ou la première occurrence parmi plusieurs éléments qui sont équivalents, selon une condition spécifiée par un prédicat binaire, à un ensemble d’éléments spécifiés.
find_if Recherche la position de la première occurrence d'un élément d'une plage qui répond à une condition spécifiée.
find_if_not Retourne le premier élément de la plage indiquée qui ne satisfait pas à une condition.
for_each Applique un objet de fonction spécifié à chaque élément d'une plage, du haut vers le bas, et retourne l'objet de la fonction.
for_each_n
generate Assigne les valeurs générées par un objet de fonction à chaque élément d'une plage.
generate_n Assigne les valeurs générées par un objet de fonction à un nombre spécifié d'éléments d'une plage et retourne à la position située juste après la dernière valeur assignée.
includes Teste si une plage triée contient tous les éléments d’une autre plage triée. Le critère de tri ou d’équivalence entre les éléments peut être spécifié par un prédicat binaire.
inplace_merge Regroupe les éléments de deux plages triées consécutives au sein d’une même plage triée. Le critère de tri peut être spécifié par un prédicat binaire.
is_heap Retourne true si les éléments d'une plage spécifiée forment un tas.
is_heap_until Retourne true si la plage spécifiée forme un tas jusqu'au dernier élément.
is_partitioned Retourne true si tous les éléments d'une plage qui testent true pour une condition donnée, se trouvent avant les éléments qui testent false.
is_permutation Détermine si les éléments d'une plage donnée forment une permutation valide.
is_sorted Retourne true si les éléments de la plage spécifiée sont triés.
is_sorted_until Retourne true si les éléments de la plage spécifiée sont triés.
iter_swap Échange deux valeurs référencées par une paire d'itérateurs spécifiés.
lexicographical_compare Compare deux séquences, élément par élément, pour déterminer lequel est inférieur à l'autre.
lower_bound Recherche la position du premier élément d’une plage triée dont la valeur est supérieure ou équivalente à une valeur spécifiée. Le critère de tri peut être spécifié par un prédicat binaire.
make_heap Convertit les éléments d’une plage spécifiée en un tas, dans lequel le premier élément est le plus grand, et pour lequel un critère de tri peut être spécifié à l’aide d’un prédicat binaire.
max Compare deux objets et retourne le plus grand des deux. Un critère de tri peut être spécifié à l’aide d’un prédicat binaire.
max_element Recherche la première occurrence du plus grand élément dans une plage spécifiée. Un critère de tri peut être spécifié par un prédicat binaire.
merge Regroupe tous les éléments de deux plages sources triées au sein d’une même plage de destination triée. Le critère de tri peut être spécifié par un prédicat binaire.
min Compare deux objets et retourne le plus petit des deux. Un critère de tri peut être spécifié à l’aide d’un prédicat binaire.
min_element Recherche la première occurrence du plus petit élément dans une plage spécifiée. Un critère de tri peut être spécifié par un prédicat binaire.
minmax Compare deux paramètres d'entrée et les retourne en tant que paire, du plus petit au plus grand.
minmax_element Exécute le travail effectué par min_element et max_element au sein d’un même appel.
mismatch Compare deux plages, élément par élément, à la recherche d’une égalité ou d’une équivalence, selon une condition spécifiée par un prédicat binaire, et recherche la première position où se trouve une différence.
<alg> move Déplace les éléments associés à une plage spécifiée.
move_backward Déplace les éléments d'un itérateur vers un autre. Le déplacement commence par le dernier élément d'une plage spécifiée, et se termine par le premier élément de cette plage.
next_permutation Réorganise les éléments d’une plage, de sorte que le tri d’origine soit remplacé par la prochaine permutation plus élevée d’un point de vue lexicographique (s’il en existe une). La notion de "prochaine" peut être définie à l’aide d’un prédicat binaire.
none_of Retourne true lorsqu'une condition n'est remplie par aucun des éléments d'une plage spécifiée.
nth_element Partitionne une plage d’éléments, en recherchant le n-ième élément de la séquence dans la plage, de sorte que tous les éléments qui le précèdent sont inférieurs ou égaux, et que tous les éléments qui le suivent sont supérieurs ou égaux.
partial_sort Réorganise un nombre spécifié d’éléments plus petits au sein d’une plage, dans un ordre non décroissant, ou selon un critère de tri spécifié par un prédicat binaire.
partial_sort_copy Copie les éléments d’une plage source dans une plage de destination. Les éléments sources sont triés par ordre croissant ou selon un autre prédicat binaire spécifié.
partition Répartit les éléments d’une plage en deux ensembles disjoints. Les éléments qui répondent à un prédicat unaire doivent précéder ceux qui n’y répondent pas.
partition_copy Copie les éléments qui renvoient la valeur true dans une destination pour une condition donnée, et qui renvoient la valeur false dans une autre destination. Les éléments doivent provenir d'une plage spécifiée.
partition_point Retourne le premier élément de la plage donnée qui ne répond pas à la condition. Les éléments sont triés de sorte que ceux qui répondent à la condition viennent avant ceux qui ne le font pas.
pop_heap Retire le plus grand élément du début du tas et le place à l'avant-dernière position de la plage, puis forme un nouveau tas à partir des éléments restants.
prev_permutation Réorganise les éléments d’une plage, de sorte que le tri d’origine soit remplacé par la prochaine permutation plus élevée d’un point de vue lexicographique (s’il en existe une). La notion de "prochaine" peut être définie à l’aide d’un prédicat binaire.
push_heap Ajoute un élément qui se trouve à la fin d'une plage à un tas existant, constitué des éléments précédents de la plage.
random_shuffle Réorganise une séquence de N éléments d’une plage en une séquence de N! dispositions possibles, sélectionnées de manière aléatoire.
remove Élimine une valeur spécifiée d'une plage donnée sans modifier l'ordre des éléments restants, et retourne la fin d'une nouvelle plage exempte de la valeur spécifiée.
remove_copy Copie les éléments d’une plage source vers une plage de destination, sauf que les éléments d’une valeur spécifiée ne sont pas copiés, sans perturber l’ordre des éléments restants et retourner la fin d’une nouvelle plage de destination.
remove_copy_if Copie les éléments d’une plage source vers une plage de destination, sauf que la satisfaction d’un prédicat n’est pas copiée, sans perturber l’ordre des éléments restants et retourner la fin d’une nouvelle plage de destination.
remove_if Élimine d’une plage donnée les éléments qui répondent à un prédicat, sans modifier l’ordre des éléments restants et en retournant la fin d’une nouvelle plage exempte de la valeur spécifiée.
replace Examine tous les éléments d'une plage et les remplace s'ils correspondent à une valeur spécifiée.
replace_copy Examine tous les éléments d'une plage source et les remplace s'ils correspondent à une valeur spécifiée, tout en copiant le résultat dans une nouvelle plage de destination.
replace_copy_if Examine tous les éléments d'une plage source et les remplace s'ils répondent à un prédicat, tout en copiant le résultat dans une nouvelle plage de destination.
replace_if Examine tous les éléments d’une plage et les remplace s’ils répondent à un prédicat spécifié.
reverse Inverse l'ordre des éléments d'une plage.
reverse_copy Inverse l'ordre des éléments d'une plage source, tout en les copiant dans une plage de destination.
rotate Échange les éléments de deux plages adjacentes.
rotate_copy Échange les éléments de deux plages adjacentes au sein d'une plage source et copie le résultat dans une plage de destination.
sample
search Recherche la première occurrence d’une séquence au sein d’une plage cible dont les éléments sont égaux à ceux d’une séquence d’éléments donnée ou dont les éléments sont équivalents à ceux d’une séquence donnée, selon un prédicat binaire spécifié.
search_n Recherche la première sous-séquence d’une plage dont un nombre spécifié d’éléments ont une valeur particulière ou une relation à cette valeur, selon un prédicat binaire spécifié.
set_difference Regroupe tous les éléments qui appartiennent à une plage source triée, mais pas à une autre plage source triée, en une même plage de destination triée. Un critère de tri peut être spécifié par un prédicat binaire.
set_intersection Regroupe tous les éléments de deux plages sources triées au sein d'une même plage de destination triée. Le critère de tri peut être spécifié par un prédicat binaire.
set_symmetric_difference Regroupe tous les éléments qui appartiennent à l'une de deux plages sources triées (mais pas aux deux) au sein d'une même plage de destination triée. Le critère de tri peut être spécifié par un prédicat binaire.
set_union Regroupe tous les éléments qui appartiennent au moins à l'une de deux plages sources triées au sein d'une même plage de destination triée. Le critère de tri peut être spécifié par un prédicat binaire.
sort Réorganise les éléments d’une plage spécifiée, dans un ordre non décroissant, ou selon un critère de tri spécifié par un prédicat binaire.
shuffle Lit de façon aléatoire (réorganise) les éléments pour une plage donnée à l'aide d'un générateur de nombres aléatoires.
sort_heap Convertit un tas en une plage triée.
stable_partition Classe les éléments d’une plage en deux ensembles disjoints. Les éléments qui répondent à un prédicat unaire doivent précéder ceux qui n’y répondent pas, et l’ordre relatif des éléments équivalents doit être conservé.
stable_sort Classe les éléments d’une plage spécifiée dans un ordre non décroissant, ou selon un critère de tri spécifié par un prédicat binaire, et conserve l’ordre relatif des éléments équivalents.
swap Échange les valeurs des éléments de deux types d'objets, en assignant le contenu du premier objet au deuxième objet, et le contenu du deuxième au premier.
swap_ranges Échange les éléments d'une plage avec ceux d'une autre plage de taille égale.
transform Applique un objet de fonction spécifié à chaque élément d'une plage source ou à une paire d'éléments de deux plages sources, et copie les valeurs de retour de l'objet de fonction dans une plage de destination.
unique Supprime les éléments dupliqués qui sont en regard les uns des autres dans une plage spécifiée.
unique_copy Copie les éléments d’une plage source dans une plage de destination, à l’exception des éléments dupliqués qui sont à côté des autres.
upper_bound Recherche la position du premier élément d’une plage triée dont la valeur est supérieure à une valeur spécifiée. Le critère de tri peut être spécifié par un prédicat binaire.

Voir aussi

Informations de référence sur les fichiers d’en-tête
Sécurité des threads dans la bibliothèque C++ Standard
Informations de référence sur la bibliothèque standard C++