Programmation C-C++/La bibliothèque standard/Les algorithmes

La plupart des opérations qui peuvent être appliquées aux structures de données ne sont pas spécifiques à ces structures. Par exemple, il est possible de trier quasiment toutes les séquences, que ce soient des listes, des vecteurs ou des deques. Les classes template des conteneurs de la bibliothèque standard ne fournissent donc que des méthodes de base permettant de les manipuler, et rares sont les conteneurs qui définissent des opérations dont le rôle dépasse le simple cadre de l'ajout, de la suppression ou de la recherche d'éléments. Au lieu de cela, la bibliothèque standard définit tout un jeu de fonctions template extérieures aux conteneurs et dont le but est de réaliser ces opérations de haut niveau. Ces fonctions sont appelées algorithmes en raison du fait qu'elles effectuent les traitements des algorithmes les plus connus et les plus utilisés en informatique.

Les algorithmes ne dérogent pas à la règle de généricité que la bibliothèque standard C++ s'impose. Autrement dit, ils sont capables de travailler en faisant le moins d'hypothèses possibles sur la structure de données contenant les objets sur lesquels ils s'appliquent. Ainsi, tous les algorithmes sont des fonctions template et ils travaillent sur les objets exclusivement par l'intermédiaire d'itérateurs et de foncteurs. Cela signifie que les algorithmes peuvent, en pratique, être utilisés sur n'importe quelle structure de données ou n'importe quel conteneur, pourvu que les préconditions imposées sur les itérateurs et le type des données manipulées soient respectées.

Comme pour les méthodes permettant de manipuler les conteneurs, les algorithmes sont décrits par leur sémantique et par leur complexité. Cela signifie que les implémentations de la bibliothèque standard sont libres quant à la manière de réaliser ces algorithmes, mais qu'elles doivent impérativement respecter les contraintes de performances imposées par la norme de la bibliothèque standard. En pratique cependant, tout comme pour les structures de données des conteneurs, ces contraintes imposent souvent l'algorithme sous-jacent pour l'implémentation de ces fonctionnalités et l'algorithme utilisé est le meilleur algorithme connu à ce jour. Autrement dit, les algorithmes de la bibliothèque standard sont forcément les plus efficaces qui soient.

La plupart des algorithmes de la bibliothèque standard sont déclarés dans l'en-tête algorithm. Certains algorithmes ont été toutefois définis initialement pour les valarray et n'apparaissent donc pas dans cet en-tête. Au lieu de cela, ils sont déclarés dans l'en-tête numeric. Ces algorithmes sont peu nombreux et cette particularité sera signalée dans leur description.

Le nombre des algorithmes définis par la bibliothèque standard est impressionnant et couvre sans doute tous les besoins courants des programmeurs. Il est donc difficile, en raison de cette grande diversité, de présenter les algorithmes de manière structurée. Cependant, les sections suivantes regroupent ces algorithmes en fonction de la nature des opérations qu'ils sont supposés effectuer. Ces opérations comprennent les opérations de manipulation générales des données, les recherches d'éléments selon des critères particuliers, les opérations de tri et de comparaison, et enfin les opérations de manipulation ensemblistes.