Warum würde ich es vorziehen, Vektor zum Deque zu verwenden?

Schon seit

1. sie sind beide zusammenhängende Speichercontainer;
2. In Bezug auf die Funktionen hat deque fast alles, was der Vektor hat, aber mehr, da es effizienter ist, vorne einzufügen.

Warum whould jemand lieber std::vectorzu std::deque?

Elemente in a dequesind im Gedächtnis nicht zusammenhängend; vectorElemente sind garantiert. Wenn Sie also mit einer einfachen C-Bibliothek interagieren müssen, die zusammenhängende Arrays benötigt, oder wenn Sie sich (viel) für die räumliche Lokalität interessieren, bevorzugen Sie möglicherweise vector. Da es eine zusätzliche Buchhaltung gibt, sind andere vectorOperationen wahrscheinlich (etwas) teurer als ihre entsprechenden Operationen. Andererseits kann die Verwendung vieler / großer Instanzen von vectorzu einer unnötigen Heap-Fragmentierung führen (Verlangsamung der Aufrufe vonnew ).

Wie bereits an anderer Stelle in StackOverflow erwähnt , gibt es hier weitere gute Diskussionen: http://www.gotw.ca/gotw/054.htm .

Um den Unterschied zu kennen, sollte man wissen, wie dequeallgemein implementiert wird. Der Speicher wird in gleich großen Blöcken zugewiesen und miteinander verkettet (als Array oder möglicherweise als Vektor).

Um das n-te Element zu finden, finden Sie den entsprechenden Block und greifen dann auf das darin enthaltene Element zu. Dies ist eine konstante Zeit, da es immer genau 2 Suchvorgänge sind, aber das ist immer noch mehr als der Vektor.

vectorfunktioniert auch gut mit APIs, die einen zusammenhängenden Puffer benötigen, da sie entweder C-APIs sind oder vielseitiger darin sind, einen Zeiger und eine Länge zu verwenden. (So ​​können Sie einen Vektor darunter oder ein reguläres Array haben und die API aus Ihrem Speicherblock aufrufen).

Wo dequehat seine größten Vorteile:

1. Beim Wachsen oder Schrumpfen der Sammlung an beiden Enden
2. Wenn Sie es mit sehr großen Sammlungsgrößen zu tun haben.
3. Wenn es um Bools geht und Sie wirklich eher Bools als ein Bitset wollen.

Die zweite davon ist weniger bekannt, aber für sehr große Sammlungsgrößen:

1. Die Kosten für die Neuzuweisung sind hoch
2. Der Aufwand, einen zusammenhängenden Speicherblock finden zu müssen, ist begrenzt, sodass Ihnen schneller der Speicher ausgeht.

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

Nach alledem können Probleme mit std::dequeSystemen auftreten, die eine "optimistische" Speicherzuordnung verwenden. Während seine Versuche, eine große Puffergröße für eine Neuzuweisung von a anzufordern, vectorwahrscheinlich irgendwann mit a abgelehnt werden bad_alloc, wird die optimistische Natur des Allokators wahrscheinlich immer die Anforderung für den kleineren Puffer gewähren, der von a angefordert wird, dequeund dies wird wahrscheinlich dazu führen das Betriebssystem, um einen Prozess abzubrechen, um zu versuchen, etwas Speicher zu erhalten. Welches auch immer es auswählt, es ist vielleicht nicht zu angenehm.

Die Problemumgehungen in einem solchen Fall bestehen entweder darin, Flags auf Systemebene zu setzen, um die optimistische Zuordnung zu überschreiben (was nicht immer möglich ist), oder den Speicher etwas manueller zu verwalten, z. B. mithilfe Ihres eigenen Allokators, der die Speichernutzung überprüft, oder ähnlichem. Offensichtlich nicht ideal. (Welches kann Ihre Frage beantworten, um Vektor zu bevorzugen ...)

Ich habe sowohl Vektor als auch Deque mehrmals implementiert. deque ist aus Sicht der Implementierung sehr viel komplizierter. Diese Komplikation führt zu mehr Code und komplexerem Code. Daher wird normalerweise ein Treffer in der Codegröße angezeigt, wenn Sie Deque anstelle von Vektor auswählen. Es kann auch zu einem kleinen Geschwindigkeitstreffer kommen, wenn Ihr Code nur die Dinge verwendet, bei denen sich der Vektor auszeichnet (dh push_back).

Wenn Sie eine Warteschlange mit zwei Enden benötigen, ist deque der klare Gewinner. Wenn Sie jedoch die meisten Einfügungen und Löschungen auf der Rückseite vornehmen, wird der Vektor der klare Gewinner sein. Wenn Sie sich nicht sicher sind, deklarieren Sie Ihren Container mit einem typedef (damit Sie leicht hin und her wechseln können) und messen Sie.

std::dequehat keinen garantierten kontinuierlichen Speicher - und ist für den indizierten Zugriff oft etwas langsamer. Eine Deque wird typischerweise als "Liste von Vektoren" implementiert.

Laut http://www.cplusplus.com/reference/stl/deque/ "ist es im Gegensatz zu Vektoren nicht garantiert, dass Deques alle ihre Elemente in zusammenhängenden Speicherorten haben, wodurch die Möglichkeit eines sicheren Zugriffs durch Zeigerarithmetik ausgeschlossen wird."

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

(Zuvor hatte meine Antwort einen Mangel an Standardisierung angesprochen (aus derselben Quelle wie oben, "Deques können von bestimmten Bibliotheken auf unterschiedliche Weise implementiert werden"), aber das gilt tatsächlich für nahezu jeden Standardbibliotheksdatentyp.)

Ein Deque ist ein Sequenzcontainer, der den wahlfreien Zugriff auf seine Elemente ermöglicht, für den jedoch keine zusammenhängende Speicherung garantiert ist.

Ich denke, diese gute Idee, einen Leistungstest für jeden Fall durchzuführen. Und treffen Sie Ihre Entscheidung anhand dieser Tests.

Ich würde es vorziehen std::dequeals std::vectorin den meisten Fällen.

Sie würden es nicht vorziehen, wenn der Vektor gemäß diesen Testergebnissen (mit Quelle) deque ist .

Natürlich sollten Sie in Ihrer App / Umgebung testen, aber zusammenfassend:

• push_back ist grundsätzlich für alle gleich
• Einfügen, Löschen in Deque sind viel schneller als Liste und geringfügig schneller als Vektor

Noch ein paar Überlegungen und ein Hinweis, um den Circular_Buffer zu berücksichtigen.

Einerseits ist der Vektor ziemlich häufig einfach schneller als die Deque. Wenn Sie nicht alle Funktionen von deque benötigen , verwenden Sie einen Vektor.

Auf der anderen Seite, manchmal Sie tun müssen Funktionen , die Vektor Ihnen nicht geben, in dem Fall , dass Sie eine deque verwenden. Zum Beispiel fordere ich jeden auf, zu versuchen, diesen Code neu zu schreiben , ohne eine Deque zu verwenden und ohne den Algorithmus enorm zu verändern.

Beachten Sie, dass der Vektorspeicher neu zugewiesen wird, wenn das Array wächst. Wenn Sie Zeiger auf Vektorelemente haben, werden diese ungültig.

Wenn Sie ein Element löschen, werden Iteratoren ungültig (jedoch nicht "für (auto ...)").

Bearbeiten: 'deque' in 'vector' geändert