Aus der (veraltet, aber immer noch sehr nützlich) SGI-STL Zusammenfassung der deque:
Eines deque ist sehr viel wie ein Vektor: wie vector, es ist eine Sequenz, unterstützt wahlfreien Zugriff auf Elemente, Konstante Zeit einsetzen und entfernen von Elementen an das Ende der Sequenz, und der linearen Zeit einsetzen und entfernen von Elementen in der Mitte.
Die Art und Weise, wie die deque unterscheidet sich von vector ist, dass deque unterstützt auch Konstante Zeit einsetzen und entfernen von Elementen am Anfang der Sequenz. Darüber hinaus deque keine member-Funktionen Analog zu Vektor-Kapazität() und reserve(), und nicht die Garantien für die iterator-Gültigkeit, die im Zusammenhang mit den Funktionen.
Hier ist die Zusammenfassung auf list von der selben Seite:
Einer Liste eine doppelt verkettete Liste. Das heißt, es ist eine Sequenz, unterstützt sowohl vorwärts und rückwärts traversieren und (amortisiert) Konstante Zeit einsetzen und entfernen von Elementen am Anfang oder am Ende oder in der Mitte. Listen haben die wichtige Eigenschaft, dass beim einfügen und Spleißen nicht ungültig Iteratoren auf Listen-Elemente, und dass Sie selbst entfernen, erlischt nur die Iteratoren, die auf die Elemente, die entfernt werden. Die Bestellung von Iteratoren kann geändert werden (das heißt, Liste::iterator hätte vielleicht eine andere Vorgänger-oder Nachfolger nach der Liste Bedienung als vorher), aber die Iteratoren selbst nicht für ungültig erklärt werden oder zeigen Sie auf verschiedene Elemente, es sei denn, die Nichtigkeit oder die mutation ist explizit.
In der Zusammenfassung der Container kann haben gemeinsame Routinen, sondern die Zeit, die Garantien für diejenigen, die Routinen unterscheiden sich von container zu container. Dies ist sehr wichtig, wenn man die von dieser Behälter zu verwenden, die für eine Aufgabe: unter Berücksichtigung wie die container werden am häufigsten verwendet (z.B., mehr zum suchen als zum einfügen/löschen) geht ein langer Weg, leitet Sie an die richtigen Behälter.
std::list hat auch die 'splice' - Methode können Sie Zusammenführen von zwei Listen zusammen
Eigentlich ist die Zeit garantiert sind die zweite wichtigste feature-Liste. Die meisten wichtige Eigenschaft von Listen ist, dass Sie können hinzufügen und entfernen von Elementen und nicht erlöschen Ihrer Iteratoren! In (fast?) alle anderen STL container, jeder edit-operation ist ungültig, alle Ihre Iteratoren, also "löschen" passende Artikel", die Sie sammeln müssen, um die passenden Artikel in einem Vorgang und löschen Sie Sie dann in einem anderen. In einer Liste, können Sie zu Fuß durch Sie, entfernen und hinzufügen, wie Sie wollen, und nie haben, um eine Neuberechnung einen iterator.
Dies sind auch die abstrakten Unterschiede, so Messen die Realität für Ihren Fall! Sowohl list und deque O(1) einfügen/löschen, aber vergessen Sie nicht, dass bedeutet, dass k * O(1), und k unterschiedliche Werte für list und deque. In meinem Fall dauerte es zehn mal länger, um ein Objekt hinzuzufügen, um eine Liste als eine deque, weil die Liste braucht mehr Aufrufe von new/delete. Das wird natürlich variieren, basierend auf dem STL-Implementierung, die Sie haben.
Lassen Sie mich Liste nach unten zu den unterschieden:
Deque verwaltet seine Elemente mit ein dynamisches array, bietet random
Zugang, und hat fast die gleiche
Schnittstelle als eine vector.
Liste verwaltet seine Elemente als eine doppelt verkettete Liste und nicht
bieten random-access -.
Deque bietet Schnelle Einfüge-und Löschoperationen an
sowohl das Ende und den Anfang. Einfügen und löschen von Elementen in
die Mitte ist relativ langsam, da
alle Elemente bis auf einen der beiden
enden verschoben werden kann, um Platz zu machen oder um
eine Lücke füllen.
In Liste, einfügen und entfernen von Elementen ist schnell an jeder position,
einschließlich der beiden enden.
Deque: Jedes einfügen oder löschen von Elementen
andere als am Anfang oder Ende
ungültig macht, alle Zeiger, Referenzen,
und Iteratoren, die sich auf Elemente
der deque.
Liste: Einfügen und löschen von Elementen funktioniert
nicht ungültig, Zeiger, Referenzen,
und Iteratoren zu anderen Elementen.
Komplexität
Insert/erase at the beginning in middle at the endDeque:Amortized constant LinearAmortized constant
List:ConstantConstantConstant
Was ist der Unterschied zwischen constant und amortized constant?
Operationen auf lange Sicht Verhalten sich wie beschrieben. Allerdings, eine einzelne operation kann länger dauern als angegeben. ex: einfügen ein element in einen Vektor, dessen aktuelle Kapazität ist 10 und die Größe schon 9 konstant ist, wo ist die Zeit linear, wenn die Kapazität ist 10 und die Größe ist auch 10. Sein, weil es hat zu reservieren und kopieren Sie alle Elemente, um neue Speicher.
Wie funktioniert deque bieten random access? Auch, wie ist diese Struktur implementiert?
std::list ist im Prinzip eine doppelt verkettete Liste.
std::deque, auf der anderen Seite implementiert ist, mehr wie std::vector. Es hat ständigen Zugriff auf die Zeit von index, sowie das einfügen und entfernen an Anfang und Ende, die für erheblich unterschiedliche Leistungsmerkmale als eine Liste.
Nicht. Eine deque unterstützt nur O(1) einfügen und löschen an der Vorder-und Rückseite. Es kann zum Beispiel umgesetzt werden, ein Vektor mit wrap-around. Da es auch garantiert O(1) random access, können Sie sicher sein, es nutzt nicht (nur) eine doppelt verkettete Liste.
Andere wichtige Garantie ist die Art, wie die verschiedenen container speichert seine Daten im Speicher:
Ein Vektor ist eine einzige zusammenhängende Speicher block.
Eine deque ist eine Gruppe von verbundenen Speicher-Blöcke, in denen mehr als ein element gespeichert ist, die in jedem Speicherblock.
Eine Liste ist eine Reihe von Elementen, die verstreut im Speicher, d.h.: immer nur ein element gespeichert ist pro Speicher "block".
Beachten Sie, dass die deque wurde entwickelt, um versuchen Gleichgewicht der Vorteile von Vektor und Liste ohne deren jeweiligen Nachteile. Es ist eine besonders interessante container im Speicher begrenzt Plattformen, wie zum Beispiel mikrocontroller.
Ist der Speicher-Strategie wird jedoch oft übersehen, ist es Häufig einer der wichtigsten Gründe für die Auswahl der am meisten passenden container für eine bestimmte Anwendung.
Die performance-Unterschiede erklärt wurden, auch von anderen. Ich wollte nur hinzufügen, dass ähnliche oder sogar identische Schnittstellen sind Häufig in der objektorientierten Programmierung-Teil der Allgemeinen Methodik des Schreibens object-oriented software. Sie sollten IN KEINER WEISE davon ausgehen, dass zwei Klassen auf die gleiche Weise arbeiten, weil Sie einfach zu implementieren das gleiche interface, mehr, als Sie sollten davon ausgehen, dass ein Pferd, arbeiten wie ein Hund, weil Sie beide implementieren Angriff() und make_noise().
Aus der (veraltet, aber immer noch sehr nützlich) SGI-STL Zusammenfassung der
deque:Hier ist die Zusammenfassung auf
listvon der selben Seite:In der Zusammenfassung der Container kann haben gemeinsame Routinen, sondern die Zeit, die Garantien für diejenigen, die Routinen unterscheiden sich von container zu container. Dies ist sehr wichtig, wenn man die von dieser Behälter zu verwenden, die für eine Aufgabe: unter Berücksichtigung wie die container werden am häufigsten verwendet (z.B., mehr zum suchen als zum einfügen/löschen) geht ein langer Weg, leitet Sie an die richtigen Behälter.
Lassen Sie mich Liste nach unten zu den unterschieden:
dynamisches array, bietet random
Zugang, und hat fast die gleiche
Schnittstelle als eine vector.
doppelt verkettete Liste und nicht
bieten random-access -.
sowohl das Ende und den Anfang. Einfügen und löschen von Elementen in
die Mitte ist relativ langsam, da
alle Elemente bis auf einen der beiden
enden verschoben werden kann, um Platz zu machen oder um
eine Lücke füllen.
einschließlich der beiden enden.
andere als am Anfang oder Ende
ungültig macht, alle Zeiger, Referenzen,
und Iteratoren, die sich auf Elemente
der deque.
nicht ungültig, Zeiger, Referenzen,
und Iteratoren zu anderen Elementen.
Komplexität
constantundamortized constant?std::listist im Prinzip eine doppelt verkettete Liste.std::deque, auf der anderen Seite implementiert ist, mehr wiestd::vector. Es hat ständigen Zugriff auf die Zeit von index, sowie das einfügen und entfernen an Anfang und Ende, die für erheblich unterschiedliche Leistungsmerkmale als eine Liste.Nicht. Eine deque unterstützt nur O(1) einfügen und löschen an der Vorder-und Rückseite. Es kann zum Beispiel umgesetzt werden, ein Vektor mit wrap-around. Da es auch garantiert O(1) random access, können Sie sicher sein, es nutzt nicht (nur) eine doppelt verkettete Liste.
Andere wichtige Garantie ist die Art, wie die verschiedenen container speichert seine Daten im Speicher:
Beachten Sie, dass die deque wurde entwickelt, um versuchen Gleichgewicht der Vorteile von Vektor und Liste ohne deren jeweiligen Nachteile. Es ist eine besonders interessante container im Speicher begrenzt Plattformen, wie zum Beispiel mikrocontroller.
Ist der Speicher-Strategie wird jedoch oft übersehen, ist es Häufig einer der wichtigsten Gründe für die Auswahl der am meisten passenden container für eine bestimmte Anwendung.
Die performance-Unterschiede erklärt wurden, auch von anderen. Ich wollte nur hinzufügen, dass ähnliche oder sogar identische Schnittstellen sind Häufig in der objektorientierten Programmierung-Teil der Allgemeinen Methodik des Schreibens object-oriented software. Sie sollten IN KEINER WEISE davon ausgehen, dass zwei Klassen auf die gleiche Weise arbeiten, weil Sie einfach zu implementieren das gleiche interface, mehr, als Sie sollten davon ausgehen, dass ein Pferd, arbeiten wie ein Hund, weil Sie beide implementieren Angriff() und make_noise().