Outils d'utilisateurs
iterateurs
Différences
Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
|
iterateurs [2016/07/02 23:06] gbdivers |
iterateurs [2018/12/10 23:35] (Version actuelle) winjerome Correction orthographique |
||
|---|---|---|---|
| Ligne 14: | Ligne 14: | ||
| ===== Manipuler un itérateur ===== | ===== Manipuler un itérateur ===== | ||
| - | Même si vous n'en aviez pas conscience, vous avez déjà manipuler des itérateurs. En effet, les fonctions ''std::begin'' et ''std::end'' permettent d'obtenir un itérateur sur le début et la fin d'une collection. Jusque maintenant, vous utilisiez les itérateurs retournés par ces fonctions directement dans des algorithmes, mais rien n'interdit de créer des variables contenant ces itérateurs. | + | Même si vous n'en aviez pas conscience, vous avez déjà manipulé des itérateurs. En effet, les fonctions ''std::begin'' et ''std::end'' permettent d'obtenir un itérateur sur le début et la fin d'une collection. Jusque maintenant, vous utilisiez les itérateurs retournés par ces fonctions directement dans des algorithmes, mais rien n'interdit de créer des variables contenant ces itérateurs. |
| <code cpp> | <code cpp> | ||
| Ligne 21: | Ligne 21: | ||
| </code> | </code> | ||
| - | <note>Pour éviter de devoir rappeler à chaque fois la déclaration d'une collection, il est classique d'utiliser des noms pour certains types de variables. Dans ce cours, vous verrez par exemple 'v' pour désigner un ''std::vector'' ou ''it'' pour désigner un itérateur (peut importe le type exacte).</note> | + | <note>Pour éviter de devoir rappeler à chaque fois la déclaration d'une collection, il est classique d'utiliser des noms pour certains types de variables. Dans ce cours, vous verrez par exemple ''v'' pour désigner un ''std::vector'' ou ''it'' pour désigner un itérateur (peu importe le type exact).</note> |
| Pour déclarer une variable de type itérateur, il est beaucoup plus simple d'utiliser l'inférence de type, comme dans le code précédent. Si vous souhaitez écrire explicitement le type d'itérateur, la syntaxe à utiliser est la suivante : | Pour déclarer une variable de type itérateur, il est beaucoup plus simple d'utiliser l'inférence de type, comme dans le code précédent. Si vous souhaitez écrire explicitement le type d'itérateur, la syntaxe à utiliser est la suivante : | ||
| Ligne 31: | Ligne 31: | ||
| Vous avez déjà vu des syntaxes similaires dans le début de ce cours (par exemple ''std::numeric_limits<int>::max()'' dans le chapitre [[informations_sur_les_types|]]). Le code ''std::vector<int>::iterator'' signifie simplement "le type ''iterator'' provenant de la classe ''vector<int>''". | Vous avez déjà vu des syntaxes similaires dans le début de ce cours (par exemple ''std::numeric_limits<int>::max()'' dans le chapitre [[informations_sur_les_types|]]). Le code ''std::vector<int>::iterator'' signifie simplement "le type ''iterator'' provenant de la classe ''vector<int>''". | ||
| - | Notez bien qu'il faut respecter les collections de provenance des itérateurs. Si vous appeler un algorithme qui attend deux itérateurs d'une même collection, mais que vous lui donnez des itérateurs provenant de deux collections différentes, cela produira un comportement indéterminé (un crash en général dans ce cas). | + | Notez bien qu'il faut respecter la provenance des itérateurs. Si vous appelez un algorithme qui attend deux itérateurs d'une même collection, mais que vous lui donnez des itérateurs provenant de deux collections différentes, cela produira un comportement indéterminé (un crash en général dans ce cas). |
| <code cpp> | <code cpp> | ||
| Ligne 45: | Ligne 45: | ||
| * les itérateurs "constants", qui interdisent de modifier les éléments d'une collection. | * les itérateurs "constants", qui interdisent de modifier les éléments d'une collection. | ||
| - | Les fonctions "reverse" commencent par "r", les fonctions "constantes" commencent par "c" et il est possible d'avoir n'importe quelles combinaisons : | + | Les fonctions "reverse" commencent par "r", les fonctions "constantes" commencent par "c" et il est possible d'avoir n'importe quelle combinaison : |
| * ''std::begin'' et ''std::end'' ; | * ''std::begin'' et ''std::end'' ; | ||
| Ligne 52: | Ligne 52: | ||
| * ''std::crbegin'' et ''std::crend''. | * ''std::crbegin'' et ''std::crend''. | ||
| - | <note>Avec le C++14, ces fonctions sont disponibles comme fonctions libres et fonctions membres, les compilateurs plus anciens ne proposeront pas forcement les fonctions libres. Dans ce cas, vous pouvez utiliser les fonctions membres, qui seront toujours disponibles. | + | <note>Avec le C++14, ces fonctions sont disponibles comme fonctions libres et fonctions membres, les compilateurs plus anciens ne proposeront pas forcément les fonctions libres. Dans ce cas, vous pouvez utiliser les fonctions membres, qui seront toujours disponibles. |
| <code cpp> | <code cpp> | ||
| Ligne 91: | Ligne 91: | ||
| </code> | </code> | ||
| - | Vous pouvez essayer ce code : cela produira une erreur à l'exécution. Voici un schéma permet de bien comprendre ce qu'il se passe. | + | Vous pouvez essayer ce code : cela produira une erreur à l'exécution. Voici un schéma qui permet de bien comprendre ce qu'il se passe. |
| {{ :rbegin-rend.png |}} | {{ :rbegin-rend.png |}} | ||
| Ligne 100: | Ligne 100: | ||
| La "const-correctness" (qui signifie "avoir un code qui respecte l'utilisation des constantes") est un peu plus complexe à comprendre, puisqu'il peut y avoir deux types de constances avec les itérateurs : sur l'itérateur et sur l'élément qu'il représente. | La "const-correctness" (qui signifie "avoir un code qui respecte l'utilisation des constantes") est un peu plus complexe à comprendre, puisqu'il peut y avoir deux types de constances avec les itérateurs : sur l'itérateur et sur l'élément qu'il représente. | ||
| - | Comme vous l'avez vu, vous pouvez utiliser le mot-clé ''const'' pour indiquer d'une variable ne sera pas modifiée. Avec un itérateur, cela signifie que la variable représentera toujours le même élément dans une collection. | + | Comme vous l'avez vu, vous pouvez utiliser le mot-clé ''const'' pour indiquer qu'une variable ne sera pas modifiée. Avec un itérateur, cela signifie que la variable représentera toujours le même élément dans une collection. |
| <code cpp> | <code cpp> | ||
| - | const auto first { std::begin(v); }; | + | const auto first { std::begin(v) }; |
| - | first = std::end(v); // modification de l'itérateur : erreur | + | first = std::end(v); // modification de l'itérateur : erreur |
| do_something(first); // modification de l'élément : ok | do_something(first); // modification de l'élément : ok | ||
| </code> | </code> | ||
| Ligne 113: | Ligne 113: | ||
| <code cpp> | <code cpp> | ||
| - | auto first { std::cbegin(v); }; | + | auto first { std::cbegin(v) }; |
| - | first = std::cend(v); // modification de l'itérateur : ok | + | first = std::cend(v); // modification de l'itérateur : ok |
| do_something(first); // modification de l'élément : erreur | do_something(first); // modification de l'élément : erreur | ||
| </code> | </code> | ||
| Ligne 133: | Ligne 133: | ||
| ==== Créer une sous-collection ==== | ==== Créer une sous-collection ==== | ||
| - | L'utilisation des itérateurs ne se limite pas aux algorithmes, il est également possible de les utiliser dans d'autres contexte. Par exemple, beaucoup de collections (en particulier ''std::vector'' et ''std::string'') peuvent être initialisées en utilisant une paire d'itérateurs. La nouvelle collection créés contiendra une copie des éléments contenus entre ces deux itérateurs. | + | L'utilisation des itérateurs ne se limite pas aux algorithmes, il est également possible de les utiliser dans d'autres contextes. Par exemple, beaucoup de collections (en particulier ''std::vector'' et ''std::string'') peuvent être initialisées en utilisant une paire d'itérateurs. La nouvelle collection créée contiendra une copie des éléments contenus entre ces deux itérateurs. |
| <code cpp> | <code cpp> | ||
| Ligne 142: | Ligne 142: | ||
| std::string s1 { "azerty" }; | std::string s1 { "azerty" }; | ||
| - | std::string s2(std::begin(s1), end(s1)); | + | std::string s2(std::begin(s1), std::end(s1)); |
| std::cout << s2 << std::endl; | std::cout << s2 << std::endl; | ||
| Ligne 203: | Ligne 203: | ||
| Dans ce code, la fonction ''std::find'' recherche le caractère ''8'' et le trouve à la douzième position. L'itérateur correspondant à cette position est ensuite utilisé pour créer une première chaîne contenant les caractères avec cet élément, puis une seconde chaîne contenant les caractères suivant cet élément. | Dans ce code, la fonction ''std::find'' recherche le caractère ''8'' et le trouve à la douzième position. L'itérateur correspondant à cette position est ensuite utilisé pour créer une première chaîne contenant les caractères avec cet élément, puis une seconde chaîne contenant les caractères suivant cet élément. | ||
| - | Vous pouvez remarquer un point important sur le fonctionnement des itérateurs : le caractère trouvé est dans la seconde sous-chaîne, pas dans la première. Une paire d'itérateurs fonctionne comme un intervalle semi-ouvert : l'élément correspondant au premier itérateur est inclut, l'élément correspondant au second itérateur est exclut. | + | Vous pouvez remarquer un point important sur le fonctionnement des itérateurs : le caractère trouvé est dans la seconde sous-chaîne, pas dans la première. Une paire d'itérateurs fonctionne comme un intervalle semi-ouvert : l'élément correspondant au premier itérateur est inclus, l'élément correspondant au second itérateur est exclu. |
| Si vous recherchez les caractères 'd' et 'i' dans la chaîne ''"abcdefghijk"'' et que vous créez la chaîne correspondante à ces deux itérateurs, le résultat sera la chaîne ''"defgh"''. | Si vous recherchez les caractères 'd' et 'i' dans la chaîne ''"abcdefghijk"'' et que vous créez la chaîne correspondante à ces deux itérateurs, le résultat sera la chaîne ''"defgh"''. | ||
| Ligne 226: | Ligne 226: | ||
| La fonction ''std::end'', qui correspond à la fin de la collection, ne correspond pas en fait au dernier élément d'une collection, mais à un élément virtuel, qui n'existe pas. Cet élément virtuel peut être vu comme un élément supplémentaire après le dernier élément de la collection. | La fonction ''std::end'', qui correspond à la fin de la collection, ne correspond pas en fait au dernier élément d'une collection, mais à un élément virtuel, qui n'existe pas. Cet élément virtuel peut être vu comme un élément supplémentaire après le dernier élément de la collection. | ||
| - | <note>Cet élément n'existe pas réellement. Tenter d'y accéder ou de le manipuler comme s'il existait produirait un comportement indéterminé. | + | <note>Cet élément n'existe pas réellement. Tenter d'y accéder ou de le manipuler comme s'il existait produit un comportement indéterminé. |
| - | Et plus généralement, essayer d'utiliser un itérateur invalide (donc non compris entre ''std::begin'' inclut et ''std::end'' exclut) produit un comportement indéterminé. C'est au développeur de vérifier la validité des itérateurs qu'il manipule.</note> | + | Et plus généralement, essayer d'utiliser un itérateur invalide (donc non compris entre ''std::begin'' inclus et ''std::end'' exclu) produit un comportement indéterminé. C'est au développeur de vérifier la validité des itérateurs qu'il manipule.</note> |
| Pour les fonctions ''std::rbegin'' et ''std::rend'', les itérateurs correspondent respectivement au dernier élément de la collection et un élément virtuel qui serait situé avant le premier élément. | Pour les fonctions ''std::rbegin'' et ''std::rend'', les itérateurs correspondent respectivement au dernier élément de la collection et un élément virtuel qui serait situé avant le premier élément. | ||
| Ligne 265: | Ligne 265: | ||
| </note> | </note> | ||
| - | Une collection vide (par exemple ''{}'' ou une chaîne vide ''""'') ne contient aucun élément. Dans ce cas, ''std::begin'' retourne ''std::end'' (vous pouvez donc tester si une collection est vide avec le code ''std::begin == std::end'', mais il est plus logique d'utiliser la fonction membre ''empty()'' si elle est disponible. | + | Une collection vide (par exemple ''{}'' ou une chaîne vide ''""'') ne contient aucun élément. Dans ce cas, ''std::begin(collection)'' retourne ''std::end(collection)'' (vous pouvez donc tester si une collection est vide avec le code ''std::begin(collection) == std::end(collection)'', mais il est plus logique d'utiliser la fonction membre ''empty()'' si elle est disponible. |
| <note>Intervalle (''range'') | <note>Intervalle (''range'') | ||
| - | Une paire d'itérateurs permet de définir un intervalle (//range//). Vous verrez parfois la notation ''[first, last)'' pour désigner un intervalle fermé à gauche et ouvert à droite. Cette notation mathématique permet d'écrire une collection, avec les crochets droits pour inclure les bornes et les parenthèses pour les exclure. Ainsi, l'ensemble [0, 1) correspond à l'ensemble des réels compris entre 0 inclus et 1 exclu, (0, 1) exclu les valeurs 0 et 1, (0, 1] exclu 0 et inclus 1, etc.</note> | + | Une paire d'itérateurs permet de définir un intervalle (//range//). Vous verrez parfois la notation ''[first, last)'' pour désigner un intervalle fermé à gauche et ouvert à droite. Cette notation mathématique permet d'écrire une collection, avec les crochets droits pour inclure les bornes et les parenthèses pour les exclure. Ainsi, l'ensemble [0, 1) correspond à l'ensemble des réels compris entre 0 inclus et 1 exclu, (0, 1) exclut les valeurs 0 et 1, (0, 1] exclut 0 et inclut 1, etc.</note> |
| Ligne 280: | Ligne 280: | ||
| Une indirection permet d'accéder indirectement à un autre objet, pour pouvoir lire la valeur ou la modifier. Accéder à l'élément correspondant à une indirection s'appelle "déréférencer une indirection". Pour les itérateurs, l'accès se fait en utilisant l'opérateur ''*'' unaire préfixé. | Une indirection permet d'accéder indirectement à un autre objet, pour pouvoir lire la valeur ou la modifier. Accéder à l'élément correspondant à une indirection s'appelle "déréférencer une indirection". Pour les itérateurs, l'accès se fait en utilisant l'opérateur ''*'' unaire préfixé. | ||
| - | * unaire signifie que cette opérateur ne prend qu'un argument, l'itérateur dans ce cas ; | + | * //unaire// signifie que cette opérateur ne prend qu'un argument, l'itérateur dans ce cas ; |
| - | * préfixé signifie que l'opérateur s'écrit avant son argument. | + | * //préfixé// signifie que l'opérateur s'écrit avant son argument. |
| Plus concrètement, il faut donc écrire : | Plus concrètement, il faut donc écrire : | ||
| Ligne 289: | Ligne 289: | ||
| </code> | </code> | ||
| - | Écris de cette façon, vous pouvez penser que cette syntaxe ne pose pas particulièrement de problème. Mais il ne faut pas oublier que l'opérateur ''*'' possède plusieurs signification en C++ : cela représente aussi la multiplication (et également les pointeurs, que vous verrez plus tard). Il faut donc être particulièrement vigilant pour éviter la confusion. N'hésitez pas à entourer cette syntaxe de parenthèses, dès que le code risque d'être ambiguë. (Voire vous pouvez mettre tout le temps les parenthèses, cela ne coûte rien). | + | Écrit de cette façon, vous pouvez penser que cette syntaxe ne pose pas particulièrement de problème. Mais il ne faut pas oublier que l'opérateur ''*'' possède plusieurs significations en C++ : cela représente aussi la multiplication (et également les pointeurs, que vous verrez plus tard). Il faut donc être particulièrement vigilant pour éviter la confusion. N'hésitez pas à entourer cette syntaxe de parenthèses, dès que le code risque d'être ambigu. (Voire vous pouvez mettre tout le temps les parenthèses, cela ne coûte rien). |
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| Ligne 330: | Ligne 330: | ||
| </code> | </code> | ||
| - | N'oubliez pas la différence entre un itérateur constant et non constant. Essayer de modifier un itérateur constant produira une erreur de compilation : | + | N'oubliez pas la différence entre un itérateur constant et non constant. Tenter de modifier un itérateur constant produira une erreur de compilation : |
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| Ligne 356: | Ligne 356: | ||
| L'erreur signifie que la valeur retournée par l'opérateur ''*'' est une valeur constante et ne peut être assignée. | L'erreur signifie que la valeur retournée par l'opérateur ''*'' est une valeur constante et ne peut être assignée. | ||
| - | Il est possible d'avoir plusieurs indirections sur un objet. Modifier l'une des indirections va modifier l'élément correspondant, ce qui implique que toutes les accès via les indirections seront modifiées. | + | Il est possible d'avoir plusieurs indirections sur un objet. Modifier l'une des indirections va modifier l'élément correspondant, ce qui implique que tous les accès via les indirections seront modifiés. |
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| Ligne 395: | Ligne 395: | ||
| std::cout << s << std::endl; | std::cout << s << std::endl; | ||
| } | } | ||
| + | </code> | ||
| + | |||
| + | affiche : | ||
| + | |||
| + | <code> | ||
| + | abcdef | ||
| + | abcdef | ||
| </code> | </code> | ||
| Ligne 430: | Ligne 437: | ||
| </code> | </code> | ||
| - | Faites bien attention au type d'inférence de type lorsque vous utiliser ''auto'' et ''decltype''. | + | Faites bien attention au type d'inférence de type lorsque vous utilisez ''auto'' et ''decltype''. |
| ==== Validité d'une indirection ==== | ==== Validité d'une indirection ==== | ||
| - | Les indirections sont des outils très puissant en C++ (et d'autres langages bas niveau). Cependant, elles ont une contrainte d'utilisation qui peut être très problématique : elles ne sont valides que tant que l'élément correspondant est accessible. Si la collection est déplacée ou supprimée, une indirection va correspondre à un élément invalide et tenter d'y accéder produira un comportement indéterminé. | + | Les indirections sont des outils très puissants en C++ (et d'autres langages bas niveau). Cependant, elles ont une contrainte d'utilisation qui peut être très problématique : elles ne sont valides que tant que l'élément correspondant est accessible. Si la collection est déplacée ou supprimée, une indirection va correspondre à un élément invalide et tenter d'y accéder produira un comportement indéterminé. |
| Et il y a un problème encore plus important : | Et il y a un problème encore plus important : | ||
| Ligne 460: | Ligne 467: | ||
| Il est facile de comprendre que puisque la chaîne ''s'' ne contient plus aucun élément, accéder au premier élément n'a aucun sens. | Il est facile de comprendre que puisque la chaîne ''s'' ne contient plus aucun élément, accéder au premier élément n'a aucun sens. | ||
| - | Notez bien que ce code ne produit pas d'erreur ! Le code s’exécute sans problème et ne semble pas présenter d'erreur. C'est le principe des comportements indéfinis (//Undefined Behavior//, UB) : cela ne produit pas forcement une erreur, cela peut sembler fonctionner et il est difficile de détecter (et donc de corriger) ce type d'erreur. | + | Notez bien que ce code ne produit pas d'erreur ! Le code s’exécute sans problème et ne semble pas présenter d'erreur. C'est le principe des comportements indéfinis (//Undefined Behavior//, UB) : cela ne produit pas forcément une erreur, cela peut sembler fonctionner et il est difficile de détecter (et donc de corriger) ce type d'erreur. |
| C'est de la responsabilité du développeur de prendre les précautions nécessaires pour ne pas avoir ce type d'erreur. Heureusement, il existe des bonnes pratiques et des outils d'analyse statique pour aider à limiter ces erreurs. | C'est de la responsabilité du développeur de prendre les précautions nécessaires pour ne pas avoir ce type d'erreur. Heureusement, il existe des bonnes pratiques et des outils d'analyse statique pour aider à limiter ces erreurs. | ||
| - | **Ne sous-estimez pas la difficulté que représente ce type d'erreur. C'est une problématique qui n'a pas été résolue de façon sûre depuis la création du C++ (et du C). De nombreuses évolutions récentes du langage C++ vise à limiter ces problématiques.** | + | **Ne sous-estimez pas la difficulté que représente ce type d'erreur. C'est une problématique qui n'a pas été résolue de façon sûre depuis la création du C++ (et du C). De nombreuses évolutions récentes du langage C++ visent à limiter ces problématiques.** |
| - | Pour terminer, une précision sur pourquoi cela pose problème de corriger les itérateurs lorsqu'ils deviennent invalides. Pour cela, il faudrait que à chaque fois qu'une collection fait une opération qui invalide des itérateurs, il faut parcourir l'ensemble des itérateurs et les mettre à ''std::end''. Faire cela est possible, mais peut être coûteux, sans que cela soit indispensable (si le développeur à correctement sécurisé son code). | + | Pour terminer, une précision sur pourquoi cela pose problème de corriger les itérateurs lorsqu'ils deviennent invalides. Pour cela, il faudrait qu'à chaque fois qu'une collection effectue une opération qui invalide des itérateurs, parcourir l'ensemble des itérateurs et les mettre à ''std::end''. Faire cela est possible, mais peut être coûteux, sans que cela soit indispensable (si le développeur a correctement sécurisé son code). |
| - | La philosophie du C++ est de ne pas payer pour ce dont on n'a pas pas besoin. Sécuriser les collections pour ce problème ne peut donc pas être proposé par défaut. (Mais cela est possible, vous pourrez faire cela en exercice après la partie sur la programmation orientée objet). | + | La philosophie du C++ est de ne pas payer pour ce dont on n'a pas besoin. Sécuriser les collections pour ce problème ne peut donc pas être proposé par défaut. (Mais cela est possible, vous pourrez faire cela en exercice après la partie sur la programmation orientée objet). |
| ^ [[rechercher|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[autres_collections|Chapitre suivant]] ^ | ^ [[rechercher|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[autres_collections|Chapitre suivant]] ^ | ||
iterateurs.1467493589.txt.gz · Dernière modification: 2016/07/02 23:06 par gbdivers
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported
