Différences

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

--- boucles [2015/06/30 17:12]
gbdivers
+++ boucles [2016/12/02 00:46] (Version actuelle)
gbdivers
@@ Ligne 2: / Ligne 2: @@
 ^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
-====== Les boucles ======
+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.
-seconde partie des structures de contrôle : les boucles. Permet de répéter un bloc d'instruction.
+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.
-Similarité avec algos (transform, foreach, etc) dans le sens ou cela permet de parcourir un tableau
+En programmation, une boucle est similaire : répéter une tâche (une séquence d'instructions) jusqu'à atteindre le but recherché.
-===== while et do while =====
+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.
-Permet de répéter un bloc d'instructions tant qu'une condition est vérifiée. Syntaxe :
-<code>
+====== Les instructions iteratives ======
-while (condition) {
+Classiquement, une boucle peut etre decomposer en trois parties :
+  * 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 :
+  * 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.
+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.
+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(TYPE ELEMENT: COLLECTION) {
     ...
 }
+</code>
-do {
+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>
+#include <iostream>
+#include <vector>
+int main() {
+    std::vector<int> v { 1, 2, 3 };
+    for(int i: v) {
+        std::cout << i << std::endl;
+    }
+}
+</code>
+affiche :
+<code>
+
+
+
+</code>
+==== 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() {
+    std::vector<int> v { 1, 2, 3 };
+    for(auto i: v) {
+        std::cout << i << std::endl;
+    }
+}
+</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;
+    }
+}
+</code>
+affiche :
+<code>
+h
+e
+l
+l
+o
+</code>
+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>
+int main() {
+    for(auto i: { 1, 2, 3, 4 }) {
+        std::cout << i << std::endl;
+    }
+}
+</code>
+affiche :
+<code>
+
+
+
+
+</code>
+<note>**Les vues [C++17]**
+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() {
+    std::vector<int> v;
+    std::vector<double> w;
+    std::sort(std::begin(v), std::end(w));
+}
+</code>
+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::vector<int> v;
+std::vector<int> w;
+std::sort(std::begin(v), std::end(w));  // (#1)
+std::sort(std::end(v), std::begin(v));  // (#2)
+</code>
+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>
+#include <iostream>
+#include <array>
+#include <numeric>
+#include <iterator>
+int main() {
+    std::array<char, 26> alphabet;
+    std::iota(std::begin(alphabet), std::end(alphabet), 'a');
+    std::copy(std::begin(alphabet), std::end(alphabet),
+              std::ostream_iterator<char>(std::cout, " "));
+}
+</code>
+affiche :
+<code>
+a b c d e f g h i j k l m n o p q r s t u v w x y z
+</code>
+===== La boucle for =====
+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.
+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 :
+<code>
+for (INITIALISATION; TEST_CONTINUATION; INCREMENTATION) {
     ...
-} while (condition);
+}
 </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
+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).
-===== for =====
+Par exemple, pour compter de 1 à 10, il faut :
-éléments, tous optionnels :
+  * 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.
-  * initialisation
+Chacune de ces composants sont facilement traduit en C++ :
-  * test de continuation
-  * incrémentation
-syntaxe :
+  * initialisation : ''int i { 1 }'' ;
+  * incrementation : ''++i'' ;
+  * condition d'arret : ''i <= 10''.
+En utilisant ces syntaxes dans un boucle //for//, vous obtenez donc :
 <code>
-for (initialisation; test de continuation; boucle) {
+#include <iostream>
+int main() {
+    for (int i { 1 }; i <;= 10; ++i) {
+        std::cout << i << std::endl;
+    }
 }
 </code>
-Par exemple, pour compter de 1 à 10, on utilise un compteur (variable entière) :
+affiche :
-  * initialisation à 1
+<code>
-  * s'arrête lorsque == à 10
-  * incrémente à chaque boucle
+
+
+
+
+
+
+
+
+</code>
+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>
+std::vector<int> v;
+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>
-devient :
+affiche :
 <code>
-for (int i { 1 }; i <= 10; ++i) {
-    std::cout << i << std::endl;
+
+
+</code>
+Notez que la boucle //range-for// fait exactement la même chose en interne.
+==== 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>
+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>
-**Exercice** :
+affiche :
+<code>
+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) {
+    ...
+}
+do {
+    ...
+} while (TEST_CONTINUATION);
+</code>
+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>
+===== Programmation structurée =====
+Toutes les syntaxes du C++ ne sont pas présentées dans ce cours. En particulier, concernant le contrôle des flux de donnees, une instruction n'est volontairement non presentee : l'instruction ''goto''. Cette instruction permet de passer d'un endroit quelconque d'un programme à un autre endroit quelconque.
+L'utilisation de cette instruction pose un gros problème de lecture du code, il devient rapidement difficile de suivre le flux d'instruction ("code spaghetti").
+Au contraire, n'utiliser que les structures de contrôles permet d'améliorer la lisibilité du code et facilite donc la conception et la maintenance des programmes (en C++ ! L'utilisation de ''goto'' ou d'un équivalent peut être une pratique acceptable dans d'autres langages de programmation, par exemple en C).
+Ce paradigme s'appelle la programmation structurée. Concretement, cela signifie que le code se limite :
+  * aux séquences d'instructions (une série d'instructions, qui s'exécutent les unes après les autres) ;
+  * aux instructions conditionnelles (qui permet de choisir entre deux flux d'instructions) ;
+  * aux instructions itératives (qui permettent de répéter des séquences d'instructions).
+<note>**Paradigmes**
+La programmation structurée est un sous-ensemble de la programmation impérative. Pour rappel des paradigmes que vous avez déjà rencontrés :
+  * la programmation impératives, qui décrit un programme comme un ensemble d'instructions ;
+  * la programmation procédurale, qui utilise des fonctions (procedure).
+</note>
+Un point intéressant avec la programmation structurée est qu'elle se prete tres bien aux représentation graphiques. Cela permet de représenter un algorithme sous forme visuelle, ce qui facilite la compréhension. Il existe plusieurs représentations graphiques dédiées aux langages de programmation, par exemple les organigrammes (//flowchat// en anglais, en vert dans la figure suivante) et les structogrammes (//Nassi–Shneiderman diagram// en anglais, en violet dans la figure suivante).
-. Ecrire le code permettant de réaliser le test présenté a la fin du chapitre [[virgule_fixe|]]. Pour dessiner le graphique, vous pouvez simplement afficher la valeur du compteur dans la console avec ''std::cout'', puis copier le contenu dans un tableur (par exemple LibreOffice Calc).
+{{ https://upload.wikimedia.org/wikipedia/commons/e/ec/Structured_program_patterns.png |}}
-. L'exercice précédent présente un problème : afficher toutes les valeurs prend du temps a afficher et a manipuler dans le tableur. De plus, ce n'est pas nécessaire d'afficher toutes les valeurs, il n'est pas possible de toutes les représenter dans un même graphique.
+(Image provenant de l'article de Wikipedia sur la programmation structurée).
-Utiliser un test ''if'' et l’opérateur modulo ''%'' pour afficher une valeur pour 100 valeurs du compteur.
+Pour aller plus loin, vous pouvez consulter l'article de Wikipedia sur la [[https://en.wikipedia.org/wiki/Structured_programming|programmation structurée]].
-. Idem, mais en utilisant deux boucles ''for'' au lieu de ''if''.
 ^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
-{{tag> Cours C++}}

C++, Qt, OpenGL, CUDA

Outils d'utilisateurs

Outils du Site

Différences

Outils de la Page