Différences

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

--- collection2 [2016/03/14 15:56]
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 407: / Ligne 421: @@
 Pour l'ajout et la suppression d’éléments, il est nécessaire de faire la distinction entre les collections séquentielles (''std::vector'', ''std::list'', etc.) et les collections associatives (''std::map'', ''std::set'', etc.). En effet, dans le premier cas, les éléments ne sont pas ordonnés automatiquement par la collection, il est donc possible d'ajouter des éléments au début, à la fin ou n'importe où dans la collection. Dans le second cas, les éléments sont organisés automatiquement, vous ne pouvez pas choisir de placer un élément à un emplacement particulier de la collection.
-==== Ajouter ou supprimer un élément ====
+==== Utiliser les collections comme des piles ====
 Vous avez déjà utilisé les fonctions de base pour ajouter et supprimer des éléments dans une collection séquentielle. Les mots-clés sont les suivants :
@@ 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 613: / Ligne 630: @@
 === L'idiome remove-erase ===
-Vous avez vu qu'insérer un élément dans ''std::vector'' impliquait que les éléments à droite de l'élément inséré devait être déplacés, pour laisser la place au nouvel élément. Pour la suppression, le problème est similaire : supprimer un élément dans un ''std::vector'' implique de déplacer tous les éléments à sa droite, pour combler l'emplacement qui a été libéré.
+Vous avez vu qu'insérer un élément dans ''std::vector'' impliquait que les éléments à la suite de l'élément inséré devait être déplacés, pour laisser la place au nouvel élément. Pour la suppression, le problème est similaire : supprimer un élément dans un ''std::vector'' implique de déplacer tous les éléments à sa droite, pour combler l'emplacement qui a été libéré.
 Lorsque vous souhaitez supprimer plusieurs éléments dans un ''std::vector'', cela nécessitera alors de décaler plusieurs fois les éléments en fin de collection, ce qui peut être coûteux en termes de performances.
+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''.
-<note>Les idioms de programmation
+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.
-définition de idiom
+<code cpp>
-</note>
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <cctype>
-https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom
+int main() {
+    std::vector<char> v { 'a', '1', 'b', '2', 'c', '3' };
+    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;
+}
+</code>
+affiche :
+<code>
+a b c
+</code>
+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" 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>
+a b c 2 c 3
+</code>
+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 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 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 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 é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 étudier pour en comprendre les tenants et les aboutissants.
+</note>
 ===== Accéder aux éléments =====
+===== Premier et dernier éléments =====
-Accès aux éléments (random access, front, back)
+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.
-===== Les autres fonctions membres =====
+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é.
-Autres fonctions membre (find, count, etc)
+<code cpp main.cpp>
+#include <iostream>
+#include <vector>
+#include <cassert>
+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>
-Itérateurs
+affiche :
-allocator, data()
+<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.
+===== Accès aléatoire =====
+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