Résumé – Chap 7 – Itérateurs et algorithmes de la bibliothèque standard
Les conteneurs de la bibliothèque standard n’organisent pas tous leurs éléments de la même manière : std::vector permet un accès direct par indice, alors que d’autres structures, comme std::list, ne le permettent pas. Les itérateurs fournissent une manière commune de parcourir ces conteneurs sans dépendre directement de leur organisation interne. Un itérateur désigne une position dans un conteneur et possède une syntaxe qui rappelle celle d’un pointeur : l’opérateur * permet d’accéder à l’élément désigné et ++ de passer à la position suivante. begin() fournit un itérateur vers le premier élément et end() une position située juste après le dernier élément ; cette dernière ne doit jamais être déréférencée. Un parcours est ainsi défini par l’intervalle semi-ouvert [begin(), end()), convention largement utilisée dans la bibliothèque standard. auto simplifie l’écriture des types d’itérateurs, souvent longs, tandis que cbegin() et cend() fournissent des itérateurs permettant uniquement la lecture. Tous les itérateurs n’offrent cependant pas les mêmes possibilités : certains permettent seulement d’avancer, d’autres également de reculer, et les itérateurs à accès aléatoire permettent de se déplacer directement entre différentes positions. Ces capacités dépendent de la structure du conteneur et déterminent les opérations qui peuvent lui être appliquées.
Les algorithmes de la bibliothèque standard travaillent généralement sur des intervalles définis par deux itérateurs plutôt que directement sur un type particulier de conteneur. Cette séparation entre conteneurs, itérateurs et algorithmes permet d’utiliser une même opération avec différentes structures de données lorsque leurs itérateurs possèdent les propriétés nécessaires. std::find recherche une valeur et retourne un itérateur vers l’élément trouvé ou end() si la recherche échoue ; std::count compte les occurrences d’une valeur et std::sort réorganise les éléments d’un intervalle. Ce dernier exige des itérateurs à accès aléatoire et ne peut donc pas être appliqué directement à std::list, qui possède sa propre méthode sort(). D’autres algorithmes permettent d’appliquer une opération à tous les éléments, de rechercher un élément satisfaisant une condition ou de transformer une plage de valeurs. Les itérateurs permettent également de limiter un algorithme à une sous-partie d’un conteneur, mais ils restent liés à la structure qu’ils parcourent et certaines modifications du conteneur peuvent les invalider. La boucle for fondée sur une plage masque une grande partie de ce mécanisme, mais repose sur la même idée de parcours entre un début et une fin. Les itérateurs constituent ainsi une abstraction intermédiaire essentielle : proches des pointeurs dans leur syntaxe, ils permettent aux algorithmes d’être indépendants de l’organisation concrète des données et forment le lien entre les conteneurs et les traitements génériques de la bibliothèque standard.