7 Itérateurs et algorithmes de la bibliothèque standard 7.1 Du conteneur à l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Pourquoi une position après le dernier élément ? . . . . . . . . . . . . . . . . . . . . 7.4 Parcourir un conteneur avec un itérateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 L’itérateur cache la structure du conteneur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8 Les différentes catégories d’itérateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9 Les algorithmes de la bibliothèque standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.10 Rechercher un élément avec std::find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.10.1 Que se passe-t-il si la valeur n’existe pas ? . . . . . . . . . . . . . . . . . . . . . . . . 7.12.1 Pourquoi std::sort ne fonctionne-t-il pas directement avec std::list ? . . . . . 7.13 Appliquer une opération à tous les éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.14 Rechercher selon une condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.15 Transformer une séquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.16 Pourquoi utiliser un algorithme ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.17 Un algorithme peut travailler sur une partie du conteneur . . . . . . . . . . . . . . . . . . . 7.18 Itérateurs et invalidation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.19 La boucle for basée sur un intervalle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.20 Itérateurs, pointeurs et abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard

Accueil

Itérateurs et algorithmes de la bibliothèque standard Du conteneur à l’algorithme Nous avons étudié std::vector et listé plusieurs autres conteneurs de la bibliothèque standard à la fin du chapitre précédent. Nous avons vu comment parcourir un vector à l’aide d’un indice : std::vector<int> valeurs{10, 20, 30, 40}; for (std::size_t i = 0; i < valeurs.size(); ++i) std::cout << valeurs[i] << ’\n’; Cette technique fonctionne très bien avec un vector, car celui-ci permet un accès direct à ses éléments par leur indice mais tous les conteneurs ne possèdent pas cette propriété. Une std::list, par exemple, ne permet pas d’écrire Les éléments d’une liste chaînée ne sont pas nécessairement placés les uns à la suite des autres en mémoire donc il nous faut donc un mécanisme plus général permettant de parcourir les éléments d’un conteneur sans dépendre directement de sa structure interne. Ce mécanisme repose sur les itérateurs. Qu’est-ce qu’un itérateur ? Un itérateur est un objet permettant de désigner une position dans une séquence et de progresser dans cette séquence, son utilisation rappelle fortement celle d’un pointeur. std::vector<int> valeurs{10, 20, 30, 40}; Nous pouvons obtenir un itérateur vers le premier élément avec auto it = valeurs.begin(); Puis accéder à l’élément désigné en déréférencant le pointeur : 2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard std::cout << *it << ’\n’; Le programme affiche : Comme avec un pointeur, l’opérateur * permet donc d’accéder à l’objet désigné par l’itérateur et nous pouvons incémenter l’itérateur : std::cout << *it << ’\n’; • Un itérateur est un objet permettant de désigner une position dans une séquence et de parcourir • Sa syntaxe ressemble souvent à celle d’un pointeur : // position suivante • Mais un itérateur n’est pas nécessairement un pointeur. Les conteneurs fournissent généralement deux fonctions membres fondamentales qui sont begin() retourne un itérateur désignant le premier élément, et end() retourne un itérateur représentant la position située juste après le dernier élément. std::vector<int> v{10, 20, 30, 40}; nous pouvons représenter la situation ainsi : La position représentée par end() ne contient aucun élément du conteneur et il ne faut donc jamais la

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard Pourquoi une position après le dernier élément ? Cette convention permet de décrire une séquence par une paire d’itérateurs : Le premier élément appartient à la séquence, quant’à la position end elle n’a pas d’élément, c’est un intervalle semi-ouvert et nous pouvons écrire for (int i = 0; i < n; ++i) est le premier indice valide tandis que : est la première position située après le dernier élément (ne contient rien). Parcourir un conteneur avec un itérateur Nous pouvons maintenant parcourir entièrement un vector : std::vector<int> valeurs{10, 20, 30, 40}; for (auto it = valeurs.begin(); it != valeurs.end(); std::cout << *it << ’\n’; Le fonctionnement est directement comparable à celui d’une boucle utilisant un indice : it = valeurs.begin() Mais l’itérateur possède un avantage essentiel c’est qu’il peut également fonctionner avec des conteneurs qui ne possèdent pas d’indice. L’itérateur cache la structure du conteneur Considérons maintenant une liste : std::list<int> valeurs{10, 20, 30, 40}; Nous pouvons écrire : for (auto it = valeurs.begin(); it != valeurs.end(); std::cout << *it << ’\n’;

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard Le code de parcours est pratiquement identique à celui utilisé pour un vector pourtant, les structures internes sont très différentes, pendant qu’un vector stocke ses éléments de manière contiguë, une liste chaînée est conceptuellement constituée de noeuds reliés entre eux. Passer à l’élément suivant. La manière d’effectuer ce passage dépend du type d’itérateur. Le programmeur peut donc parcourir différentes structures à travers une interface commune. Le type d’un itérateur Nous avons utilisé l’itérateur auto it = valeurs.begin(); parce que l’utilisation de auto est particulièrement pratique ici en effet, l’écriture du type réel peut être on pourrait écrire explicitement std::vector<int>::iterator it = valeurs.begin(); auto it = valeurs.begin(); est généralement plus lisible. Nous rencontrons ici une utilisation particulièrement naturelle de auto : le type exact existe et reste parfaitement déterminé à la compilation, mais il n’est pas nécessaire de le répéter. Itérateurs constants Si nous ne voulons pas permettre la modification des éléments par l’intermédiaire de l’itérateur, nous pouvons utiliser un itérateur constant, par exemple auto it = valeurs.cbegin(); et la limite correspondante sera Avec un tel itérateur :

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard std::cout << *it << ’\n’; Nous disposons donc notamment de : parcours permettant éventuellement la modification, parcours en lecture seule. Les différentes catégories d’itérateurs Tous les itérateurs ne possèdent pas les mêmes possibilités, certains permettent seulement d’avancer, par D’autres permettent de reculer : D’autres encore permettent un déplacement direct Ces différences proviennent directement de la structure du conteneur. Par exemple, un vector permet un accès direct à n’importe quel élément et son itérateur peut effectuer efficacement des opérations telles que : Une liste chaînée doit au contraire suivre successivement les liens entre les noeuds pour avancer, elle ne permet donc pas le même type d’accès direct. La bibliothèque standard définit plusieurs catégories d’itérateurs mais pour l’instant, l’idée essentielle est Tous les itérateurs permettent certaines opérations communes, mais certains offrent des possibilités Les algorithmes de la bibliothèque standard L’intérêt des itérateurs apparaît pleinement avec les algorithmes qui pour pouvoir être utilisés nécessite #include <algorithm> Un algorithme ne travaille pas nécessairement directement avec un conteneur mais travaille souvent avec un intervalle d’itérateurs. Par exemple :

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard décrit l’ensemble des éléments du vector. Cette séparation est fondamentale : conteneur −→ itérateurs −→ algorithme L’algorithme n’a donc pas nécessairement besoin de connaître la structure interne du conteneur. Rechercher un élément avec std::find std::vector<int> valeurs{10, 20, 30, 40}; Nous pouvons rechercher la valeur 30 avec : auto it = std::find( std::find parcourt l’intervalle : [valeurs.begin(), valeurs.end()) et recherche la valeur demandée. Si elle est trouvée, l’algorithme retourne un itérateur vers l’élément correspondant et donc nous pouvons if (it != valeurs.end()) std::cout << « Valeur trouvee :  » Que se passe-t-il si la valeur n’existe pas ? Si la valeur recherchée n’est pas trouvée, std::find retourne : if (it == valeurs.end()) std::cout << « Valeur absente\n »; Nous retrouvons donc encore une fois le rôle particulier de end() : Il représente la position située après le dernier élément et peut également servir à signaler qu’aucun élément valide n’a été trouvé.

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard Compter avec std::count permet de compter le nombre d’occurrences d’une valeur. Par exemple, std::vector<int> valeurs{2, 7, 2, 4, 2, 9}; auto nombre = std::count( La variable nombre contient alors L’algorithme effectue lui-même le parcours du conteneur. Trier avec std::sort Un vector peut être trié avec : std::vector<int> valeurs{8, 2, 9, 1, 5}; std::sort(valeurs.begin(), valeurs.end()); Après cette opération, le vector contient : L’algorithme modifie directement l’ordre des éléments. Pourquoi std::sort ne fonctionne-t-il pas directement avec std::list ? Essayons conceptuellement : std::list<int> valeurs{8, 2, 9, 1, 5}; std::sort(valeurs.begin(), valeurs.end()); Cette utilisation n’est pas valide. std::sort nécessite des itérateurs permettant un accès aléatoire efficace aux éléments et les itérateurs d’une std::list ne possèdent pas cette capacité. La liste fournit donc sa propre fonction membre qui est : Cet exemple montre que l’abstraction fournie par les itérateurs ne signifie pas que toutes les structures de données deviennent identiques mais que leurs propriétés fondamentales continuent à déterminer les opérations qui peuvent être réalisées efficacement.

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard Appliquer une opération à tous les éléments Considérons une opération très simple : afficher chaque élément. Une solution serait parcourir une boucle, cependant, la bibliothèque standard fournit également des algorithmes capables d’appliquer une opération à chaque élément. Historiquement, on rencontre notamment : Son utilisation devient particulièrement intéressante lorsqu’on peut définir directement l’opération à effectuer et c’est précisément l’un des rôles des expressions lambda que nous verrons dans le chapitre Rechercher selon une condition std::find recherche une valeur déterminée. Par exemple, on peut vouloir rechercher • le premier nombre négatif ; • le premier nombre supérieur à 100 ; • le premier objet satisfaisant une certaine condition. La bibliothèque fournit pour cela Cet algorithme doit recevoir une condition capable de répondre à la question Cet élément convient-il ? Là encore, les expressions lambda fourniront une manière particulièrement élégante d’écrire cette condition. Nous reporterons donc l’étude détaillée de find_if au chapitre suivant. Transformer une séquence Un autre algorithme important est : Il permet notamment de produire des valeurs transformées à partir des éléments d’une séquence. Nous pourrions par exemple vouloir transformer : L’algorithme doit alors savoir quelle transformation appliquer à chaque élément et une expression lambda 1 permettra par exemple d’exprimer directement : Nous reviendrons donc également sur std::transform après avoir étudié les lambdas. 1. Voir chapitre suivant

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard Pourquoi utiliser un algorithme ? Considérons la recherche manuelle d’une valeur : bool trouve = false; for (int valeur : valeurs) La même intention peut être exprimée avec : auto it = std::find( L’intérêt n’est pas simplement de réduire le nombre de lignes, l’expression : indique immédiatement l’intention de rechercher un élément Le détail de la boucle disparaît du code principal donc les algorithmes permettent ainsi d’écrire du code à un niveau d’abstraction plus élevé. Un algorithme peut travailler sur une partie du conteneur Puisque les algorithmes travaillent sur des intervalles d’itérateurs, ils ne sont pas limités à l’ensemble du std::vector<int> v{10, 20, 30, 40, 50}; Nous pouvons rechercher uniquement dans une partie du vector : auto debut = v.begin() + 1; auto it = std::find(debut, fin, 30); L’intervalle considéré est : et correspond ici aux valeurs : La valeur 50 n’appartient pas à l’intervalle examiné et cela montre pourquoi les algorithmes travaillent avec des positions plutôt qu’avec le conteneur complet.

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard Itérateurs et invalidation Nous avons déjà rencontré le problème de la réallocation d’un vector. std::vector<int> v{10, 20, 30}; auto it = v.begin(); Si une opération ultérieure provoque une réallocation : l’ancienne zone de stockage peut être abandonnée au profit d’une nouvelle et dans ce cas, l’itérateur it devient invalide, donc il ne doit plus être utilisé. Nous retrouvons exactement le même phénomène que pour un pointeur ou une référence vers un élément du vector et les règles précises d’invalidation dépendent du conteneur et de l’opération effectuée. • Un itérateur n’assure pas à lui seul que l’objet désigné continuera d’exister à la même position. • Certaines modifications du conteneur peuvent invalider ses itérateurs. • Dans un vector, une réallocation invalide les itérateurs désignant ses éléments. La boucle for basée sur un intervalle Nous avons déjà utilisé : for (const int& valeur : valeurs) std::cout << valeur << ’\n’; Cette syntaxe paraît très différente d’une boucle utilisant explicitement des itérateurs et conceptuellement, elle repose pourtant sur le même principe qui est parcourir une séquence entre son début et sa fin. Nous pouvons donc voir la boucle : for (const auto& valeur : valeurs) comme une forme particulièrement pratique lorsque nous voulons simplement traiter successivement tous les éléments sans avoir besoin de manipuler explicitement leur position. Itérateurs, pointeurs et abstraction Il existe une parenté importante entre un pointeur et un itérateur. Avec un tableau classique nous avons : int t[] = {10, 20, 30};

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard nous pouvons écrire : auto it = v.begin(); L’itérateur généralise en quelque sorte certaines propriétés du pointeur, mais il les généralise à des structures qui ne sont pas forcément contiguës en mémoire donc c’est cette abstraction qui permet aux algorithmes génériques de fonctionner avec de nombreux types de conteneurs. Un itérateur représente une position dans une séquence. Les fonctions membres : délimitent généralement l’intervalle des éléments d’un conteneur où begin() désigne le premier élément et end() représente la position située immédiatement après le dernier élément et ne doit jamais être déréférencé. Les algorithmes de la bibliothèque standard utilisent fréquemment un intervalle semi-ouvert Nous avons vu les algorithmes suivant Les algorithmes séparent l’opération à effectuer de la structure concrète du conteneur mais les possibilités d’un algorithme restent cependant liées aux capacités des itérateurs qui lui sont fournis. Les itérateurs peuvent être invalidés lorsque le conteneur est modifié. Nous disposons maintenant des deux premières composantes de la programmation générique : Il reste à étudier une manière particulièrement puissante de fournir aux algorithmes le comportement qu’ils doivent appliquer aux éléments. Ce sera l’objet du chapitre suivant : les expressions lambda.

Accueil

P4-Chap-07 Itérateurs et algorithmes de la bibliothèque standard

Accueil

2026 – C++ Partie III Itérateurs et algorithmes de la bibliothèque standard

Accueil

Termes à ajouter au glossaire