Partager via

Algorithmes

  • Article

Les algorithmes sont un élément fondamental de la bibliothèque C++ Standard. Les algorithmes ne fonctionnent pas eux-mêmes avec des conteneurs, mais plutôt avec des itérateurs. Par conséquent, le même algorithme peut être utilisé par la plupart des conteneurs de la bibliothèque C++ Standard (voire tous). Cette section traite des conventions et de la terminologie des algorithmes de la bibliothèque C++ Standard.

Notes

Les descriptions des modèles de fonction d’algorithme utilisent plusieurs expressions abrégées :

  • L’expression « dans la plage [A, B) » signifie la séquence de zéro ou plus de valeurs discrètes commençant par A jusqu’à B, mais pas B. Une plage est valide uniquement si B est accessible à partir de A, vous pouvez stocker A dans un objet N (N = A), vous pouvez incrémenter l’objet zéro ou plus de fois (++N), et faire en sorte que l’objet soit égal à B après un nombre fini d’incréments (N == B).

  • L’expression « chaque N de la plage [A, B) » signifie que N commence par la valeur A et est incrémenté zéro ou plus de fois jusqu’à ce qu’il soit égal à la valeur B. Le cas N == B n’est pas dans la plage.

  • L’expression « la plus petite valeur de N dans la plage [A, B) telle que X » signifie que la condition X est déterminée pour chaque N dans la plage [A, B) jusqu’à ce que la condition X soit remplie.

  • L’expression « valeur la plus élevée de N dans la plage [A, B) telle que X » signifie que X est déterminé pour chaque N de la plage [A, B). La fonction stocke en K une copie de N chaque fois que la condition X est remplie. Si un tel magasin se produit, la fonction remplace la valeur finale de N, qui est égale à B, par la valeur K. Pour un itérateur bidirectionnel ou d’accès aléatoire, toutefois, il peut également signifier que N commence par la valeur la plus élevée de la plage et est décrémenté sur la plage jusqu’à ce que la condition X soit remplie.

  • Les expressions comme X - Y, où X et Y peuvent être des itérateurs autres que des itérateurs d’accès aléatoire, doivent être interprétées au sens mathématique. La fonction n’évalue pas nécessairement l’opérateur - s’il doit déterminer une telle valeur. Cela vaut également pour les expressions comme X + N et X - N, où N est un type entier.

Plusieurs algorithmes utilisent un prédicat qui effectue une comparaison par paire, par exemple avec operator==, pour générer un résultat bool. La fonction de prédicat operator==, ou tout remplacement, ne doit pas modifier l'un de ses opérandes. Il doit produire le même bool résultat chaque fois qu’il est évalué, et il doit produire le même résultat si une copie de l’opérande est remplacée par l’opérande.

Plusieurs algorithmes utilisent un prédicat qui doit imposer un classement faible strict sur des paires d’éléments d’une séquence. Pour le prédicat pred(X, Y) :

  • Strict signifie que pred(X, X) est false.

  • Faible signifie que X et Y ont un ordre équivalent si !pred(X, Y) && !pred(Y, X) (X == Y n’a pas besoin d’être défini).

  • L’ordre signifie que pred(X, Y) && pred(Y, Z) implique préd(X, Z).

Certains de ces algorithmes utilisent implicitement le prédicat X<Y. Les autres prédicats qui répondent généralement aux exigences strictes de classement faible sont X>Y, less(X, Y) et greater(X, Y). Notez toutefois que les prédicats tels que X<= Y et X>= Y ne répondent pas à cette exigence.

Une séquence d’éléments désignés par des itérateurs dans la plage [First, Last) est une séquence ordonnée par opérateur < si, pour chaque N de la plage [0,First - Last ) et pour chaque M de la plage (N, Last - First) le prédicat !( *(First + M) < *(First + N)) a la valeur true. (Notez que les éléments sont triés dans l’ordre croissant.) La fonction operator<de prédicat, ou tout remplacement, ne doit pas modifier l’un de ses opérandes. Il doit produire le même bool résultat chaque fois qu’il est évalué, et il doit produire le même résultat si une copie de l’opérande est remplacée par l’opérande. En outre, elle doit imposer un classement faible strict sur les opérandes qu’elle compare.

Une séquence d’éléments désignés par des itérateurs dans la plage [First, Last) est un tas ordonné par operator< si, pour chaque N de la plage [1, Last - First) le prédicat !( *First< *(First + N)) a la valeur true. (Le premier élément est le plus grand.) Sa structure interne est sinon connue uniquement pour les fonctions make_heapde modèle , pop_heapet push_heap. Comme avec une séquence ordonnée, la fonction operator<de prédicat , ou tout remplacement pour elle, ne doit pas modifier l’un de ses opérandes, et il doit imposer un ordre faible strict sur les opérandes qu’il compare. Il doit produire le même bool résultat chaque fois qu’il est évalué, et il doit produire le même résultat si une copie de l’opérande est remplacée par l’opérande.

Les algorithmes de la bibliothèque standard C++ se trouvent dans les fichiers d’en-tête et <numeric> d’en-tête<algorithm>.

Voir aussi

Informations de référence sur la bibliothèque standard C++
Sécurité des threads dans la bibliothèque C++ Standard