Was ist der Unterschied zwischen deque und Liste STL-Containern?

StackOverflow https://stackoverflow.com/questions/1436020

  •  07-07-2019
  •  | 
  •  

Frage

Was ist der Unterschied zwischen den beiden? Ich meine, die Methoden sind alle gleich. Also, für einen Benutzer, arbeiten sie identisch.

Ist das richtig ??

War es hilfreich?

Lösung

Von der (veraltet, aber immer noch sehr nützlich) SGI STL Zusammenfassung der deque :

  

A Deque ist sehr ähnlich wie ein Vektor: wie Vektor, ist es eine Sequenz, die am Ende der Sequenz, und lineare Zeit Einsetzen und Entfernen von Elementen in der wahlfreien Zugriff auf Elemente, konstante Zeit Einsetzen und Entfernen von Elementen unterstützt Mitte.

     

Der Haupt Weise, in der Deque von Vektor unterscheidet, ist, dass Deque unterstützt auch konstante Zeit Einführen und Entfernen von Elementen am Anfang der Sequenz. Zusätzlich deque hat keine Mitgliederfunktionen analog zu Vectors Kapazität () und Reserve () und nicht eine der Garantien für Iterator Gültigkeit liefern, die mit den Elementfunktionen zugeordnet sind.

Hier ist die Zusammenfassung auf list aus dem gleichen Ort:

  

Eine Liste ist eine doppelt verknüpfte Liste. Das heißt, dass es sich um eine Sequenz ist, die sowohl vorwärts als auch rückwärts traversal unterstützt, und (fortgeführten) konstante Zeit Einsetzen und Entfernen der Elemente am Anfang oder am Ende, oder in der Mitte. Listen haben die wichtige Eigenschaft, die das Einfügen und Spleißen nicht Iteratoren ungültig Elemente aufzulisten, und dass auch die Entfernung entkräftet nur die Iteratoren, die auf die Elemente verweisen, die entfernt werden. Die Reihenfolge der Iteratoren kann geändert werden (das heißt, die Liste :: iterator möglicherweise einen anderen Vorgänger oder Nachfolger nach einer Liste Operation haben als vor), aber die Iteratoren sich nicht, es sei denn, dass Ungültigkeits auf verschiedene Elemente hinweisen, für ungültig erklärt oder gemacht werden oder Mutation ist explizit.

Zusammenfassend die Container-Routinen geteilt haben, aber die Zeitgarantien für diese Routinen unterscheiden sich von Container zu Container . Dies ist sehr wichtig, wenn die diese Behälter unter Berücksichtigung für eine Aufgabe zu nutzen: unter Berücksichtigung der wie wird der Behälter am häufigsten verwendet werden (zB mehr für die Suche als für Einfügen / Löschen) geht einem langen Weg in Sie auf der rechten Seite Behälter zu leiten.

Andere Tipps

Lassen Sie mich die Unterschiede Liste unten:

  • Deque verwaltet seine Elemente mit einem dynamisches Array , bietet Random Zugang , und hat fast die gleichen Schnittstelle als Vektor.
  • Liste verwaltet seine Elemente als doppelt verknüpfte Liste und nicht bieten random access .
  • Deque bietet schnelle Einfügungen und Löschungen an sowohl das Ende und der Anfang. Einfügen und Löschen von Elementen in die Mitte ist relativ langsam, da Alle Elemente, bis beide entweder Enden kann bewegt werden, um Platz zu machen oder zu füllt eine Lücke.
  • In Liste , Einfügen und Entfernen von Elementen schnell an jeder Position, einschließlich der beiden Enden.
  • Deque : Jede Einfügen oder Löschen von Elementen außer am Anfang oder Ende entkräftet alle Zeiger, Referenzen, und Iteratoren, die auf Elemente beziehen, der deque.
  • Liste : Einfügen und Löschen von Elementen tun keine Zeiger, Referenzen ungültig machen, und Iteratoren zu anderen Elementen.

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, ist mehr wie std::vector umgesetzt. Es hat eine konstante Zugriffszeit von Index, sowie das Einsetzen und Entfernen am Anfang und Ende, die dramatisch unterschiedliche Leistungsmerkmale als eine Liste bereitstellt.

Nein. A Deque unterstützt nur O (1) das Einfügen und Löschen an der Vorder- und Rückseite. Es kann zum Beispiel in einem Vektor mit Umgriff umgesetzt werden. Da es auch O (1) Direktzugriff garantiert, können Sie sicher sein, dass es nicht mit (nur) eine doppelt verknüpfte Liste.

Eine weitere wichtige Garantie ist die Art und Weise jeweils verschiedene Behälter speichert seine Daten im Speicher:

  • Ein Vektor ist ein einziger zusammenhängender Speicherblock.
  • A Deque ist ein Satz von verknüpften Speicherblöcken, in denen mehr als ein Element in jedem Speicherblock gespeichert ist.
  • Eine Liste ist eine Reihe von Elementen in dem Speicher verteilt sind, d.h .: nur ein Element ist pro Speicher „Block“ gespeichert.

Beachten Sie, dass die deque zu wurde entwickelt, versuchen, die Vorteile von Vektor- und Liste ohne ihre jeweiligen Nachteile ausgleichen. Es ist ein besonders interessanter Behälter in Speicher begrenzt Plattformen, beispielsweise Mikrocontroller.

Die Speicherstrategie oft übersehen wird, ist es jedoch häufig einer der wichtigsten Gründe, die am besten geeigneten Behälter für eine bestimmte Anwendung zu wählen.

Die Leistungsunterschiede wurden gut erklärt durch andere. Ich wollte nur hinzufügen, dass ähnliche oder sogar identische Schnittstellen in der objektorientierten Programmierung üblich sind - ein Teil der allgemeinen Methodologie der objektorientierte Software zu schreiben. Sie sollten KEINESFALLS davon ausgehen, dass zwei Klassen genauso einfach arbeiten, weil sie die gleiche Schnittstelle implementieren, mehr als Sie, dass ein Pferd wie ein Hund arbeitet übernehmen soll, weil sie beide Angriff () implementieren und make_noise ().

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top