Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

--- iterateurs [2016/01/18 06:04]
gbdivers
+++ iterateurs [2018/12/10 23:35] (Version actuelle)
winjerome Correction orthographique
@@ Ligne 1: / Ligne 1: @@
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
+^ [[rechercher|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[autres_collections|Chapitre suivant]] ^
@@ Ligne 14: / Ligne 14: @@
 ===== 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 ''begin'' et ''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>
@@ Ligne 21: / Ligne 21: @@
 </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 :
@@ 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>''".
-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>
-std::sort(begin(v1), end(v2)); // erreur
+std::sort(std::begin(v1), std::end(v2)); // erreur
 </code>
@@ Ligne 40: / Ligne 40: @@
 ==== Reverse et Const-correctness ====
-Il existe en fait plusieurs versions des fonctions ''begin'' et ''end'' :
+Il existe en fait plusieurs versions des fonctions ''std::begin'' et ''std::end'' :
   * les itérateurs "reverse", qui permettent de parcourir une collection de la fin vers le début ;
   * 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'' ;
@@ Ligne 51: / Ligne 51: @@
   * ''std::cbegin'' et ''std::cend'' ;
   * ''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 forcément les fonctions libres. Dans ce cas, vous pouvez utiliser les fonctions membres, qui seront toujours disponibles.
+<code cpp>
+std::begin(v)  // fonction libre
+v.begin() // fonction membre
+</code>
+</note>
 Les itérateurs "reverse" permettent de parcourir une collection depuis la fin vers le début.
@@ Ligne 61: / Ligne 69: @@
 int main() {
     std::string s { "azerty" };
-    std::sort(begin(s), end(s));
+    std::sort(std::begin(s), std::end(s));
     std::cout << s << std::endl;
-    std::sort(rbegin(s), rend(s));
+    std::sort(std::rbegin(s), std::rend(s));
     std::cout << s << std::endl;
 }
@@ Ligne 77: / Ligne 85: @@
 L'effet est le même que si vous aviez trié la collection en utilisant l'opérateur "plus grand que" (''std::greater'') au lieu de l'opération par défaut "plus petit que".
-<note>Vous pourriez être tenté, pour parcourir une collection depuis la fin vers le début, d'utiliser un algorithme en donnant ''end'' avant ''begin''.
+<note>Vous pourriez être tenté, pour parcourir une collection depuis la fin vers le début, d'utiliser un algorithme en donnant ''std::end'' avant ''std::begin''.
 <code cpp>
-std::sort(end(s), begin(s));
+std::sort(std::end(s), std::begin(s));
 </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 |}}
-En passant ''end'' puis ''begin'' en argument, l'algorithme va commencer à parcourir la collection à ''end'', mais va aller vers la droite. Il ne rencontrera jamais ''begin'' et ne s'arrêtera que lorsque votre programme va crasher. En utilisant ''rbegin'' et ''rend'', l'algorithme va aussi commencer vers la fin de la collection, mais va la parcourir vers la gauche. Il rencontrera ''rend'' et s'arrêtera donc correctement au début de la collection, après l'avoir parcouru.
+En passant ''std::end'' puis ''std::begin'' en argument, l'algorithme va commencer à parcourir la collection à ''end'', mais va aller vers la droite. Il ne rencontrera jamais ''std::begin'' et ne s'arrêtera que lorsque votre programme va crasher. En utilisant ''std::rbegin'' et ''std::rend'', l'algorithme va aussi commencer vers la fin de la collection, mais va la parcourir vers la gauche. Il rencontrera ''std::rend'' et s'arrêtera donc correctement au début de la collection, après l'avoir parcouru.
 </note>
-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>
-const auto first { begin(v); };
+const auto first { std::begin(v) };
-first = 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
 </code>
@@ Ligne 105: / Ligne 113: @@
 <code cpp>
-auto first { cbegin(v); };
+auto first { std::cbegin(v) };
-first = 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
 </code>
@@ Ligne 115: / Ligne 123: @@
 const std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
 std::string s2       { "........................................" };
-std::copy(cbegin(s1), cend(s1), begin(s2));
+std::copy(std::cbegin(s1), std::cend(s1), std::begin(s2));
 </code>
-Pour rappel, ce code copie les éléments de la première collection (''s1'') dans la seconde (''s2''). La première collection n'est pas modifiée, elle est donc constante. Dans le code, cette constance est exprimée par le mot-clé ''const'' dans la déclaration de la collection ''s1'' et dans l'utilisation des fonctions retournant des itérateurs constants ''cbegin'' et ''cend''.
+Pour rappel, ce code copie les éléments de la première collection (''s1'') dans la seconde (''s2''). La première collection n'est pas modifiée, elle est donc constante. Dans le code, cette constance est exprimée par le mot-clé ''const'' dans la déclaration de la collection ''s1'' et dans l'utilisation des fonctions retournant des itérateurs constants ''std::cbegin'' et ''std::cend''.
-La seconde collection est modifiée, elle n'est donc pas déclarée comme constante et la fonction ''begin'' est utilisée.
+La seconde collection est modifiée, elle n'est donc pas déclarée comme constante et la fonction ''std::begin'' est utilisée.
 ==== 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>
@@ Ligne 134: / Ligne 142: @@
     std::string s1 { "azerty" };
-    std::string s2(begin(s1), end(s1));
+    std::string s2(std::begin(s1), std::end(s1));
     std::cout << s2 << std::endl;
-    std::string s3(begin(s1), begin(s1) + 3);
+    std::string s3(std::begin(s1), std::begin(s1) + 3);
     std::cout << s3 << std::endl;
 }
@@ Ligne 159: / Ligne 167: @@
 <code cpp>
 std::string s2(s1.size());
-std::copy(begin(s1), end(s1), begin(s2));
+std::copy(std::begin(s1), std::end(s1), std::begin(s2));
 </code>
 L'initialisation avec une paire d'itérateurs permet de simplifier le code et d'utiliser ''const'' plus facilement dans ce cas.
-La déclaration de la variable ''s3'' utilise une opération arithmétique sur un itérateur : ''begin(s1) + 3''. Vous allez voir plus en détail cette syntaxe par la suite, mais il suffit simplement de comprendre pour le moment que la syntaxe ''begin(s1), begin(s1) + 3'' permet de prendre les trois premiers éléments.
+La déclaration de la variable ''s3'' utilise une opération arithmétique sur un itérateur : ''std::begin(s1) + 3''. Vous allez voir plus en détail cette syntaxe par la suite, mais il suffit simplement de comprendre pour le moment que la syntaxe ''std::begin(s1), std::begin(s1) + 3'' permet de prendre les trois premiers éléments.
-==== Itérateur retourné par une recherche ====
+==== Intervalle semi-ouvert ====
+Les fonctions ''std::begin'' et ''std::end'' ne sont pas les seules fonctions à retourner un itérateur. Plusieurs algorithmes retournent également un itérateur, comme ''std::find'' pour rechercher une valeur dans une collection ou ''std::partition'' pour séparer une collection en deux sous-collections.
-Pourquoi cette façon de faire ? Avec ''find'', si aucun élément n'est trouvé, comment indiquer que la recherche a échoué ? Une solution serait que ''find'' retourne un booléen en plus. Mais ce serait compliqué à gérer. La solution choisie est qu'elle retourne ''end()'' si la recherche échoue.
+Par exemple, avec ''std::find'' pour trouver un élément puis créer deux sous-collections :
-Donc tester le résultat de ''find'' :
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    const std::string s { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    const auto it = std::find(std::begin(s), std::end(s), '8');
+    std::cout << std::string(std::begin(s), it) << std::endl;
+    std::cout << std::string(it, std::end(s)) << std::endl;
+}
+</code>
-<code cpp>
+affiche :
-auto p = std::find(begin(v), end(v), 3);
-std::cout << boolalpha << (p == end(v)) << endl;
+<code>
-p = std::find(begin(v), end(v), 10);
+f9c02b6c9da
-std::cout << boolalpha << (p == end(v)) << endl;
+feaea4966ba7417d65de2fe7e
 </code>
-Comme ''end(v)'' ne représente pas un élément dans une collection, il est interdit de le manipuler comme les autres positions. Ainsi, il est légal d'écrire ''begin(v)+1'', puisque ''begin(v)'' est une position correspondante à un élément dans la collection (s'il y a au moins un élément dans la collection), on a le droit de le manipuler. Au contraire, ''end(v)+1'' est interdit. C'est pour cela que la notion ''begin(v)+n'' est dangereuse, puisque l'on peut accéder à une position invalide, si ''n > size()''.
+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.
-__advance ? next ?__
+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"''.
-Supposons que l'on ait plusieurs fois la même valeur dans une collection. Comment toutes les trouver avec ''find'' ?
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    const std::string s { "abcdefghijk" };
+    const auto first = std::find(std::begin(s), std::end(s), 'd');
+    const auto last = std::find(std::begin(s), std::end(s), 'i');
+    std::cout << std::string(first, last) << std::endl;
+}
+</code>
-On recherche d'abord sur l'intervalle qui nous intéresse avec ''begin'' et ''end''. Puis, si on trouve un élément (donc si ''p != end''), alors on peut refaire la recherche entre ''p+1'' et ''end'' pour trouver un deuxième élément. Et ainsi de suite, jusqu'à trouver tous les éléments.
+{{ :end.png |}}
+Il se pose alors une question : que représente l'itérateur retourné par ''std::end'' ? Si ''std::end'' retourne un itérateur sur le dernier élément (par exemple 'k' dans le dernier exemple), alors la chaîne créée en utilisant les itérateurs retournés par ''std::begin'' et ''std::end'' correspondrait à la chaîne ''"abcdefghij"'' et non à la chaîne ''"abcdefghijk"'' (la chaîne sans le dernier caractère).
-<code cpp>
+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 produit un comportement indéterminé.
+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.
+Cet itérateur invalide retourné par ''std::end'' a une utilisation particulière avec les algorithmes de recherche, il est retourné lorsque la recherche échoue. Par exemple, si vous essayez de rechercher le caractère "1" dans la chaîne "abcdefghijk", le recherche échoue et retourne ''std::end''.
+<code cpp main.cpp>
 #include <iostream>
 #include <string>
@@ Ligne 196: / Ligne 240: @@
 int main() {
-    std::string const s { "azertyazerty" };
+    const std::string s { "abcdefghijk" };
-    auto position = std::find(std::begin(s), std::end(s), 'e');
+    const auto it = std::find(std::begin(s), std::end(s), '1');
-    auto const first = std::string(std::begin(s), position);
+    std::cout << std::boolalpha << (it == std::end(s)) << std::endl;
-    auto const second = std::string(position, std::end(s));
-    std::cout << first << std::endl;
-    std::cout << second << std::endl;
-    position = std::find(position+1, std::end(s), 'e');
-    std::cout << std::string(std::begin(s), position) << std::endl;
-    std::cout << std::string(position, std::end(s)) << std::endl;
 }
 </code>
@@ Ligne 212: / Ligne 249: @@
 <code>
-az
+true
-ertyazerty
-azertyaz
-erty
 </code>
-second ''find'' : recherche à partir du 'e' trouvé
+Avant d'utiliser un itérateur retourné par ''std::begin'' ou un algorithme, il est nécessaire de tester la validité avant utilisation.
-<note>Pour une collection vide ({} ou ""), il n'y a pas d'élément et ''begin == end''.</note>
+<code cpp>
+assert(it != std::end(s));
+</code>
+<note>**Assertion**
-==== Ce que représente std::end ====
+''assert'' est une fonction qui vérifie qu'une condition est valide et arrête le programme si ce n'est pas le cas. Ce comportement est bien sûr un comportement qui ne doit pas arriver à l'utilisateur final de vos logiciels. C'est un outil qui sert à vérifier s'il y a des erreurs de programmation, qui doivent être corrigées avant de publier un logiciel.
-Pour effectuer une recherche dans une collection, on peut utiliser ''find''. Si on regarde la documentation, elle indique que cette fonction prend un //range// et un élément à chercher, elle retourne l'itérateur (donc une position) de l'élément dans la collection s'il a été trouvé, sinon l'itérateur ''end''.
+Cette fonction est disponible dans le fichier d'en-tête ''<cassert>''.
+</note>
-&lt;code cpp&gt;
+Une collection vide (par exemple ''{}'' ou une chaîne vide ''&quot;&quot;'') 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.
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
-auto position = std::find(std::begin(v), std::end(v), 3);
+<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) exclut les valeurs 0 et 1, (0, 1] exclut 0 et inclut 1, etc.</note>;
+===== Notion d'indirection =====
+Lorsque vous créez une variable, cela permet de créer un objet en mémoire, qui sera accessible directement avec cette variable. Chaque variable que vous créez correspond à un objet différent en mémoire, si vous créez une nouvelle variable à partir d'une variable existante, cela copie le premier objet. Si vous modifiez ensuite le second objet, le premier ne sera pas modifié.
+Il existe plusieurs types d'indirection en C++ : les références, les pointeurs et les itérateurs. Les syntaxes présentent quelques différences, mais également des principes communs. Les itérateurs sont utilisés avec les collections, les références et pointeurs seront utilisés avec les fonctions (dans la partie "Créer ses algorithmes") et l'allocation dynamique (dans la partie Programmation Orientée Objet).
+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 ;
+  * //préfixé// signifie que l'opérateur s'écrit avant son argument.
+Plus concrètement, il faut donc écrire :
+<code>
+*it
 </code>
-On peut alors utiliser cette position pour créer deux sous-collections :
+É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>
 #include <iostream>
 #include <vector>
-#include <algorithm>
 int main() {
-    std::vector<int> v1 { 1, 2, 3, 4, 5 };
+    const std::vector<int> v { 12, 23, 34 };
-    auto p = std::find(std::begin(v1), std::end(v1), 3);
+    const auto it = std::cbegin(v);
+    std::cout << (*it) << std::endl;
+}
+</code>;
-    std::vector<float> v2(std::begin(v1), p);
+affiche :
-    for (auto i: v2) std::cout << i << ' ';
-    std::cout << std::endl;
-    std::vector<float> v3(p, std::end(v1));
+<code>
-    for (auto i: v3) std::cout << i << ' ';
-    std::cout << endl;
+</code>
+Modifier un itérateur après déréférencement permet de modifier l'élément correspondant dans la collection.
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+int main() {
+    std::string s { "abcdef" };
+    const auto it = std::begin(s);
+    std::cout << s << std::endl;
+    (*it) = 'A';
+    std::cout << s << std::endl;
 }
 </code>
@@ Ligne 256: / Ligne 326: @@
 <code>
-2
+abcdef
-4 5
+Abcdef
 </code>
-On voit ici une particularité importante des //ranges//. La variable ''p'' correspond à la position de la valeur ''3'' dans la collection. On pourrait croire que la collection ''v2'' qui est créée à partir de ''begin(v1)'' et ''p'' allait contenir les éléments ''{ 1, 2, 3 }'', mais ce n'est pas le cas.
+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 :
-En effet, un //range// est une paire d'itérateurs dont le premier est inclus et le second exclu.
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
-&lt;note&gt;On écrira souvent ''[first, last)'' pour désigner un //range//. Cette notation mathématique permet d'écrire un ensemble, 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>
+int main() {
+    std::string s { &quot;abcdef&quot; };
+    const auto it = std::cbegin(s);  // cbegin au lieu de begin
+    std::cout << s << std::endl;
+    (*it) = 'A';
+    std::cout << s << std::endl;
+}
+</code>
-Revenons sur un code précédent. Lorsque l'on écrit :
+affiche :
-<code cpp>
+<code>
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
+main.cpp:8:11: error: cannot assign to return value because
-std::vector<int> v2(std::begin(v1), std::end(v1));
+function 'operator*' returns a const value
+    (*it) = 'A';
+    ~~~~~ ^
 </code>
-On a bien une copie complète de ''v1''. Est-ce que cela est compatible avec l'exclusion de la borne supérieure du //range// ? En fait, oui, tout simplement parce que ''end(v1)'' correspond à la fin de la collection, et non au dernier élément de cette collection. Si on crée des sous-collections depuis les premiers et derniers éléments :
+L'erreur signifie que la valeur retournée par l'opérateur ''*'' est une valeur constante et ne peut être assignée.
-<code cpp>
+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.
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
-// premier élément ?
+<code cpp main.cpp>
-std::vector<int>; v2(std::begin(v1), std::begin(v1));
+#include <iostream&gt;
-std::cout <&lt; boolalpha <&lt; v2.empty() << std::endl; // vide
+#include <string&gt;
-// premier élément
+int main() {
-std::vector&lt;int&gt; v3(std::begin(v1), std::begin(v1)+1);
+    std::string s { &quot;abcdef&quot; };
-for (auto i: v3) std::cout << i << ' '; // ok, contient {1}
+    const auto it1 = std::begin(s);
+    const auto it2 = std::begin(s);
+    std::cout << (*it2) << std::endl;
+    (*it1) = 'A';
+    std::cout << (*it2) << std::endl;
+}
+</code>
-// dernier élément ?
+affiche :
-std::vector<int> v4(std::end(v1), std::end(v1));
-std::cout << boolalpha << v4.empty() << std::endl; // vide
-// dernier élément
+<code>
-std::vector<int>; v5(std::end(v1)-1, std::end(v1));
+a
-for (auto i: v5) std::cout << i << ' '; // ok, contient {5}
+A
 </code>
-En pratique, cela signifie que ''end(v)'' ne représente pas le dernier élément d'une collection, mais un élément supplémentaire et imaginaire qui se trouverait après le dernier élément.
+==== Inférence de type après déréférencement ====
-{{ :end.png |}}
+Si vous essayez de créer une variable avec ''auto'' pour contenir l'élément après déréférencement, vous perdez l'indirection :
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
-===== Notion d'indirection =====
+int main() {
+    std::string s { "abcdef" };
+    const auto it = std::begin(s);
+    auto c = (*it);
+    std::cout << s << std::endl;
+    c = 'A';
+    std::cout << s << std::endl;
+}
+</code>
-==== Accéder à un élément d'une collection ====
+affiche :
-Lorsque un itérateur correspond à une position valide dans une collection (donc pas end), il est possible d'accéder à l'élément en utilisant l'opérateur * devant l'itérateur :
+<code>
+abcdef
-<code cpp>
+abcdef
-vector<int> v { 1, 2, 3, 4, 5 };
-auto p = begin(v);
-cout << (*p) << endl;
 </code>
-affiche 1
+La ligne modifiant la variable ''c'' ne modifie pas la collection, ce n'est plus une indirection.
-Egalement accessible en modification (si non const) :
+La raison est que ''auto'' ne conserve pas les modificateurs de type, en particulier les indirections. Ce code est donc équivalent au code suivant :
-<code cpp>
+<code>
-auto p = begin(v) + 3;
+char c = (*it);
-*p = 0;
-for (auto value: v)
-    cout << value << endl;
 </code>
-Si fonction template :
+Ce qui permet de copier l'élément correspondant à l'itérateur dans une nouvelle variable, pas de créer une indirection sur cet élément.
-<code cpp>
+Pour régler ce problème, vous pouvez utiliser des références (que vous verrez ensuite) ou utiliser ''decltype(auto)'' pour l'inférence de type. (Pour rappel, ''decltype'' et ''decltype(auto)'' conservent les modificateurs de type, au contraire de ''auto'').
-template<class Iterator>
-void foo(Iterator it) {
+<code cpp main.cpp>
-    auto value = *it;
+#include <iostream>
+#include <string>
+int main() {
+    std::string s { "abcdef" };
+    const auto it = std::begin(s);
+    decltype(auto) c = (*it);
+    std::cout << s << std::endl;
+    c = 'A';
+    std::cout << s << std::endl;
 }
 </code>
-it est un itérateur sur un élément d'un conteneur, donc *it correspond à un élément d'un conteneur. Le type déduit par auto est le type de cet élément
+affiche :
-<code cpp>
+<code>
-std::vector<int> v {};
+abcdef
-foo(begin(v)); // dans foo, it est de type vector<int>::iterator et *it est de type int
+Abcdef
 </code>
-<note>Il est possible d'expliciter auto. Pour cela, il faut pouvoir récupérer le type d'un itérateur et le type de valeur pointé. Pour cela, il faut utiliser la classe de trait iterator_traits :
+Faites bien attention au type d'inférence de type lorsque vous utilisez ''auto'' et ''decltype''.
-<code cpp>
-template<class Iterator>
-void foo(Iterator it) {
-    typename iterator_traits<Iterator>::value_type value = *it;
-}
-</code>
-__ explication sur typename ? sur classe de traits ? __
+==== Validité d'une indirection ====
-On comprend l'intérêt de auto dans ce code.
+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é.
-</note>
+Et il y a un problème encore plus important :
-===== Catégories d'itérateurs =====
+**Il n'est pas possible de tester une indirection pour vérifier qu'elle est valide ou non !**
+Cette phrase peut paraître étrange, puisque vous avez vu qu'il était possible de tester un itérateur pour savoir s'il correspond à ''std::end'' ou non, pour savoir s'il est valide ou non. Pourquoi n'est-il pas possible de tester la validité d'une indirection dans ce cas ?
+Pour commencer, un exemple de code montrant le problème :
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+int main() {
+    std::string s { "abcdef" };
+    const auto it = std::begin(s);
+    std::cout << s << std::endl;
+    s.clear();
+    (*it) = 'z'; // à quel élément correspond (*it) ?
+}
+</code>
-Iterateur, bidirectional, random. Possibilité de manipuler directement les éléments d'une collection. Via itérateur (le plus générique) et pour certains types de collection par [] ou at(). next, prev, advance, distance
+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.
-Vu comment accéder séquentiellement dans un conteneur (du début à la fin). Méthode la plus simple et la plus performante. Autre méthode : accéder directement à un élément dans le conteneur. Faisable sur certain type de conteneur, dont array et vector.
+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.
-Utilisation de at() et []
+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.
-Vérification des limites d'accès
+**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 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).
-===== Adaptateurs d'itérateurs =====
+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).
-Adaptateur : back_inserter, front_inserter, inserter etc
+^ [[rechercher|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[autres_collections|Chapitre suivant]] ^
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^

C++, Qt, OpenGL, CUDA

Outils d'utilisateurs

Outils du Site

Différences

Outils de la Page