Warum sollte ich die Verwendung von Vektor gegenüber Deque vorziehen?

Question

Seit

1. sie sind beide zusammenhängende Speichercontainer;
2. Feature weise, deque hat fast alles, was Vektor hat, aber mehr, da es effizienter ist, in der Front einzufügen.

Warum sollte jemand die std::vector a std::deque ?

Answer 1

Elemente in einem deque son pas zusammenhängend im Speicher; vector Elemente sind garantiert. Wenn Sie also mit einer einfachen C-Bibliothek interagieren müssen, die zusammenhängende Arrays benötigt, oder wenn Sie (viel) Wert auf räumliche Lokalität legen, dann sollten Sie vector . Darüber hinaus sind andere Operationen aufgrund des zusätzlichen Buchführungsaufwands wahrscheinlich (etwas) teurer als ihre Entsprechung. vector Operationen. Andererseits ist die Verwendung vieler/großer Instanzen von vector kann zu einer unnötigen Fragmentierung des Heaps führen (Verlangsamung der Aufrufe von new ).

Außerdem, wie bereits erwähnt anderswo auf StackOverflow gibt es hier weitere gute Diskussionen: http://www.gotw.ca/gotw/054.htm .

Answer 2

Um den Unterschied zu erkennen, sollte man wissen, wie deque wird generell umgesetzt. Der Speicher wird in gleich großen Blöcken zugewiesen, die miteinander verkettet werden (als Array oder möglicherweise als Vektor).

Um also das n-te Element zu finden, suchen Sie den entsprechenden Block und greifen dann auf das Element in diesem Block zu. Das ist konstante Zeit, weil es immer genau 2 Suchvorgänge sind, aber das ist immer noch mehr als der Vektor.

vector funktioniert auch gut mit APIs, die einen zusammenhängenden Puffer wollen, weil sie entweder C-APIs sind oder vielseitiger in der Lage, einen Zeiger und eine Länge zu nehmen sind. (So können Sie einen Vektor unter oder ein reguläres Array haben und die API von Ihrem Speicherblock aufrufen).

Wo deque hat seine größten Vorteile sind:

1. Beim Vergrößern oder Verkleinern der Sammlung von beiden Seiten
2. Wenn Sie es mit sehr großen Sammlungen zu tun haben.
3. Beim Umgang mit bools und Sie wirklich wollen bools und nicht ein Bitset.

Der zweite ist weniger bekannt, aber für sehr große Sammlungen:

1. Die Kosten der Umverteilung sind hoch
2. Der Overhead, der durch die Suche nach einem zusammenhängenden Speicherblock entsteht, ist einschränkend, so dass der Speicher schneller erschöpft sein kann.

Als ich in der Vergangenheit mit großen Sammlungen zu tun hatte und von einem zusammenhängenden Modell zu einem Blockmodell wechselte, konnten wir etwa fünfmal so große Sammlungen speichern, bevor uns in einem 32-Bit-System der Speicher ausging. Das liegt zum Teil daran, dass bei der Neuzuweisung sowohl der alte als auch der neue Block gespeichert werden musste, bevor die Elemente kopiert wurden.

Allerdings können Sie Probleme bekommen mit std::deque auf Systemen, die eine "optimistische" Speicherzuweisung verwenden. Während seine Versuche, eine große Puffergröße für eine Neuzuweisung von Speicherplatz anzufordern vector wird wahrscheinlich irgendwann mit einer bad_alloc wird die optimistische Natur der Zuteilungsfunktion wahrscheinlich immer dem Antrag auf den kleineren Puffer stattgeben, der von einem deque und das wird wahrscheinlich dazu führen, dass das Betriebssystem einen Prozess abbricht, um zu versuchen, etwas Speicher zu bekommen. Welchen Weg es auch immer wählt, er könnte nicht sehr angenehm sein.

Die Abhilfe in einem solchen Fall besteht entweder darin, Flags auf Systemebene zu setzen, um die optimistische Zuteilung außer Kraft zu setzen (was nicht immer möglich ist), oder den Speicher etwas manueller zu verwalten, z. B. mit einem eigenen Allokator, der die Speichernutzung überprüft. Offensichtlich nicht ideal. (Was vielleicht Ihre Frage nach dem bevorzugten Vektor beantwortet...)

Answer 3

Ich habe sowohl Vektor und deque mehrere Male implementiert. deque ist enorm komplizierter von einem Standpunkt der Implementierung. Diese Komplikation führt zu mehr Code und komplexerem Code. Wenn Sie sich also für Deque statt für Vektor entscheiden, werden Sie in der Regel einen Größenvorteil beim Code haben. Sie können auch einen kleinen Geschwindigkeitsvorteil erfahren, wenn Ihr Code nur die Dinge verwendet, die der Vektor besonders gut kann (z.B. push_back).

Wenn Sie eine Warteschlange mit zwei Enden benötigen, ist deque der eindeutige Sieger. Wenn Sie jedoch die meisten Einfüge- und Löschvorgänge auf der Rückseite durchführen, ist vector der eindeutige Sieger. Wenn Sie unsicher sind, deklarieren Sie Ihren Container mit einem Typendefinition (so ist es einfach, hin und her zu wechseln), und messen.

Answer 4

std::deque hat keinen garantierten kontinuierlichen Speicher - und ist bei indiziertem Zugriff oft etwas langsamer. Eine Deque wird in der Regel als eine "Liste von Vektoren" implementiert.

Answer 5

Según http://www.cplusplus.com/reference/stl/deque/ Im Gegensatz zu Vektoren ist bei Deques nicht garantiert, dass sich alle Elemente an zusammenhängenden Speicherplätzen befinden, so dass die Möglichkeit eines sicheren Zugriffs durch Zeigerarithmetik nicht gegeben ist.

Deques sind etwas komplizierter, zum Teil weil sie nicht unbedingt ein zusammenhängendes Speicherlayout haben. Wenn Sie diese Funktion benötigen, sollten Sie kein Deque verwenden.

(Zuvor hatte meine Antwort auf einen Mangel an Standardisierung hingewiesen (aus derselben Quelle wie oben: "Deques können von bestimmten Bibliotheken auf unterschiedliche Weise implementiert werden"), aber das gilt eigentlich für so gut wie jeden Standardbibliotheksdatentyp).