Différences

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

--- boucles [2016/11/05 16:12]
gbdivers
+++ boucles [2016/12/02 00:46] (Version actuelle)
gbdivers
@@ Ligne 3: / Ligne 3: @@
 Le chapitre précédent présentait le premier type de structure de contrôle permettant de ne pas avoir une séquence linéaire d'instructions. Ce chapitre présente le second type de structure de contrôle, permettant de répéter plusieurs fois une même séquence d'instructions.
+La notion de "répéter une tâche" vous est familier dans la vie courante. Par exemple, compter de un à dix sur ses doigts peut être considéré comme une boucle, dans laquelle vous comptez un doigt supplémentaire à chaque itération et vous vous arrêtez lorsque vous avez comptez tous vos doigts. Pour lire un livre, vous allez lire une page, passer à la suivante et recommencer, jusqu'a la derniere pages. Si vous jouez à un jeu vidéo, vous allez avancer votre personnage, évaluer la situation, agir en conséquence, puis recommencer jusqu'à arriver à la fin du jeu.
+En programmation, une boucle est similaire : répéter une tâche (une séquence d'instructions) jusqu'à atteindre le but recherché.
+Les boucles sont particulièrement utiles avec les collections, pour réaliser une tâche quelconque sur chaque élément de la collection. Pour illustrer cela, le cas du tableau ''std::vector'' sera detaillé comme exemple.
 ====== Les instructions iteratives ======
-point important : les conditions d'arret. Une boucle se repete jusqu'a ce que la condition d'arret soit valide. Risque de boucle infinie en cas d'erreur sur la condition d'arret.
+Classiquement, une boucle peut etre decomposer en trois parties :
-Utiliser des syntaxes qui limite les risques, en determinant automatiquement les conditions d'arret.
+  * l'initialisation, c'est-à-dire ce qui sera réalisé avant de démarrer la boucle ;
+  * les instructions à réaliser a chaque itération de la boucle ;
+  * une condition à vérifier pour terminer la boucle.
+Par exemple, pour compter de un à dix, vous devrez :
-====== Range-for ======
+  * initialiser un compteur avec la valeur ''1'' ;
+  * a chaque itération, incrémenter le compteur ;
+  * lorsque le compteur est égal à la valeur ''10'', la boucle s'arrête.
-Va parcourir tous les elements d'une collection. Aucun risque sur la condition d'arret, puisque determinee directement par l'instruction ''for-rnage''.
+Chaque étape est importante pour que la tâche soit correctement réalisée. Si vous réinitialisez le compteur avec la valeur ''5'', vous aurez compte que cinq fois lorsque la boucle s'arretera. Idem si incrément de deux le compteur a chaque itération. Et la condition d'arrêt n'est pas correcte, le compteur ne sera pas non plus correct.
-Syntaxe :
+Cependant, les erreurs mentionnées précédemment produisent "simplement" un résultat faux. Il existe en réalité un problème plus grave : les boucles infinies, qui ne se terminent jamais. Une telle boucle mène au blocage du programme, puis à son crash (automatique lorsque la mémoire est saturée, ou provoquée par l'utilisateur).
+Il n'est pas possible de proposer une syntaxe, quelque soit le langage de programmation, qui empêcherait celui qui écrit le code de ne pas faire d'erreur de logique et d'ecrire une boucle qui ne realise pas la tache accomplie. (C'est le rôle des tests unitaires de vérifier cela, vous verrez cela dans un prochain chapitre).
+Par contre, il est possible de proposer des syntaxes qui limiteront le risque d'ecrire des boucles infinies. Pour cette raison, il existe plusieurs syntaxes possible en C++ pour ecrire des boucles. Dans ce chapitre, les syntaxes seront présentées dans l'ordre du plus sécurisé au moins sécurisé.
+===== Les boucles range-for =====
+==== Syntaxe de base ====
+Les boucles //for// sur un intervalle (//range-based for loop//, qui est souvent simplifie en //range-for//) permettent de parcourir la totalité d'une collection. La syntaxe est la suivante :
 <code cpp>
-for(auto&& ELEMENT: COLLECTION) {
+for(TYPE ELEMENT: COLLECTION) {
     ...
 }
 </code>
-"extrait" les elements d'une collection un par un. ''auto&& ELEMENT'' est la declaration d'une variable "ELEMENT", dont le type est deduit automatiquement par inference de type. Par exemple, ''vector<int>'' sera ''int'' et ''list<string>'' sera ''string''.
+Dans cette syntaxe, ''COLLECTION'' correspond à la collection sur laquelle la boucle est appliquée. ''ELEMENT'' est une variable locale que vous pouvez utiliser dans la boucle et qui correspond à chaque élément de la collection. Par exemple, si vous avec une collection qui contient les valeurs ''1'', ''2'', ''3'', la variable ''ELEMENT'' aura la valeur ''1'' lors de la premiere iteration, puis la valeur ''2'' lors de la deuxième itération, puis pour terminer la valeur ''3'' lors de la troisième itération.
+Par exemple, pour parcourir un tableau :
 <code cpp>
@@ Ligne 31: / Ligne 56: @@
 int main() {
     std::vector<int> v { 1, 2, 3 };
-    for(auto&& i: v) {
+    for(int i: v) {
         std::cout << i << std::endl;
     }
@@ Ligne 45: / Ligne 70: @@
 </code>
-Directement utilisation sur un liste de valeurs (//initializer-list//) ou une chaine de caracteres (qui peut etre vu comme un tableau de caracteres) :
+==== Le type de l'élément ====
+Le type ''TYPE'' correspond au type de la variable représentant chaque élément dans la boucle. Cela peut être le type de l'élément dans la collection ou n'importe quel type convertible.
+Par exemple, pour une collection de type ''std::vector<int>'', il est possible d'utiliser le type ''int'' (comme dans l'exemple précédent), mais également ''int&'' (référence sur un entier), ''long int'' (conversion vers un type plus large).
+Note : il est egalement possible d'utiliser un type moins large (par exemple ''short int''), mais cela peut produire un message d'avertissement dans ce cas.
+<code>
+warning: implicit conversion loses integer precision: 'int' to 'short' [-Wconversion]
+    for (short int i: v) {
+                   ~^
+</code>
+Sauf cas particulier, il n'est pas utile de réaliser une conversion de type et il est plus simple d'utiliser exactement le même type dans la boucle //range-for// que le type de l'élément dans la collection (donc pour une collection de type ''std::vector<int>'', utiliser ''int''). De fait, le plus simple est d'utiliser la déduction de type dans ce cas, ce qui permet en plus d'avoir un code plus évolutif (si vous changez le type de la collection, vous n'avez pas besoin de changer le type utilisé dans la boucle //range-for//).
+Avec la déduction de types, le code précédent devient :
 <code cpp>
 #include <iostream>
+#include <vector>
 int main() {
-    for(auto&amp;&amp; i: { 1, 2, 3 }) {
+    std::vector&lt;int&gt; v { 1, 2, 3 };
+    for(auto i: v) {
         std::cout << i << std::endl;
     }
+}
-    for(auto&& c: "hello") {
+</code>
+Pour rappel, le mot-clé ''auto'' déduit uniquement le type (''int'' dans ce cas), sans conserver les modificateurs de types (''const'' ou les references par exemple). Il peut donc être intéressant d'ajouter des modificateurs de types, en fonction du type d'éléments et de ce que vous souhaitez faire. Le choix des modificateurs est la même problématique que celle que vous avez vu pour les parametres de fonctions :
+  * si vous souhaitez modifier la valeur, il faut utiliser une référence ;
+  * si vous ne souhaitez pas modifier la valeur et que le type est un type fondamentale (la copie est peu coûteuse), il faut utiliser un passage par valeur ;
+  * si vous ne souhaitez pas modifier la valeur et que le type est complexe (la copie est coûteuse), il faut utiliser une référence constante.
+<code cpp>
+const vector<int> v { 1, 2, 3, 4 };
+for (auto i: v) {
+    std::cout << i << std::endl;
+}
+vector<int> v { 1, 2, 3, 4 };
+for (auto & i: v) {
+    ++i; // v contient { 2, 3, 4, 5 } apres la boucle
+}
+const vector<std::string> v { "hello", "world" };
+for (auto const& s: v) {
+    std::cout << s << std::endl;
+}
+</code>
+<note>**Reference universelle**
+Une autre solution est d'utiliser une référence universelle. Ce type de référence s'adapte en fonction du type de collection et de l'élément. La syntaxe est la suivante :
+<code cpp>
+for (auto && x: v) ...
+</code>
+La syntaxe est similaire à une référence sur une //rvalue//, mais en utilisant ''auto''.
+</note>
+==== Avec les collections associatives ====
+Pour rappel, une collection associative est une collection qui associe une valeur a une cle, comme par exemple ''std::map''. Ce type de collection ne contient pas des valeurs, mais des paires de clés et valeurs. Il faut donc adapter l'utilisation des boucles //range-for// en consequence. Pour cela, il faut utiliser les accesseurs ''first'' et ''second'' correspondant au type ''std::pair'' utilise dans une ''std::map''.
+Par exemple :
+<code cpp main.cpp>
+#include <iostream>
+#include <map>
+#include <string>
+int main() {
+    std::map<int, std::string> m { { 1, "hello" }, { 2, "world" } };
+    for (auto const& p: m) {
+        std::cout << p.first << ": " << p.second << std::endl;
+    }
+}
+</code>
+affiche :
+<code>
+: hello
+: world
+</code>
+L'utilisation de la déduction de type est particulièrement intéressant dans ce cas, pour éviter de devoir utiliser explicitement ''std::pair'' (ce qui alourdi la syntaxe). Sans la déduction de types, il faudrait ecrire :
+<code cpp>
+for (std::pair<int, std::string> const& p: m) ...
+</code>
+Les collections de la bibliothèque standard qui nécessitent l'utilisation de ''std::pair'' sont celle contenant "map" : ''std::map'', ''std::multimap'', ''std::unordered_map'' et ''std::unordered_multimap''.
+==== Avec d'autres types de conteneurs ====
+Les boucles //range-for// sont utilisables avec d'autres types de conteneurs que les collections de la bibliothèque standard :
+  * les tableaux hérités du C (qui sont à éviter en C++ moderne, sauf cas d'utilisation spécifiques) ;
+  * les chaines de caracteres (qui sont assimilables à des collections de caractères) ;
+  * les listes de valeurs (//initializer-list//).
+Utiliser une boucle //range-for// avec une chaîne de caractères permet d'accéder directement a chaque caractère.
+<code cpp>
+#include <iostream>
+int main() {
+    for(auto c: "hello") {
         std::cout << c << std::endl;
     }
@@ Ligne 64: / Ligne 192: @@
 <code>
 h
 e
@@ Ligne 74: / Ligne 199: @@
 </code>
-Note : futur C++ (ou a implementer soi meme) les vues qui sont un sous-collection d'une collection.
+Les listes de valeurs sont particulierement interessantes, puisque cela permet d'ecrire directement une liste de valeur dans une boucle //range-for//. Par exemple :
+<code cpp main.cpp>
+#include <iostream>
-====== Les algorithmes de la bibliothèque standard ======
+int main() {
+    for(auto i: { 1, 2, 3, 4 }) {
+        std::cout << i << std::endl;
+    }
+}
+</code>
+affiche :
+<code>
+
+
+
+
+</code>
-Les algos ne sont pas des instruction iteratives, mais il est bien de les rappeler.
+<note>**Les vues [C++17]**
-Permet d'appliquer une tache sur chaque element d'une collection. En interne, cela utilise donc bien des iterations. Relativement safe, puisque l'on passe des iterateurs sur le premier element a traiter et le premier element qui ne dois plus l'etre.
+Dans la prochaine norme du C++ (le C++17) est ajouté un nouveau concept : les vues. Les vues sont des collections qui permettent d'accéder aux éléments d'une autre collection. Cela permet de créer une sous-collection, sans copier les donnees.
 <code cpp>
+std::string      s1 { "hello, world" };
+std::string      s2 { std::begin(s), std::begin(s) + 5 }; // copie contenant "hello"
+std::string_view s3 { std::begin(s), std::begin(s) + 5 }; // vue sur la sous-chaîne "hello"
+for (auto & c: s2) {
+    c = std::to_upper(c);
+}
+std::cout << s1 << std::endl; // affiche "hello, world"
+for (auto & c: s3) {
+    c = std::to_upper(c);
+}
+std::cout << s1 << std::endl; // affiche "HELLO, world"
+</code>
+</note>
+===== Interlude : les algorithmes standards =====
+Les algorithmes de la bibliothèques standard **ne sont pas** des instructions iteratives. Mais beaucoup utilisent en interne des boucles et peuvent être utilisés à leur place, lorsque vous travaillez sur des collections.
+En termes de sécurité du code, les algorithmes prennent généralement en paramètre des paires d'itérations. Vous avez donc la garantie qu'ils ne seront pas appelés sur des collections de types differents.
+<code cpp>
+#include <iostream>
+#include <vector>
 #include <algorithm>
 int main() {
-    const std::vector<int> v { 1, 2, 3 };
+    std::vector<int> v;
-    const auto sum = std::accumulate(std::begin(v), std::end(v), 0);
+    std::vector<double> w;
+    std::sort(std::begin(v), std::end(w));
 }
 </code>
-Toujours un risque d'erreur (se tromper entre begin/end, iterateurs sur collections differentes). Note : futur C++ avec Ranges.
+affiche un message indiquant qu'il y a un conflit pour la déduction du type d'itérateur (//deduced conflicting types//) :
+<code>
+main.cpp:8:5: error: no matching function for call to 'sort'
+    std::sort(std::begin(v), std::end(w));
+    ^~~~~~~~~
+(...) note: candidate template ignored: deduced conflicting types for parameter '_RandomAccessIterator'
+</code>
+Par contre, les algorithmes ne garantissent pas :
+  * que les itérateurs proviennent de la même collection ;
+  * que les itérateurs sont dans le bon ordre.
+Par exemple :
 <code cpp>
-std::accumulate(std::end(v), std::begin(v), 0);
+std::vector<int> v;
-std::accumulate(std::begin(v), std::end(w), 0);
+std::vector<int> w;
+std::sort(std::begin(v), std::end(w));  // (#1)
+std::sort(std::end(v), std::begin(v));  // (#2)
 </code>
-Utilisation avec range-for, par exemple ''iota'' pour generer des series, ou ''generate'' pour generer des nombres aleatoires.
+Le premier appel a la fonction ''std::sort'' est invalide du fait que les deux itérateurs proviennent de collections différentes. Le second appel à la fonction ''std::sort'' est invalide du fait que le premier itérateur correspond a un élément qui se trouve après l'élément correspondant au second itérateur.
+<note>**Les ranges [C++2x]**
+Dans une prochaine norme du C++, il sera possible d'utiliser le concept de //range//, qui sont sémantiquement des paires d'itérations, ce qui apportent les deux garanties manquantes aux algorithmes.
+</note>
+Dans de nombreux cas, il sera plus intéressant et sécurisé d'utiliser les algorithmes standards (avec ou sans prédicat personnalisé) que les syntaxes itératives qui sont décrits dans la suite de ce chapitre.
+L'intérêt des algorithmes par rapport à la boucle //range-for// est qu'ils permettent de travailler sur des sous-ensembles d'une collection. En particulier, l'algorithme ''std::for_each'' peut remplacer une boucle //range-for// sur un sous-collection (en attendant l'arrivée de vues en C++).
 <code cpp>
@@ Ligne 105: / Ligne 300: @@
 #include <array>
 #include <numeric>
+#include <iterator>
 int main() {
     std::array<char, 26> alphabet;
-    std::iota(alphabet.begin(), alphabet.end(), 'a');
+    std::iota(std::begin(alphabet), std::end(alphabet), 'a');
+    std::copy(std::begin(alphabet), std::end(alphabet),
-    for(auto&& c: alphabet) {
+              std::ostream_iterator<char&gt;(std::cout, &quot; &quot;));
-        std::cout <&lt; c << ' ';
-    }
-    std::cout &lt;&lt; std::endl;
 }
 </code>
@@ Ligne 124: / Ligne 317: @@
-===== instruction for =====
+===== La boucle for =====
-éléments, tous optionnels :
+Les syntaxes précédentes sont les plus sûres, mais si vous recherchez des exemples de code sur Internet, vous les rencontrerez moins souvent que les syntaxes qui suivent. Cela s'explique par le fait que les boucles //range-for// sont un ajout "récent" du C++11 (donc plus de 5 ans...), que les algorithmes standards s'utilisent régulièrement avec les fonctions //lambdas// (qui sont egalement un ajout du C++11), et que ces deux syntaxes n'existent pas en C.
-  * initialisation
+Dans les syntaxes précédentes, les trois composantes d'une itération (initialisation, incrémentation et condition d'arrêt) sont implicites, ce qui évite de faire des erreurs en les écrivant. La boucle //for// permet d'ecrire explicitement ces trois composantes. La syntaxe générale est la suivante :
-  * test de continuation
-  * incrémentation
-syntaxe :
 <code>
@@ Ligne 140: / Ligne 329: @@
 </code>
-Par exemple, pour compter de 1 à 10, on utilise un compteur (variable entière) :
+Une particularité de la boucle //for// : il s'agit d'un test de continuation, et non un test d'arret. C'est-à-dire que la boucle continuera tant que la condition est vraie (au lieu de s'arrêter dès que la condition est vraie).
+Par exemple, pour compter de 1 à 10, il faut :
+  * initialiser une variable avec la valeur 1 ;
+  * incrementer de 1 cette variable ;
+  * tant que la variable est inférieure ou égale à la valeur 10, continuer la boucle.
+Chacune de ces composants sont facilement traduit en C++ :
-  * initialisation à 1
+  * initialisation : ''int i { 1 }'' ;
-  * s'arrête lorsque == à 10
+  * incrementation : ''++i'' ;
-  * incrémente à chaque boucle
+  * condition d'arret : ''i <= 10''.
-devient :
+En utilisant ces syntaxes dans un boucle //for//, vous obtenez donc :
 <code>
-for (int i { 1 }; i <= 10; ++i) {
+#include <iostream>
-    std::cout << i << std::endl;
+int main() {
+    for (int i { 1 }; i <= 10; ++i) {
+        std::cout << i << std::endl;
+    }
 }
 </code>
+affiche :
-==== Parcourir un tableau ====
+<code>
+
+
+
+
+
+
+
+
+
+
+</code>
-Avec des iterateurs :
+La syntaxe de la boucle //for// est relativement compacte, et donc il est assez facile de se tromper. Vous devez vous habituer à lire correctement cette syntaxe, en identifiant bien chaque composant de la boucle (initialisation, incrémentation, condition d'arrêt). N'hésitez pas à bien aérer votre code, pour le rendre le plus lisible possible.
+==== Parcourir une collection ====
+Un cas d'utilisation classique de la boucle //for// est de parcourir une collection (lorsque la boucle //range-for// n'est pas utilisable). Pour cela, la méthode la plus générique est d'utiliser les itérateurs. Les trois composants de la boucle peuvent s'écrire :
+  * initialisation : ''auto it = std::begin(v)'' (ou ''std::cbegin'', ''std::rbegin'', ''std::crbegin'') ;
+  * incrementation : ''++it'' ;
+  * condition d'arret : ''it != std::end(v)'' (ou ''std::cend'', ''std::rend'', ''std::crend'').
+Notez l'utilisation de la déduction de type avec ''auto'' pour éviter de devoir ecrire le type complet (et long) de l'itérateur. Pour rappel :
 <code cpp>
-for (auto it = std::begin(v); it != std::end(v); ++it) {
+std::vector<int> v;
-    std::cout << (*it) << std::endl;
+std::vector<int>::iterator it { std::begin(v) };
+std::vector<int>::const_iterator cit { std::cbegin(v) };
+</code>
+Faites bien attention que ''std::begin'' retourne ''iterator'' et ''std::cbegin''' retourne ''const_iterator''.
+Le code complet pour parcourir une collection avec des itérateurs est donc le suivant :
+<code cpp main.cpp>
+#include <iostream>
+#include <list>
+int main() {
+    std::list<int> l { 1, 2, 3, 4 };
+    for (auto it = std::cbegin(l); it != std::cend(l); ++it) {
+        std::cout << (*it) << std::endl;
+    }
 }
 </code>
-Pars du premier element (begin). A chaque boucle, passe a l'element suivant (++, next aurait pu convenir aussi). S'arrete lorsque arrive a end.
+affiche :
-Condition d'arret = n'est pas executee. Donc quand it == end, la boucle n'est pas executee et (*it) non plus (ca serait invalide).
+<code>
+
+
+
+
+</code>
-Pour cela que end(v) ne correspond pas au dernier element d'une collection, mais a l'element "fictif" suivant.
+Notez que la boucle //range-for// fait exactement la même chose en interne.
-Avec l'operateur [] :
+==== Parcourir un tableau ====
+Les tableaux sont des collections et peuvent donc être parcouru en utilisant des itérateurs. Mais il est également possible de les parcourir en utilisant l'indice des éléments et l'opérateur d'indexation ''[]''. Dans ce cas, il faut ecrire une boucle //for// basé sur une variable, comme vu précédemment, et l'utiliser pour acceder aux elements.
+<code cpp main.cpp>
+#include <iostream>
+#include <vector>
-===== while et do while =====
+int main() {
+    std::vector<char> v { 'a', 'b', 'c', 'd' };
+    for (std::size_t i { 0 }; i < v.size(); ++i) {
+        std::cout << v[i] << std::endl;
+    }
+}
+</code>
-Permet de répéter un bloc d'instructions tant qu'une condition est vérifiée. Syntaxe :
+affiche :
 <code>
-while (condition) {
+a
+b
+c
+d
+</code>
+<note>**Choix du type pour l'indice**
+Le type à utiliser pour l'indice devrait être le même type que celui retourné par la fonction ''size()''. En toute rigueur, ce type est ''std::vector<int>::size_type''.
+Cependant, ce type est un peu long à ecrire et équivalent en general a ''std::size_t''. Vous verrez donc souvent ce type dans les codes.
+Il est possible d'utiliser la déduction de type, mais il faut faire attention. Si vous écrivez ''auto i = 0'', la littérale ''0'' est de type ''int'' et la variable ''i'' sera donc aussi de type ''int''. Ce qui est une erreur ! (La comparaison d'un type signé et d'un type non signé produit des messages d'avertissement et des comportements parfois inattendus).
+Il faut donc utiliser la syntaxe avec ''decltype'' : ''decltype(v.size()) i = 0''. Mais cela ne simplifie pas beaucoup la lecture par rapport à l'écriture explicite du type.
+L'utilisation de ''std::size_t'' est un bon compromis entre lisibilité et rigueur.
+</note>
+===== Les boucles while et do-while =====
+Les deux dernières syntaxes itératives sont relativement simples à comprendre. Par rapport à la boucle //for//, seule la condition de continuation a une place definie dans ces syntaxes. L'initialisation et l'incrémentation sont placées librement dans le code (voire sont omis).
+<code>
+while (TEST_CONTINUATION) {
     ...
 }
@@ Ligne 187: / Ligne 467: @@
 do {
     ...
-} while (condition);
+} while (TEST_CONTINUATION);
 </code>
-Dans les 2 cas, exécute le bloc tant que la condition est vraie. Différence entre les 2 : avec do while, bloc exécuté au moins 1 fois avant de test la condition ; avec while, commence par tester
+La difference entre les boucles //while// et //do-while// est que dans la premiere, la condition de continuation est exécutée avant le corps de la boucle. Il est donc possible de sortir tout de suite de la boucle //while// sans entrer dans la boucle. Dans la seconde syntaxe, le corps de la boucle est exécutée avant le test de continuation. La boucle sera donc toujours exécutée au moins une fois.
+En pratique, les boucle //while// et //do-while// sont souvent equivalentes a la boucle //for//, si l'initialisation et l'incrémentation est explicite :
+<;code>
+INITIALISATION;
+while (TEST_CONTINUATION) {
+    ...
+    INCREMENTATION;
+}
+</code>
@@ Ligne 225: / Ligne 515: @@
 ^ 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