Quelle est la différence entre les conteneurs STL deque et list?

Question

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 correct ??

Answer 1

Extrait du STL SGI résumé de deque :

  

Un deque ressemble beaucoup à un vecteur: comme un vecteur, il s’agit d’une séquence prenant en charge l’accès aléatoire aux éléments, l’insertion et le retrait à temps constant d’éléments à la fin de la séquence, et l’insertion et le retrait linéaires d’éléments dans le milieu.

     

La différence principale entre deque et vector est que deque prend également en charge l’insertion et la suppression à temps constant d’éléments au début de la séquence. En outre, deque ne possède aucune fonction membre analogue à la capacité de vector () et à reserve (), et ne fournit aucune des garanties relatives à la validité de l’itérateur qui sont associées à ces fonctions membres.

Voici le résumé de la liste à partir du même site:

  

Une liste est une liste doublement chaînée. C'est-à-dire qu'il s'agit d'une séquence qui prend en charge les parcours avant et arrière, ainsi que l'insertion et l'amortissement à temps constant (amorti) d'éléments au début, à la fin ou au milieu. Les listes ont la propriété importante que l'insertion et le raccordement n'invalident pas les itérateurs pour répertorier les éléments, et que même leur suppression invalide uniquement les itérateurs qui pointent sur les éléments supprimés. La commande des itérateurs peut être changée (c’est-à-dire que list :: iterator peut avoir un prédécesseur ou un successeur différent de celui utilisé auparavant), mais les itérateurs eux-mêmes ne seront pas invalidés ou ne seront pointés vers des éléments différents, à moins que cette invalidation ou la mutation est explicite.

En résumé, les conteneurs peuvent avoir des routines partagées mais les garanties de temps pour ces routines diffèrent d'un conteneur à l'autre . Ceci est très important pour déterminer lequel de ces conteneurs utiliser pour une tâche: prendre en compte la manière dont le conteneur sera utilisé le plus fréquemment (par exemple, davantage pour la recherche que pour l'insertion / suppression) va un long chemin pour vous diriger vers le bon conteneur.

Answer 2

Permettez-moi de lister les différences:

• Deque gère ses éléments avec un tableau dynamique , fournit aléatoire accès et a presque le même interface en tant que vecteur.
• Liste gère ses éléments en tant que liste doublement chaînée et ne fournir un accès aléatoire .

• Deque fournit des insertions et des suppressions rapides à à la fois la fin et le début. Insérer et supprimer des éléments dans le milieu est relativement lent car tous les éléments jusqu'à l'un ou l'autre les extrémités peuvent être déplacées pour faire de la place ou combler un vide.
• Dans Liste , l'insertion et le retrait d'éléments sont rapides à chaque position, y compris les deux extrémités.

• Deque : insertion ou suppression d'éléments autre qu'au début ou à la fin invalide tous les pointeurs, références, et les itérateurs qui font référence à des éléments de la deque.
• Liste : l'insertion et la suppression d'éléments ne pas invalider les pointeurs, références, et itérateurs à d'autres éléments.

Complexité

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

Answer 3

std :: list est fondamentalement un liste doublement chaînée.

std :: deque , à la D'autre part, est implémenté plus comme std :: vector . Il possède 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.

Answer 4

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.

Answer 5

Une autre garantie importante est la manière dont chaque conteneur stocke ses données en mémoire:

• Un vecteur est un seul bloc de mémoire contigu.
• Un deque est un ensemble de blocs de mémoire liés dans lesquels plusieurs éléments sont stockés dans chaque bloc de mémoire.
• Une liste est un ensemble d’éléments dispersés dans la mémoire, c’est-à-dire qu’un seul élément est stocké par mémoire "bloc".

Notez que la deque a été conçue pour essayer d’équilibrer les avantages du vecteur et de la liste sans leurs inconvénients respectifs. C’est un conteneur particulièrement intéressant dans les plates-formes limitées en mémoire, par exemple les microcontrôleurs.

La stratégie de stockage en mémoire est souvent négligée. Cependant, il est souvent l’une des raisons les plus importantes de choisir le conteneur le mieux adapté à une application donnée.

Answer 6

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 devez 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 ().