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:12] foxdry42 [Les tableaux] |
map [2019/04/04 21:55] (Version actuelle) foxdry42 [Les deque] |
||
|---|---|---|---|
| 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.1554318758.txt.gz · Dernière modification: 2019/04/03 21:12 par foxdry42
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported
