Was ist der Unterschied zwischen Deque- und List-STL-Containern?

Was ist der Unterschied zwischen den beiden? Ich meine, die Methoden sind alle gleich. Für einen Benutzer funktionieren sie also identisch.

Ist das korrekt??

Aus der (datierten, aber immer noch sehr nützlichen) SGI STL- Zusammenfassung von deque:

Eine Deque ist einem Vektor sehr ähnlich: Wie ein Vektor ist es eine Sequenz, die den wahlfreien Zugriff auf Elemente, das Einfügen und Entfernen von Elementen mit konstanter Zeit am Ende der Sequenz sowie das lineare Einfügen und Entfernen von Elementen in der Mitte in der Mitte unterstützt.

Der Hauptunterschied zwischen deque und Vektor besteht darin, dass deque auch die konstante zeitliche Einfügung und Entfernung von Elementen zu Beginn der Sequenz unterstützt. Darüber hinaus verfügt deque über keine Elementfunktionen, die der Kapazität () und der Reserve () des Vektors entsprechen, und bietet keine der Garantien für die Gültigkeit des Iterators, die diesen Elementfunktionen zugeordnet sind.

Hier ist die Zusammenfassung listvon derselben Site:

Eine Liste ist eine doppelt verknüpfte Liste. Das heißt, es handelt sich um eine Sequenz, die sowohl das Vorwärts- als auch das Rückwärtsdurchlaufen sowie das (amortisierte) Einfügen und Entfernen von Elementen mit konstanter Zeit am Anfang oder am Ende oder in der Mitte unterstützt. Listen haben die wichtige Eigenschaft, dass durch Einfügen und Spleißen Iteratoren für Listenelemente nicht ungültig werden und dass selbst durch Entfernen nur die Iteratoren ungültig werden, die auf die entfernten Elemente verweisen. Die Reihenfolge der Iteratoren kann geändert werden (dh list :: iterator hat nach einer Listenoperation möglicherweise einen anderen Vorgänger oder Nachfolger als zuvor), aber die Iteratoren selbst werden nicht ungültig gemacht oder auf andere Elemente verweisen, es sei denn, diese Ungültigmachung oder Mutation ist explizit.

Zusammenfassend können die Container gemeinsame Routinen haben, aber die Zeitgarantien für diese Routinen unterscheiden sich von Container zu Container . Dies ist sehr wichtig, wenn Sie überlegen, welcher dieser Container für eine Aufgabe verwendet werden soll: Wenn Sie berücksichtigen, wie der Container am häufigsten verwendet wird (z. B. mehr zum Suchen als zum Einfügen / Löschen), werden Sie auf lange Sicht zum richtigen Container geleitet .

Lassen Sie mich die Unterschiede auflisten:

• Deque verwaltet seine Elemente mit einem dynamischen Array , bietet Direktzugriff und hat fast die gleiche Schnittstelle wie ein Vektor.
• List verwaltet seine Elemente als doppelt verknüpfte Liste und bietet keinen wahlfreien Zugriff .

• Deque bietet schnelle Einfügungen und Löschungen sowohl am Ende als auch am Anfang. Das Einfügen und Löschen von Elementen in der Mitte ist relativ langsam, da alle Elemente bis zu beiden Enden verschoben werden können, um Platz zu schaffen oder eine Lücke zu füllen.
• In List ist das Einfügen und Entfernen von Elementen an jeder Position, einschließlich beider Enden, schnell.

• Deque : Jedes Einfügen oder Löschen von anderen Elementen als am Anfang oder Ende macht alle Zeiger, Referenzen und Iteratoren ungültig, die sich auf Elemente der Deque beziehen.
• Liste : Durch das Einfügen und Löschen von Elementen werden Zeiger, Verweise und Iteratoren auf andere Elemente nicht ungültig.

Komplexität

             Insert/erase at the beginning       in middle        at the end

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

std::list ist im Grunde eine doppelt verknüpfte Liste.

std::deque, auf der anderen Seite wird eher wie implementiert std::vector. Es verfügt über eine konstante Zugriffszeit nach Index sowie über das Einfügen und Entfernen am Anfang und Ende, was dramatisch andere Leistungsmerkmale als eine Liste bietet.

Eine weitere wichtige Garantie ist die Art und Weise, wie jeder Container seine Daten speichert:

• Ein Vektor ist ein einzelner zusammenhängender Speicherblock.
• Eine Deque ist ein Satz verknüpfter Speicherblöcke, in denen mehr als ein Element in jedem Speicherblock gespeichert ist.
• Eine Liste ist eine Menge von Elementen, die im Speicher verteilt sind, dh: Pro Speicherblock wird nur ein Element gespeichert.

Beachten Sie, dass die Deque so konzipiert wurde, dass versucht wird, die Vorteile von Vektor und Liste ohne ihre jeweiligen Nachteile auszugleichen. Es ist ein besonders interessanter Container für speicherbeschränkte Plattformen, beispielsweise Mikrocontroller.

Die Speicherstrategie wird häufig übersehen, ist jedoch häufig einer der wichtigsten Gründe für die Auswahl des am besten geeigneten Containers für eine bestimmte Anwendung.

Nein. Eine Deque unterstützt nur das Einfügen und Löschen von O (1) vorne und hinten. Es kann zum Beispiel in einem Vektor mit Wrap-Around implementiert werden. Da es auch O (1) Direktzugriff garantiert, können Sie sicher sein, dass es nicht (nur) eine doppelt verknüpfte Liste verwendet.

Die Leistungsunterschiede wurden von anderen gut erklärt. Ich wollte nur hinzufügen, dass ähnliche oder sogar identische Schnittstellen in der objektorientierten Programmierung üblich sind - ein Teil der allgemeinen Methodik zum Schreiben objektorientierter Software. Sie sollten auf keinen Fall davon ausgehen, dass zwei Klassen auf die gleiche Weise funktionieren, nur weil sie dieselbe Schnittstelle implementieren, genauso wenig wie Sie davon ausgehen sollten, dass ein Pferd wie ein Hund funktioniert, weil beide attack () und make_noise () implementieren.

Hier ist eine Proof-of-Concept-Code-Verwendung der Liste, nicht sortierte Karte, die O (1) Lookup und O (1) genaue LRU-Wartung bietet. Benötigt die (nicht gelöschten) Iteratoren, um Löschvorgänge zu überleben. Planen Sie die Verwendung in einem O (1) beliebig großen, von der Software verwalteten Cache für CPU-Zeiger im GPU-Speicher. Nickt dem Linux O (1) Scheduler zu (LRU <-> Run Queue pro Prozessor). Die unordered_map hat über eine Hash-Tabelle einen zeitlich konstanten Zugriff.

#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;
} 

Unter bedeutenden Unterschieden zwischen dequeundlist

• Für deque:

  Nebeneinander gelagerte Gegenstände;

  Optimiert für das Hinzufügen von Daten von zwei Seiten (vorne, hinten);

  Elemente, die durch Zahlen (Ganzzahlen) indiziert sind.

  Kann von Iteratoren und sogar vom Elementindex durchsucht werden.

  Der zeitliche Zugriff auf Daten ist schneller.

• Zum list

  Elemente, die "zufällig" im Speicher gespeichert sind;

  Kann nur von Iteratoren durchsucht werden.

  Optimiert für das Einsetzen und Entfernen in der Mitte.

  Der zeitliche Zugriff auf Daten ist aufgrund der sehr schlechten räumlichen Lokalität langsamer und langsamer zu iterieren.

  Behandelt sehr gut große Elemente

Sie können auch den folgenden Link überprüfen , der die Leistung zwischen den beiden STL-Containern vergleicht (mit std :: vector).

Ich hoffe, ich habe einige nützliche Informationen geteilt.