C++ STL containers: Quelle est la différence entre deque et list?
Quelle est la différence entre les deux? Je veux dire, toutes les techniques sont les mêmes. Donc, pour un utilisateur, ils fonctionnent de manière identique.
Est-ce exact??
6 réponses
du (daté mais encore très utile) SGI STL résumé deque :
une deque est très semblable à un vecteur: comme vecteur, c'est une séquence qui supporte l'accès aléatoire aux éléments, l'insertion à temps constant et l'enlèvement des éléments à la fin de la séquence, et l'insertion linéaire à temps et l'enlèvement des éléments au milieu.
La principale façon dont deque diffère de vector est que deque soutient également l'insertion de temps constant et l'enlèvement des éléments au début de la séquence. De plus, deque n'a aucune fonction de membre analogue à la capacité() et à la réserve () du vecteur, et ne fournit aucune des garanties sur la validité de l'itérateur qui sont associées à ces fonctions de membre.
voici le résumé sur list 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 supporte à la fois la traversée vers l'avant et vers l'arrière, et l'insertion (amortie) en temps constant et l'enlèvement des éléments au début ou à la fin, ou au milieu. Les listes ont la propriété importante que l'insertion et l'épissage n'invalident pas les itérateurs pour lister les éléments, et que même la suppression invalide seulement les itérateurs qui pointent vers les éléments qui sont supprimés. L'ordre des itérateurs peuvent être modifiées (c'est, list:: iterator peut avoir un prédécesseur ou un successeur différent après une opération list), mais les itérateurs eux-mêmes ne seront pas invalidés ou mis en évidence des éléments différents à moins que cette invalidation ou mutation ne soit explicite.
en résumé, les conteneurs peuvent avoir des routines communes mais les garanties de temps pour ces routines diffèrent d'un conteneur à l'autre . C'est très important lorsque l'on considère lequel des ces conteneurs à utiliser pour une tâche: prendre en compte comment le conteneur sera le plus souvent utilisé (par exemple, plus pour la recherche que pour l'insertion/suppression) va un long chemin en vous dirigeant vers le bon conteneur.
permettez-moi d'énumérer les différences:
- Deque gère ses éléments avec un tableau dynamique , prévoit que aléatoire accès , et a presque le même interface comme vecteur.
- Liste gère ses éléments liste doublement liée et ne fournir accès aléatoire .
- Deque fournit des insertions rapides et des suppressions à à 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 liste , l'insertion et la suppression des éléments est rapide à chaque position, y compris les deux extrémités.
- Deque : toute insertion ou suppression d'éléments d'autres qu'au début ou à la fin annule tous les pointeurs, références, et les itérateurs qui se réfèrent aux éléments de la deque.
- liste : L'insertion et la suppression d'éléments ne ne pas invalider les pointeurs, les 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
std::list est fondamentalement une liste doublement liée.
std::deque , d'autre part, est mis en œuvre plus comme std::vector . Il a un temps d'accès constant par index, ainsi que l'insertion et la suppression au début et à la fin, ce qui fournit des caractéristiques de performance radicalement différentes d'une liste.
Pas de. Un deque ne supporte que L'insertion et la suppression O (1) à l'avant et à l'arrière. Il peut, par exemple, être mis en œuvre dans un vecteur avec enroulement. Comme il garantit également l'accès aléatoire O (1), vous pouvez être sûr qu'il n'utilise pas (juste) une liste doublement liée.
une autre garantie importante est la façon dont chaque conteneur stocke ses données en mémoire:
- un vecteur est un bloc de mémoire contigu simple.
- Un deque est un ensemble de blocs de mémoire, où plus d'un élément est stocké dans chaque bloc de mémoire.
- une liste est un ensemble d'éléments dispersés en mémoire, c'est-à-dire qu'un seul élément est stocké par"bloc" de mémoire.
noter que le deque a été conçu pour essayer de équilibrer les avantages de vecteur et de liste sans leurs inconvénients respectifs. Il s'agit d'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 de mémoire est souvent négligée, cependant, il est souvent l'une des raisons les plus importantes de choisir le contenant le plus approprié pour une certaine application.
les différences de rendement ont été bien expliquées par d'autres. Je voulais juste ajouter que des interfaces similaires ou même identiques sont courantes dans la programmation orientée objet -- une 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 devez supposer qu'un cheval fonctionne comme un chien parce qu'ils implémentent attack() et make_noise().