Quelle est la différence entre les deux? Je veux dire que les méthodes sont toutes les mêmes. Donc, pour un utilisateur, ils travaillent de manière identique.
Est-ce exact??
Réponses
Trop de publicités?
aJ.
Points
17014
Permettez-moi de liste vers le bas les différences:
- Deque gère ses éléments avec un tableau dynamique, offre aléatoire d'accès, et a presque la même interface comme un vecteur.
- Liste gère ses éléments liste doublement chaînée et ne pas fournir un accès aléatoire.
- Deque Rapide des insertions et des délétions à la fois la fin et le début. Insertion et suppression d'éléments dans le milieu est relativement lente car tous les éléments jusqu'à l'une des deux les extrémités peuvent être déplacés pour faire de la place ou à combler une lacune
- Dans la Liste, l'insertion et la suppression d'éléments est rapide à chaque position, et pas seulement à l'une ou aux deux extrémités .
- Deque : Toute insertion ou la suppression d'éléments d'autres qu'au début ou à la fin annule tous les pointeurs, références, et itérateurs qui font référence à des éléments de la deque.
- Liste: Insertion et suppression d'éléments ne pas pour effet d'invalider les pointeurs, références, et itérateurs à d'autres éléments
La complexité
Insert/eraser at the beginning in middle at the end
Deque: .............. Amorti constant.......................................... Linéaire.................... Amorti constant Liste: ....................Constant...........................................................Constant.................Constant
À partir de l' (daté mais toujours très utile) SGI STL résumé de l' deque:
Une deque est très bien comme un vecteur: comme le vecteur, c'est une séquence qui prend en charge l'accès aléatoire à des éléments, de la constante de temps de l'insertion et de suppression d'éléments à la fin de la séquence, et le temps linéaire de l'insertion et de suppression d'éléments dans le milieu.
La principale façon dont deque diffère de vecteur est que deque prend également en charge la constante de temps de l'insertion et de suppression d'éléments au début de la séquence. En outre, deque n'a pas toutes les fonctions de membre analogue à vecteur de la capacité() et de la réserve(), et n'offre pas de garanties sur l'itérateur de validité qui sont associés à ces fonctions de membre.
Voici le résumé sur list à partir du même site:
Une liste est une liste doublement chaînée. C'est, c'est une Séquence qui prend en charge à la fois en avant et en arrière de la traversée, et (amorti) constante de temps de l'insertion et de suppression d'éléments au début ou à la fin, ou au milieu. Des listes ont la propriété la plus importante, la pose et le raccordement de ne pas invalider les itérateurs d'éléments d'une liste, et que même la suppression invalide uniquement les itérateurs qui pointent vers les éléments qui sont supprimés. L'ordre des itérateurs peuvent être modifiées (qui est, liste::iterator peuvent avoir un autre prédécesseur ou successeur après une liste qu'il a fait avant), mais les itérateurs eux-mêmes ne seront pas invalidées ou pour pointer vers les différents éléments, à moins que l'invalidation ou la mutation est explicite.
En résumé, les conteneurs peuvent avoir partagé routines, mais le temps des garanties pour ces routines diffèrent d'un contenant à l'autre. Ceci est très important lors de l'examen qui, ces récipients à utiliser pour une tâche: en tenant compte de la façon dont le conteneur seront les plus fréquemment utilisées (par exemple, plus pour la recherche que pour l'insertion/délétion) va un long chemin pour vous diriger vers la droite du conteneur.
Reed Copsey
Points
315315
std::list est fondamentalement une liste doublement chaînée.
std::deque , en revanche, est mis en œuvre plus comme std::vector . Il a un temps d'accès constant par index, ainsi que des insertions et des suppressions au début et à la fin, ce qui offre des caractéristiques de performances radicalement différentes de celles d'une liste.
Jonathan Graehl
Points
6460
Non. Un deque ne prend en charge que l’insertion et la suppression de O (1) à l’avant et à l’arrière. Il peut, par exemple, être implémenté dans un vecteur avec bouclage. Comme il garantit également un accès aléatoire à O (1), vous pouvez être sûr qu'il n'utilise pas (simplement) une liste doublement chaînée.
Lee B
Points
1748
Les différences de performances ont bien été expliquées par d’autres. Je voulais juste ajouter que des interfaces similaires, voire identiques, sont courantes dans la programmation orientée objet - qui fait partie de la méthodologie générale d'écriture de logiciels orientés objet. Vous ne devriez EN AUCUN CAS supposer que deux classes fonctionnent de la même manière simplement parce qu'elles implémentent la même interface, pas plus que vous ne devriez supposer qu'un cheval fonctionne comme un chien, car elles implémentent à la fois attack () et make_noise ().
