Différences

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

--- map [2016/02/10 08:47]
gbdivers
+++ map [2019/04/04 21:55] (Version actuelle)
foxdry42 [Les deque]
@@ Ligne 1: / Ligne 1: @@
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
+^ [[collection|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[collection2|Chapitre suivant]] ^
 ====== Les catégories de collections ======
-La bibliothèque standard propose de nombreux conteneurs de données. Pour le moment, vous avez vu principalement ''std::vector'' et ''std::string''. Ce chapitre présente les autres collections de la bibliothèque standard et leurs fonctionnalités de base.
+La bibliothèque standard propose de nombreux conteneurs de données. Pour le moment, vous avez vu principalement ''std::vector'' et ''std::string''. Ce chapitre présente les autres collections de la bibliothèque standard, en particulier les listes doublement chaînées ''std::list'' et les conteneurs associatifs ''std::map'' et ''std::set''.
-Note : la manipulation plus poussées des collections avec ''begin'' et ''end'' passe par l'utilisation des itérateurs. Ce concept est suffisamment important pour faire l'objet d'un chapitre dédié. Ce chapitre se focalise uniquement sur les fonctionnalités spécifiques des conteneurs.
+Les collections se distinguent par leur gestion interne des données et par les fonctionnalités qu'elles proposent. Cependant, il est habituel que plusieurs collections proposent les mêmes fonctionnalités.
+Par exemple, plusieurs collections permettent d'ajouter un élément à la fin d'une collection avec la fonction ''push_back'' ("pousser à la fin"), comme ''std::vector'', ''std::list'', ou ''std::deque''. Ces différentes collections ne gèrent pas les données de la même façon en interne, ce qui a un impact sur les performances. La complexité algorithmique de chaque fonction est indiquée dans la documentation.
+(Si vous ne connaissez pas ce qu'est la complexité algorithmique, ce concept sera détaillé dans les chapitres sur la création d'algorithmes).
+Note : la manipulation plus poussée des collections avec ''begin'' et ''end'' passe par l'utilisation des itérateurs. Ce concept est suffisamment important pour faire l'objet d'un chapitre dédié. Ce chapitre se focalise uniquement sur les fonctionnalités spécifiques des conteneurs.
@@ Ligne 15: / Ligne 21: @@
 En pratique, les conteneurs de la bibliothèque standard du C++ sont aussi des collections, vous verrez souvent dans ce cours les termes "collection" et "conteneur" utilisés indifféremment. (Lorsque vous créerez vos propres conteneurs, il est recommandé de les implémenter également sous forme de collections, pour être compatibles avec les algorithmes de la bibliothèque standard).
-Mais n'oubliez pas que ce sont des concepts distincts (par exemple, les vues //views// proposent les fonctionnalités des collection, mais ne contiennent les données qu'elles manipulent. Et les [[https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes|graphes]] peuvent être des conteneurs de données, mais ne proposent généralement pas les concepts de "premier élément", "dernier élément" et "élément suivant").
+Mais n'oubliez pas que ce sont des concepts distincts (par exemple, les vues //views// proposent les fonctionnalités des collections, mais ne contiennent les données qu'elles manipulent. Et les [[https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes|graphes]] peuvent être des conteneurs de données, mais ne proposent généralement pas les concepts de "premier élément", "dernier élément" et "élément suivant").
 </note>
-===== Les différents types de conteneurs =====
-==== Conteneurs séquentiels et associatifs ====
+===== Conteneurs séquentiels et associatifs =====
 La première grande classification des collections est la séparation entre conteneurs séquentiels et associatifs. Un conteneur associatif associe une clé à des informations (un objet). A partir de cette clé, il est alors facile de retrouver les informations associées. C'est une notion que vous pouvez retrouver dans la vie de tous les jours : par exemple, pour trouver une définition (l'information) d'un mot (la clé) dans un dictionnaire (la collection de données), ou lorsque vous allez à la banque consulter vos dépenses du mois (les informations) en utilisant votre numéro de compte (la clé).
@@ Ligne 30: / Ligne 35: @@
 Notez bien que les conteneurs associatifs sont aussi des collections et peuvent donc être manipulés comme des conteneurs séquentiels. Cependant, n'oubliez pas qu'ils gèrent automatiquement en interne les données, cela n'a pas de sens par exemple de trier les éléments avec ''std::sort''.
-Pour bien comprendre ce principe de "gestion automatiquement interne" des données par une conteneur associatif, le code suivant utilise une conteneur non-associatif (''std::vector'') et un conteneur associatif (''std::map'') et affiche les éléments séquentiellement (avec une boucle ''for'' que vous verrez dans la site de ce cours).
+Pour bien comprendre ce principe de "gestion automatiquement interne" des données par un conteneur associatif, le code suivant utilise une conteneur non-associatif (''std::vector'') et un conteneur associatif (''std::map'') et affiche les éléments séquentiellement (avec une boucle ''for'' que vous verrez dans la suite de ce cours).
 <code cpp main.cpp>
@@ Ligne 39: / Ligne 44: @@
 int main() {
     using data_t = std::pair<int, std::string>;
-    std::vector<data_t> v {
+    const std::vector<data_t> v {
         { 2, "hello" },
         { 3, "every" },
         { 1, "body" }
     };
-    for (auto & p: v)
+    for (auto p: v)
         std::cout << p.first << ' ' << p.second << std::endl;
     std::cout << std::endl;
-    std::map<int, std::string> m {
+    const std::map<int, std::string> m {
         { 2, "hello" },
         { 3, "every" },
         { 1, "body" }
     };
-    for (auto & p: m)
+    for (auto p: m)
         std::cout << p.first << ' ' << p.second << std::endl;
 }
@@ Ligne 73: / Ligne 78: @@
 Dans le conteneur non-associatif (''std::vector''), les éléments sont affichés dans le même ordre qu'ils ont été entrés dans la collection. Dans le conteneur associatif (''std::map''), les éléments ont été trié en fonction de la clé (la valeur entière).
-Vous pouvez voir dans le code précédent qu'il est possible de manipuler les mêmes informations, quelque soit le type de conteneur. Il est tout à fait possible de trier un tableau ''std::vector'' en fonction de la valeur entière avec ''std::sort'' et de faire une recherche sur cette valeur avec ''std::find''. La différence est que dans la cas des conteneurs associatifs, l'une des informations a un rôle particulier pour le stockage et l'accès.
+Vous pouvez voir dans le code précédent qu'il est possible de manipuler les mêmes informations, quelque soit le type de conteneur. Il est tout à fait possible de trier un tableau ''std::vector'' en fonction de la valeur entière avec ''std::sort'' et de faire une recherche sur cette valeur avec ''std::find''. La différence est que dans le cas des conteneurs associatifs, l'une des informations a un rôle particulier pour le stockage et l'accès.
 Choisir la structure de données la plus adaptée à une problématique fait partie des bases de la programmation.
+===== Les conteneurs séquentiels =====
 ==== Les tableaux ====
@@ Ligne 99: / Ligne 106: @@
 </note>
-La particularité des tableaux est d'avoir ses éléments contiguës en mémoire, dans un bloc mémoire réservé pour ce tableau. Cela permet d'avoir un accès efficace direct à n'importe quel élément, selon son indice dans le tableau, avec l'opérateur ''[]''. (Il est également possible d’utiliser la fonction ''at'', mais son utilisation est déconseillée). Les indices commencent à partir de zéro jusque ''size()-1''.
+La particularité des tableaux est d'avoir ses éléments contiguës en mémoire, dans un bloc mémoire réservé pour ce tableau. Cela permet d'avoir un accès efficace direct à n'importe quel élément, selon son indice dans le tableau, avec l'opérateur d'indexation ''[]''. (Il est également possible d’utiliser la fonction ''at'', mais son utilisation est déconseillée). Les indices commencent à partir de zéro jusque ''size()-1''.
 <code cpp>
-const vector<char> v { 'a', 'z', 'e', 'r', 't', 'y' };
+const std::vector<char> v { 'a', 'z', 'e', 'r', 't', 'y' };
 std:cout << v[0] << std::endl;
 </code>
@@ Ligne 118: / Ligne 125: @@
 </code>
-(Le code ''i < v.size()'' est strictement équivalent à ''i <= v.size()-1'' pour les entiers, mais n'utilise qu'une seule opération de comparaison, alors que la seconde syntaxe utilise un comparaison et une soustraction, ce qui est moins performant).
+(Le code ''i < v.size()'' est strictement équivalent à ''i <= v.size()-1'' pour les entiers, mais n'utilise qu'une seule opération de comparaison, alors que la seconde syntaxe utilise une comparaison et une soustraction, ce qui est moins performant).
 ==== Gestion de la mémoire des tableaux ====
@@ Ligne 140: / Ligne 147: @@
   * ''size()'' permet de connaître le nombre total d'élément actuellement utilisés dans le tableau.
-  * ''capactity()'' permet de connaître le nombre totale d'élément dans le tableau (utilisés et réserve).
+  * ''capacity()'' permet de connaître le nombre totale d'élément dans le tableau (utilisés et réserve).
   * ''max_size()'' permet de connaître le nombre maximal d'élément qu'il sera possible d'avoir dans un tableau.
   * ''empty()'' permet de savoir si un tableau ne contient pas d'élément utilisé (autrement dit, si ''size()'' vaut zéro).
@@ Ligne 186: / Ligne 193: @@
 En termes de mémoire, les listes consomment un peu plus que les tableaux, du fait de la présence des indirections pour chaque élément. Si une collection contient N éléments, alors une liste simplement chaînée aura un surcoût mémoire de N x sizeof(indirection), et une liste doublement chaînée aura un surcoût de 2N x sizeof(indirection). A cela, il faut également ajouter une perte de performances, à cause des caches mémoires (la mémoire n'étant pas contiguë, l'utilisation des listes sont moins performantes que les tableaux).
+==== Les deques ====
+Le dernier type de collection proposé par la bibliothèque standard est ''std::deque''. Cette collection permet l'insertion et la suppression d'éléments au début et à la fin. En termes de fonctionnalités, cette collection est similaire à ''std::list'', mais les accès sont plus performants. (Voir l'article sur [[https://en.wikipedia.org/wiki/Double-ended_queue|Wikipédia]] pour les détails sur l'implémentation).
+<code cpp>
+const std::deque<char> q { 'a', 'z', 'e', 'r', 't', 'y' };
+</code>
+===== Les conteneurs associatifs =====
 ==== Les maps ====
@@ Ligne 193: / Ligne 210: @@
 Il existe deux types de //maps// :
-  * ''std::map'' dont toutes les clés sont distinctes (insérer un élément avec une clé existante supprime l'élément précédent) ;
+  * ''std::map'' dont toutes les clés sont distinctes (l'insertion d'un élément avec une clé existante échouera) ;
   * ''std::multimap'', qui peut contenir plusieurs éléments utilisant la même clé.
@@ Ligne 238: / Ligne 255: @@
 ==== Les maps non ordonnées ====
-Dans les //maps// non ordonnées, les clés ne sont pas utilisées directement pour organiser les éléments, mais via une [[https://fr.wikipedia.org/wiki/Fonction_de_hachage|fonction de hachage]]. Une telle fonction prend en argument un valeur et génère une clé à partir de cela. Cette clé est généralement plus simple à manipuler que la valeur d'origine et donc plus performante.
+Dans les //maps// non ordonnées, les clés ne sont pas utilisées directement pour organiser les éléments, mais via une [[https://fr.wikipedia.org/wiki/Fonction_de_hachage|fonction de hachage]]. Une telle fonction prend en argument une valeur et génère une clé à partir de cela. Cette clé est généralement plus simple à manipuler que la valeur d'origine et donc plus performante.
 <code cpp main.cpp>
@@ Ligne 259: / Ligne 276: @@
 </code>
-Cet type de collection est en particulier intéressant lorsque la clé est une chaîne de caractères. Une chaîne prend du temps a être copiée et être comparée à une autre chaîne, alors qu'une simple valeur numérique est très rapide.
+Ce type de collection est en particulier intéressant lorsque la clé est une chaîne de caractères. Une chaîne prend du temps a être copiée et être comparée à une autre chaîne, alors qu'une simple valeur numérique est très rapide.
 Comme pour les //maps//, il existe deux versions des //maps// non ordonnées : avec clé unique ou non.
@@ Ligne 341: / Ligne 358: @@
-==== Les queues ====
+===== Les adaptateurs de collections =====
-std::deque
+Les adaptateurs de collections ne sont pas des collections à proprement parlé, mais utilisent une collection en interne et lui ajoutent de nouvelles fonctionnalités. Par exemple, ''std::stack'' propose le concept de [[https://fr.wikipedia.org/wiki/Last_in,_first_out|pile]] (LIFO, //Last In, First Out//, "dernier arrivé, premier sorti") et utilise par défaut en interne un ''std::deque''.
+==== std::stack ====
-==== Les adaptateurs de collections ====
+Le concept de pile est très simple à comprendre, puisque c'est quelque chose que vous avez appris lorsque vous étiez bébé : lorsque vous empiliez des petits cubes (ou n'importe quel autre type d'objets), vous créez une pile. Vous ne pouvez ajouter un élément que sur le dessus de la pile et vous ne pouvez retirer que l'élément qui se trouve sur le dessus (tous les bébés ont expérimentés que retirer un autre élément que celui qui se trouve au dessus détruit la pile... ce qu'ils apprécient généralement beaucoup).
-stack
+{{ :stack.png |}}
-queue
-priority_queue
+  * ''push'' permet d'ajouter un élément ;
+  * ''emplace'' permet de créer un élément directement sur le dessus de la pile ;
+  * ''pop'' permet de retirer un élément ;
+  * ''top'' permet d'accéder à l'élément sur le dessus de la pile ;
+  * ''empty'' permet de savoir si une pile est vide ;
+  * ''size'' permet de connaître le nombre d'éléments.
+Les fonctions ''push'' et ''emplace'' sont similaires, elles permettent d'ajouter un élément sur la pile. La première prend un objet existant et le place sur la pile. Le second créé directement un objet sur la pile. La différence sera importante pour les objets complexes (ceux qui prennent du temps à être créer, ceux qui ne peuvent pas être copié). Cela sera plus clair pour vous lorsque vous verrez la création d'objets (programmation orientée objet).
-===== Créer une collection =====
+<code cpp main.cpp>
+#include <stack>
+#include <iostream>
+int main() {
+    std::stack<char> s;
+    s.push('a');
+    s.emplace('b');
+    s.push('c');
+    s.pop();
+    std::cout << s.top() << std::endl;
+    std::cout << s.size() << std::endl;
+}
+</code>
-Construction (par défaut, par copie, reserve/resize). Size, capacité, empty, shrink_to_fit. swap
+affiche :
+<code>
+b
+</code>
-===== Ajouter et supprimer des éléments =====
+(Dans ce code, ''push'' et ''emplace'' donnent le même résultat, puisque un entier est une objet simple en mémoire).
-Ajout et suppression d'éléments. L'idiome remove-erase. emplace vs push/insert
+Notez que les fonctions ''top'' et ''pop'' nécessitent que la pile contient au moins un élément, sinon cela produit un comportement indéfini (//undefined behavior//). Il est donc nécessaire de vérifier que la pile ne soit pas vide.
-Complexité algo
+<code cpp>
+assert(!s.empty());
+s.top();
+s.pop();
+</code>
-===== Accéder aux éléments =====
+==== std::queue ====
-Accès aux éléments (random access, front, back)
+''std::queue'' est un second type classique de structure de données : les [[https://fr.wikipedia.org/wiki/File_(structure_de_donn%C3%A9es)|files]] (FIFO, //First In, First Out//, "premier arrivé, premier sorti"). Vous pouvez vous représenter cette structure de données comme un tuyau, dans lequel vous poussez les éléments d'un côté et les récupérez de l'autre côté.
-===== Les autres fonctions membres =====
+{{ :queue.png |}}
-Autres fonctions membre (find, count, etc)
+  * ''push'' permet d'ajouter un élément ;
+  * ''emplace'' permet de créer un élément directement à l'entrée de la file ;
+  * ''pop'' permet de retirer un élément ;
+  * ''front'' permet d'accéder à l'élément à l'entrée de la file ;
+  * ''back'' permet d'accéder à l'élément à la sortie de la file ;
+  * ''empty'' permet de savoir si une file est vide ;
+  * ''size'' permet de connaître le nombre d'éléments.
+<code cpp main.cpp>
+#include <queue>
+#include <iostream>
+int main() {
+    std::queue<char> q;
+    q.push('a');
+    q.emplace('b');
+    q.push('c');
+    q.pop();
+    std::cout << q.front() << std::endl;
+    std::cout << q.back() << std::endl;
+    std::cout << q.size() << std::endl;
+}
+</code>
+affiche :
+<code>
+b
+c
+</code>
+Il faut également tester si la file est vide avant d'utiliser les fonctions ''front'', ''back'' et ''pop''.
+<code cpp>
+assert(!q.empty());
+q.front();
+q.back();
+q.pop();
+</code>
+==== std::priority_queue ====
+Le dernier type d'adaptateur est similaire à ''std::queue'', sauf que les éléments sont triés. De fait, lorsque vous retirer un élément de la queue, c'est celui qui a la plus grande valeur qui sort en premier.
+<code cpp main.cpp>
+#include <queue>
+#include <iostream>
+int main() {
+    std::priority_queue<char> pq;
+    pq.push('z');
+    pq.emplace('b');
+    pq.push('c');
+    pq.pop();
+    std::cout << pq.top() << std::endl;
+    std::cout << pq.size() << std::endl;
+}
+</code>
+affiche :
+<code>
+c
+</code>
+Pour comprendre pourquoi ce code affiche "c", il faut regarder ce que contient la queue à chaque étape. Après les trois ajouts d'éléments, la queue contient les éléments dans l'ordre : z, c, b (du plus grand au plus petit). Après le ''pop'', l'élément "z" est supprimé et l'élément avec la plus haute priorité dans la queue est "c".
+Comme pour ''std::queue'', il faut que la queue contienne au moins un élément pour pouvoir utiliser ''top'' et ''pop'.
+<code cpp>
+assert(!pq.empty());
+pq.top();
+pq.pop();
+</code>
-Itérateurs
-allocator, data()
+^ [[collection|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[collection2|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