Partager via


Algorithmes

Les algorithmes sont une première partie de la bibliothèque de modèles Standard.Les algorithmes ne fonctionnent pas avec les conteneurs eux-mêmes mais plutôt avec les itérateurs.Par conséquent, le même algorithme peut être utilisé par le plus si tous les conteneurs STL.Cette section présente les conventions et la terminologie des algorithmes de STL.

Notes

Les descriptions des fonctions de modèle d'algorithme utilisent plusieurs expressions abrégée :

  • L'expression « dans la plage [A, B) » signifie la séquence de zéro valeurs séparées ou plus démarrant avec Un jusqu'à la limite de B.Une plage est valide uniquement si B est accessible d'Un ; vous pouvez enregistrer Un dans un objet N (N = Un), incrémenter l'objet zéro ou plusieurs fois à (++N), et exécution comparer l'objet égale à B après un nombre terminé d'incréments (== de N B).

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

  • L'expression « la valeur la plus faible de N dans la plage [A, *B)*tels 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 est rempli.

  • l'expression « la valeur la plus élevée de N dans la plage [A, *B)*tels que X signifie que X est déterminé pour chaque N dans la plage [A, B).La fonction stocker dans K une copie de N chaque fois que la condition X est remplie.Si une telle magasin se produit, la fonction remplace la valeur finale de N, qui équivaut à B, par la valeur d' K.Pour un affichage ou un itérateurs d'accès aléatoire, toutefois, il peut également signifier que N commence par la valeur la plus élevée dans la plage et est décrémenté dans une plage comprise entre jusqu'à ce que la condition X est rempli.

  • expressions telles que X - O, où X et Y peuvent être des itérateurs autres que les itérateurs d'accès aléatoire, sont supposés dans le sens mathématique.La fonction ne correspond pas nécessairement l'opérateur- si elle doit déterminer une telle valeur.C'est également vrai pour les expressions telles que X + et NX - n, où N est un type entier.

Plusieurs algorithmes utilisent un attribut qui exécute par paire une comparaison, par exemple avec operator==, pour donner un résultat d' bool .La fonction **operator==**d'attribut, ou none remplacement pour celle-ci, ne doit modifier non plus de ses opérandes.Il doit donner le même résultat d' bool chaque fois qu'il est évalué, et il doit donner le même résultat si une copie de l'un des opérandes est substituée pour l'opérande.

Plusieurs algorithmes utilisent un attribut qui doit appliquer le classement faible strict aux paires d'éléments d'une séquence.pour l'attribut pr(X, Y):

  • Strict signifie cet pr(X, *X)*est false.

  • Faible signifie que X et Y ont le classement équivalent si !pr(X, Y) && !pr(Y, X)(== Ode X n'a pas besoin d'être défini).

  • Le classement signifie cet pr(X, *Y && )*pr(O, Z) implique pr(X, Z).

Certains de ces algorithmes utilisent implicitement l'attribut X < *Y.*D'autres attributs qui correspondent généralement à la spécification de classement faible stricte est X > Y, moins(X, Y), et greater(X, Y).Notez, cependant, que les attributs tels que X <= O et X >= O ne répondent pas à cette condition.

Une séquence d'éléments indiqués par les itérateurs dans la plage [First, Last) est une séquence classée par l'opérateur**<** si, pour chaque N dans la plage [0, Last - First) et pour chaque M dans la plage (N, Last - First) l'attribut ! (* (First + M)< * (premier + N)) a la valeur true.(Notez que les éléments sont triés par ordre croissant.) La fonction **operator<**d'attribut, ou none remplacement pour celle-ci, ne doit modifier non plus de ses opérandes.Il doit donner le même résultat d' bool chaque fois qu'il est évalué, et il doit donner le même résultat si une copie de l'un des opérandes est substituée pour l'opérande.De plus, elle doit appliquer le classement faible strict aux opérandes qu'il compare.

Une séquence d'éléments indiqués par les itérateurs dans la plage [First, Last) est un tas classé par operator< si, pour chaque N dans la plage [1, Last - First) l'attribut ! (*First < * (First + N)) a la valeur true.(Le premier élément est le plus grand.) Sa structure interne est généralement connue uniquement aux fonctions de modèle make_heap, pop_heap, et push_heap.Comme pour une séquence classée, la fonction **operator<**d'attribut, ou none remplacement pour celui-ci, ne doit modifier non plus de ses opérandes, et il doit appliquer le classement faible strict aux opérandes qu'il compare.Il doit donner le même résultat d' bool chaque fois qu'il est évalué, et il doit donner le même résultat si une copie de l'un des opérandes est substituée pour l'opérande.

Les algorithmes STL se trouvent dans les fichiers d'en-tête de <algorithm> et de <numeric> .

Voir aussi

Référence

Modèles Standard

Sécurité des threads dans la bibliothèque C++ standard