Différences

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

--- collection2 [2016/03/25 19:12]
gbdivers
+++ collection2 [2019/04/08 22:55] (Version actuelle)
foxdry42 [Suppression]
@@ Ligne 1: / Ligne 1: @@
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
+^ [[map|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[comparer|Chapitre suivant]] ^
 ====== Les fonctionnalités de base des collections ======
-Le chapitre précédent présentait chaque collection et ses spécificités, mais sans entrer dans les détails. Certaines fonctionnalités étant commune à plusieurs collections, ces fonctionnalités ne vont pas être décrites par collection, mais par catégories de fonctionnalités. N’hésitez pas à consulter la documentation pour savoir si une collection en particulier permet d'utiliser une fonctionnalité ou non.
+Le chapitre précédent présentait chaque collection et ses spécificités, mais sans entrer dans les détails. Certaines fonctionnalités étant communes à plusieurs collections, ces fonctionnalités ne vont pas être décrites par collection, mais par catégories de fonctionnalités. N’hésitez pas à consulter la documentation pour savoir si une collection en particulier permet d'utiliser une fonctionnalité ou non.
-Certaines fonctionnalités ont déjà étaient décrites dans les chapitres précédents, ce chapitre ne sera qu'un rappel dans ce cas.
+Certaines fonctionnalités ont déjà été décrites dans les chapitres précédents, ce chapitre ne sera qu'un rappel dans ce cas.
@@ Ligne 164: / Ligne 165: @@
 int main() {
-    const std::vector<int> v1 { 1, 2, 3 };
+    std::vector<int> v1 { 1, 2, 3 };
     std::vector<int> v2;  // déclaration
@@ Ligne 282: / Ligne 283: @@
 Si une collection est redimensionnée avec une taille plus petite, les éléments en fin de collection sont simplement supprimés. Pour supprimer tous les éléments, vous pouvez utiliser la fonction ''clear'' (nettoyer).
+<note>**empty ou isEmpty**
+Si vous dites a une personne qu'il existe deux fonctions dans les collections de la bibliothèque standard  ''empty'' et ''clear'', et que l'une d'elle permet de supprimer tous les éléments de la collection et l'autre permet de tester si la collection ne contient aucun element. Il est très probable que cette personne soit incapable de dire qui fait quoi entre ''empty'' et ''clear'' (les deux termes pouvant correspondre aussi bien a l'adjectif "vide" qu'au verbe "vider").
+Pour améliorer la lisibilité du code, il est classique que les guides de codage recommandent que les fonctions qui retourne un booléen commencent par un verbe, en général "is" (être quelque chose) ou "has" (avoir quelque chose).
+Plus généralement, les fonctions correspondent a des actions, quelque chose qui est fait. Il est classique de nommer les fonctions en utilisant un verbe, exprimant cette action.
+En suivant ces recommandations, ''empty'' devrait s'appeler ''is_empty'', qui se traduit alors par "est vide", et ''clear'' se traduit par "vider".
+La bibliothèque standard ne suis pas cette recommandation, certaines bibliothèques vont les suivre et d'autres bibliothèques vont proposer les deux versions des fonctions.
+</note>
 Ces quatre fonctions sont disponibles pour toutes les collections. En revanche, les fonctions suivantes sont uniquement disponibles pour ''std::vector'' et les chaînes de caractères (''std::string'' et équivalents).
@@ Ligne 400: / Ligne 414: @@
 </code>
-Le dernier point est plus complexe à comprendre, cela nécessite de comprendre la fonctionnement des ordinateurs, en particulier des caches mémoire. Sachez simplement qu'une mémoire contiguë comme dans ''std::vector'' sera généralement plus rapide qu'une mémoire non contiguë comme dans ''std::list''.
+Le dernier point est plus complexe à comprendre, cela nécessite de comprendre le fonctionnement des ordinateurs, en particulier des caches mémoire. Sachez simplement qu'une mémoire contiguë comme dans ''std::vector'' sera généralement plus rapide qu'une mémoire non contiguë comme dans ''std::list''.
@@ Ligne 417: / Ligne 431: @@
   * //back// (derrière) correspond à la fin d'une collection.
-Avec ces quatre mots-clés, vous avez donc les fonctions suivantes :
+Avec ces cinq mots-clés, vous avez donc les fonctions suivantes :
   * ''emplace_front'' pour créer au début ;
@@ Ligne 451: / Ligne 465: @@
     auto it = std::find(begin(v), end(v), 2);
     v.insert(it, { -1, -2, -3 });
-    for (auto i: v) std::cout << i << ' '; std::cout << std::endl;
+    for (auto i: v) std::cout << i << ' ';
+    std::cout << std::endl;
 }
 </code>
@@ Ligne 472: / Ligne 487: @@
 </code>
-La première version permet d'insérer un élément, la deuxième version permet d'insérer plusieurs fois la même valeur (faites bien attention à l'ordre des informations données : le nombre d'occurence puis la valeur), la troisième version permet d'insérer plusieurs éléments provenant d'une collection (paire d'itérateurs), la dernière version permet d'insérer une liste de valeurs.
+La première version permet d'insérer un élément, la deuxième version permet d'insérer plusieurs fois la même valeur (faites bien attention à l'ordre des informations données : le nombre d'occurrence puis la valeur), la troisième version permet d'insérer plusieurs éléments provenant d'une collection (paire d'itérateurs), la dernière version permet d'insérer une liste de valeurs.
 Lorsque vous insérez des éléments dans un ''std::vector'', les indirections sur les éléments peuvent être invalidés. Il n'est donc pas sûr d'insérer des éléments provenant d'un ''std::vector'' sur lui-même.
@@ Ligne 493: / Ligne 508: @@
 Pour ''emplace'', il existe également une version qui prend un itérateur de positionnement, mais la fonction change de nom. Il faut utiliser dans ce cas la fonction ''emplace_hint''.
-Les fonctions ''insert'', ''emplace'' et ''emplace_int'' suivent les prototypes suivants :
+Les fonctions ''insert'', ''emplace'' et ''emplace_hint'' suivent les prototypes suivants :
 <code>
@@ Ligne 515: / Ligne 530: @@
     std::set<int> s { 1, 2, 3, 4 };
     s.insert({ -1, -2, -3 });
-    for (const auto i: s) std::cout << i << ' '; std::cout << std::endl;
+    for (const auto i: s) std::cout << i << ' ';
+    std::cout << std::endl;
 }
 </code>
@@ Ligne 598: / Ligne 614: @@
     auto last  = std::find(begin(v), end(v), 7);
     v.erase(first, last);
-    for (auto i: v) std::cout << i << ' '; std::cout << std::endl;
+    for (auto i: v) std::cout << i << ' ';
+    std::cout << std::endl;
 }
 </code>
@@ Ligne 619: / Ligne 636: @@
 L'idiome "remove-erase" a un nom assez explicite : cela consiste a appliquer dans un premier temps l'algorithme ''std::remove'', puis la fonction membre ''erase''.
-Le code d'exemple suivant utilise cet idiome sur une collection de caracteres, qui contient des lettres et de chiffres, de facon a supprimer les chiffres.
+Le code d'exemple suivant utilise cet idiome sur une collection de caractères, qui contient des lettres et de chiffres, de façon à supprimer les chiffres.
 <code cpp>
@@ Ligne 631: / Ligne 648: @@
     auto it = std::remove_if(begin(v), end(v), isdigit);
     v.erase(it, end(v));
-    for (auto i: v) std::cout << i << ' '; std::cout << std::endl;
+    for (auto i: v) std::cout << i << ' ';
+    std::cout << std::endl;
 }
 </code>
@@ Ligne 641: / Ligne 659: @@
 </code>
-L'algorithme ''std::remove'' est un algorithme de la biliotheque standard (il faut donc inclure le fichier d'en-tete ''<algorithm>''). Il parcourt une collection et a chaque fois qu'il rencontre un element a supprimer, il le remplace par l'element valide suivant de la collection. A la fin, il retourne un iterateur sur le premier element invalide de la collection (la taille de la collection n'a pas ete modifiee).
+L'algorithme ''std::remove'' est un algorithme de la bibliothèque standard (il faut donc inclure le fichier d'en-tête ''<algorithm>''). Il parcourt une collection et à chaque fois qu'il rencontre un élément à supprimer, il le remplace par l’élément valide suivant de la collection. A la fin, il retourne un itérateur sur le premier élément invalide de la collection (la taille de la collection n'a pas été modifiée).
-Notez que "invalide" signfie que les elements present dans le collection sont encore accessible (les utiliser ne produit pas de comportement indetermine), mais peuvent correspondre a n'importe quel element. Le comportement est laisse a la discretion des developpeurs de la bibliotheque standard. Si vous avez la totalite de la collection du code precedent apres l'appel a ''std::remove'', vous pouvez obtenir par exemple le resultat suivant :
+Notez que "invalide" signifie que les éléments présent dans la collection sont encore accessible (les utiliser ne produit pas de comportement indéterminé), mais peuvent correspondre a n'importe quel élément. Le comportement est laisser a la discrétion des développeurs de la bibliothèque standard. Si vous avez la totalité de la collection du code précédent après l'appel a ''std::remove'', vous pouvez obtenir par exemple le résultat suivant :
 <code>
@@ Ligne 649: / Ligne 667: @@
 </code>
-Vous voyez dans cette version de l'algorithme que les elements valides sont places au debut de la collection (comme attendu), les elements invalides sont simplement laisses tel quel.
+Vous voyez dans cette version de l'algorithme que les éléments valides sont placer au début de la collection (comme attendu), les éléments invalides sont simplement laisser tel quel.
-La fonction membre ''erase'' est ensuite utilisee pour supprimer les elements invalides, qui sont les elements entre l'iterateur retourne par ''std::remove'' et la fin de la collection.
+La fonction membre ''erase'' est ensuite utilisée pour supprimer les éléments invalides, qui sont les éléments entre l'itérateur retourne par ''std::remove'' et la fin de la collection.
-En termes de performances par rapport a appeler plusieurs fois ''erase'', cet idiome garantie que la complexite est lineaire, ce qui signifie que chaque element n'est deplace qu'une seule fois. (Vous verrez la complexite algorithmique au chapitre sur la creation d'algorithmes).
+En termes de performances par rapport a appeler plusieurs fois ''erase'', cet idiome garantie que la complexité est linéaire, ce qui signifie que chaque élément n'est déplacé qu'une seule fois. (Vous verrez la complexité algorithmique au chapitre sur la création d'algorithmes).
-**Exercice** : dans code precedent, il y a au total trois deplacements d'elements avec l'idiome "remove-erase" (un pour chaque element 'a', 'b' et 'c'). Essayez de calculer le nombre de deplacements qu'il faudrait si vous n'utilisez que la fonction ''erase''.
+**Exercice** : dans le code précédent, il y a au total trois déplacements d’éléments avec l'idiome "remove-erase" (un pour chaque élément 'a', 'b' et 'c'). Essayez de calculer le nombre de déplacements qu'il faudrait si vous n'utilisez que la fonction ''erase''.
 <note>**Les idiomes de programmation**
-En programmation, un idiome est une ecriture que l'on retrouve habituellement dans un langage, pour realiser une tache particuliere. Ils sont parfois peu comprehensible au premier abord pour un debutant, mais ils sont consideres comme faisant partie du "vocabulaire" commun des developpeurs, qui faut savoir connaitre si on pretant vouloir maitriser un langage.
+En programmation, un idiome est une écriture qui se retrouve habituellement dans un langage, pour réaliser une tâche particulière. Ils sont parfois peu compréhensible au premier abord pour un débutant, mais ils sont considérés comme faisant partie du "vocabulaire" commun des développeurs, qui faut savoir connaitre si on prêtant vouloir maîtriser un langage.
-Notez bien que l'important n'est pas simplement de connaitre les idiomes, mais surtout de les etudier pour en comprendre les tenants et les aboutissants.
+Notez bien que l'important n'est pas simplement de connaitre les idiomes, mais surtout de les étudier pour en comprendre les tenants et les aboutissants.
 </note>
+===== Accéder aux éléments =====
+===== Premier et dernier éléments =====
+Pour accéder aux éléments d'une collection, la méthode privilégiée est le parcours séquentiel, avec ''std::begin'' et ''std::end'', qui fonctionne avec n'importe quel type de collection.
-===== Accéder aux éléments =====
+Certaines collections, comme ''std::vector'' et ''std::list'' proposent également des fonctions membres pour accéder directement au premier et au dernier élément, avec respectivement les fonctions ''front'' (//devant//) et ''back'' (//derrière//). Il faut bien sûr que la collection contienne au moins un élément, sinon cela provoque un comportement indéterminé.
+<code cpp main.cpp>
+#include <iostream>
+#include <vector>
+#include <cassert>
-Accès aux éléments (random access, front, back)
+int main() {
+    std::vector<int> const v { 1, 2, 3, 4 };
+    assert(!v.empty());
+    std::cout << v.front() << std::endl;
+    std::cout << v.back() << std::endl;
+}
+</code>
-===== Les autres fonctions membres =====
+affiche :
-Autres fonctions membre (find, count, etc)
+<code>
+
+
+</code>
+Notez que l'utilisation d'une assertion pour vérifier que le tableau n'est pas vide est inutile dans ce code, puisqu'il est déclaré juste au dessus, il serait difficile de faire une erreur. Mais c'est une bonne habitude à prendre de toujours faire les vérifications.
-Itérateurs
+===== Accès aléatoire =====
-allocator, data()
+Quelques types de collections, comme ''std::vector'' et ''std::array'' autorisent d'accéder directement à un élément quelconque, en utilisant les crochets droits ''[POSITION]''. Le terme "aléatoire" signifie "n'importe quel élément" et pas "un élément au hasard". Les éléments sont identifiés par leur position dans la collection, en commençant avec l'indice 0.
+Le type de l'indice est formellement donné selon le type de collection, en utilisant ''size_type'' sur la collection. Par exemple pour ''std::vector'' :
+<code cpp>
+using type = std::vector<int>::size_type;
+</code>
+Ce type est un type entier non signé, qui correspond le plus souvent à ''std::size_t'' (qui représente une taille en général).
+<code cpp main.cpp>
+#include <iostream>
+#include <vector>
+#include <cassert>
+int main() {
+    const std::vector<int> v { 1, 2, 3, 4 };
+    const std::size_t index { 1 };
+    assert(index < v.size());
+    std::cout << v[index] << std::endl;
+}
+</code>
+affiche :
+<code>
+</code>
+Dans ce code, l'élément correspondant à ''v[1]'' n'est pas le premier élément de la collection, mais l'élément correspondant à l'indice "1", c'est à dire la valeur "2" (l'indice 0 correspondant au premier élément, c'est à dire la valeur "1").
+(Le code d'exemple utilise volontairement des valeurs dans la collection proches des indices, pour insister sur le fait que vous ne devez pas penser en termes de "premier élément", "deuxième élément", etc. mais de "élément à la position 0", "élément à la position 1", etc.)
+Comme toujours, l'accès en dehors du tableau provoque un comportement indéfini, il est donc nécessaire de tester la valeur de l'index avant d'accéder aux valeurs. L'écriture "index strictement inférieur à la taille" est une écriture idiomatique, il est préférable de l'utiliser.
+Note : pour les collections n'autorisant pas un accès aléatoire, il est possible d'accéder à un élément en particulier, mais il faudra utiliser l'algorithme ''std::advance'' (qui parcourt une collection, en pratique).
+<code cpp main.cpp>
+#include <iostream>
+#include <list>
+#include <cassert>
+int main() {
+    std::list<int> const l { 1, 2, 3, 4 };
+    const std::size_t index { 1 };
+    assert(index < l.size());
+    auto it = begin(l);
+    std::advance(it, index);
+    std::cout << (*it) << std::endl;
+}
+</code>
+affiche :
+<code>
+</code>
+<note>Il existe également la fonction membre ''at'', qui est similaire à l'opérateur d'indexation ''[]'', mais son usage n'est pas recommandé.</note>
+===== Collections associative =====
+Dans le cas des collections associatives, la notion de position n'a pas réellement de sens, puisque la collection est libre de réorganiser les éléments. Il est cependant possible d'accéder séquentiellement aux éléments, en utilisant l'algorithme ''std::advance'', comme indiqué ci-dessus.
+L'opérateur d'indexation ''[]'' n'est donc pas utilisable avec un indice dans la collection, mais avec une clé.
+<code>
+collection[clé]
+</code>
+Cet opérateur d'indexation ''[]'' est utilisable aussi bien pour lire une valeur que pour la créer et la modifier. Si la clé n'existe pas, l'opérateur d'indexation ''[]'' va créer un élément correspondant à cette clé.
+<code cpp main.cpp>
+#include <iostream>
+#include <map>
+int main() {
+    std::map<int, char> m;
+    std::cout << m.size() << std::endl;
+    m[123] = 'a';
+    std::cout << m.size() << std::endl;
+    std::cout << m[123] << std::endl;
+}
+</code>
+affiche :
+<code>
+a
+</code>
+La taille de la collection est bien augmenté de un après l'utilisation de l'opérateur d'indexation ''[]''.
+Cela implique que l'accès en utilisant l'opérateur d'indexation ''[]'' sur une collection associative est toujours valide, puisque cela va créer un élément si la clé n'existe pas. Vous pouvez quand même utiliser une assertion, dans le cas où vous souhaitez garantir qu'un élément ne sera pas ajouté dans la collection.
+<code cpp>
+assert(m.find(key) == end(m));
+m[key] = value;
+</code>
+<note>Il existe également une fonction membre ''at'', qui est similaire à l'opérateur d'indexation ''[]'', mais son usage n'est pas recommandé.</note>
+^ [[map|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[comparer|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