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

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 fonctionnent à l'identique.

Est-ce exact??

Extrait du résumé SGI STL (daté mais toujours très utile) de deque:

Un deque ressemble beaucoup à un vecteur: comme un vecteur, il s'agit d'une séquence qui prend en charge l'accès aléatoire aux éléments, l'insertion et la suppression d'éléments à temps constant à la fin de la séquence, et l'insertion et la suppression en temps linéaire des éléments au milieu.

La principale façon dont deque diffère du vecteur est que deque prend également en charge l'insertion et la suppression à temps constant des éléments au début de la séquence. De plus, deque n'a aucune fonction membre analogue à vector's capacity () et reserve (), et ne fournit aucune des garanties sur la validité de l'itérateur qui sont associées à ces fonctions membres.

Voici le résumé sur listle même site:

Une liste est une liste doublement liée. Autrement dit, il s'agit d'une séquence qui prend en charge à la fois la traversée avant et arrière, et l'insertion et la suppression à temps constant (amorti) d'é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 n'invalide que les itérateurs qui pointent vers les éléments qui sont supprimés. L'ordre des itérateurs peut être modifié (c'est-à-dire que list :: iterator peut avoir un prédécesseur ou un successeur différent après une opération de liste qu'avant), mais les itérateurs eux-mêmes ne seront pas invalidés ou 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 le plus fréquemment utilisé (par exemple, plus pour la recherche que pour l'insertion / suppression) vous oriente dans une large mesure vers le bon conteneur .

Laissez-moi énumérer les différences:

• Deque gère ses éléments avec un tableau dynamique , fournit un accès aléatoire et a presque la même interface qu'un vecteur.
• List gère ses éléments comme une liste doublement chaînée et ne fournit pas d' accès aléatoire .

• Deque fournit des insertions et des suppressions rapides à la fois à la fin et au début. L'insertion et la suppression d'éléments au milieu est relativement lente car tous les éléments jusqu'aux deux extrémités peuvent être déplacés pour faire de la place ou pour combler un vide.
• Dans List , l'insertion et la suppression d'éléments sont rapides à chaque position, y compris aux deux extrémités.

• Deque : toute insertion ou suppression d'éléments autres qu'au début ou à la fin invalide tous les pointeurs, références et itérateurs qui font référence à des éléments du deque.
• Liste : l'insertion et la suppression d'éléments n'invalident pas les pointeurs, références et itérateurs vers 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 essentiellement 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 performances radicalement différentes d'une liste.

Une autre garantie importante est la façon dont chaque conteneur différent 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, 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" mémoire.

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

La stratégie de stockage en mémoire est souvent négligée, cependant, c'est souvent l'une des raisons les plus importantes pour sélectionner le conteneur le plus approprié pour une certaine application.

Non. Un deque ne prend en charge que l'insertion et la suppression d'O (1) à l'avant et à l'arrière. Il peut, par exemple, être implémenté dans un vecteur avec enveloppement. Puisqu'il garantit également un accès aléatoire O (1), vous pouvez être sûr qu'il n'utilise pas (juste) une liste doublement liée.

Les différences de performances 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 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 parce qu'elles implémentent toutes les deux attack () et make_noise ().

Voici un code de preuve de concept utilisant une liste, une carte non ordonnée qui donne une recherche O (1) et une maintenance LRU exacte O (1). Nécessite les itérateurs (non effacés) pour survivre aux opérations d'effacement. Prévoyez d'utiliser dans un cache géré par logiciel arbitrairement grand O (1) pour les pointeurs de processeur sur la mémoire GPU. Fait un signe de tête au planificateur Linux O (1) (file d'attente d'exécution LRU <-> par processeur). Unordered_map a un accès en temps constant via une table de hachage.

#include <iostream> 
#include <list> 
#include <unordered_map>  
using namespace std; 

struct MapEntry {
  list<uint64_t>::iterator LRU_entry;
  uint64_t CpuPtr;
};
typedef unordered_map<uint64_t,MapEntry> Table;
typedef list<uint64_t> FIFO;
FIFO  LRU;        // LRU list at a given priority 
Table DeviceBuffer; // Table of device buffers

void Print(void){
  for (FIFO::iterator l = LRU.begin(); l != LRU.end(); l++) {
    std::cout<< "LRU    entry "<< *l << "   :    " ;
    std::cout<< "Buffer entry "<< DeviceBuffer[*l].CpuPtr <<endl;
  }  
}
int main() 
{ 

  LRU.push_back(0);
  LRU.push_back(1);
  LRU.push_back(2);
  LRU.push_back(3);
  LRU.push_back(4);

  for (FIFO::iterator i = LRU.begin(); i != LRU.end(); i++) {
    MapEntry ME = { i, *i}; 
    DeviceBuffer[*i] = ME;
  }

  std::cout<< "************ Initial set of CpuPtrs" <<endl;
  Print();

  {
    // Suppose evict an entry - find it via "key - memory address uin64_t" and remove from 
    // cache "tag" table AND LRU list with O(1) operations
    uint64_t key=2;
    LRU.erase(DeviceBuffer[2].LRU_entry);
    DeviceBuffer.erase(2);
  }

  std::cout<< "************ Remove item 2 " <<endl;
  Print();

  { 
    // Insert a new allocation in both tag table, and LRU ordering wiith O(1) operations
    uint64_t key=9;
    LRU.push_front(key); 
    MapEntry ME = { LRU.begin(), key };
    DeviceBuffer[key]=ME;
  }

  std::cout<< "************ Add item 9  " <<endl;
  Print();

  std::cout << "Victim "<<LRU.back()<<endl;
} 

Parmi les différences éminentes entre dequeetlist

• Pour deque:

  Articles stockés côte à côte;

  Optimisé pour ajouter des données de deux côtés (avant, arrière);

  Éléments indexés par des nombres (entiers).

  Peut être parcouru par les itérateurs et même par l'index de l'élément.

  L'accès aux données est plus rapide.

• Pour list

  Les éléments stockés "au hasard" dans la mémoire;

  Peut être parcouru uniquement par les itérateurs;

  Optimisé pour l'insertion et le retrait au milieu.

  Le temps d'accès aux données est plus lent, lent à itérer, en raison de sa très mauvaise localisation spatiale.

  Gère très bien les gros éléments

Vous pouvez également vérifier le lien suivant , qui compare les performances entre les deux conteneurs STL (avec std :: vector)

J'espère que j'ai partagé quelques informations utiles.