Outils d'utilisateurs
map
Différences
Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
|
map [2019/04/03 21:02] foxdry42 |
map [2019/04/04 21:55] (Version actuelle) foxdry42 [Les deque] |
||
|---|---|---|---|
| Ligne 78: | 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). | 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. | Choisir la structure de données la plus adaptée à une problématique fait partie des bases de la programmation. | ||
| Ligne 125: | Ligne 125: | ||
| </code> | </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 ==== | ==== Gestion de la mémoire des tableaux ==== | ||
| Ligne 193: | 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). | 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 queues ==== | + | ==== 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). | 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). | ||
| Ligne 255: | Ligne 255: | ||
| ==== Les maps non ordonnées ==== | ==== 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> | <code cpp main.cpp> | ||
map.1554318131.txt.gz · Dernière modification: 2019/04/03 21:02 par foxdry42
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported
