std::vector<> oder std::deque<>?
-
In seinem Guru of The Week Artikel #54 schreibt Herb Sutter, dass man an meistens std::deque vorziehen soll, weil der nicht garantiert, dass alle Elemente in einem Stueck Speicher hintereinander stehen muessen und deshalb nicht staendig alles umkopieren muss, wenn er seine aktuelle Kapazitaet ueberschreitet beim Fuellen. Vector solle nur dann benutzt werden, wenn man eben diese Eigenschaft der kontinuierlichen Speicherbelegung nutzen will. Leider sind seine Performancetests schon etwas aelter, daher weiss ich nciht, wie aktuell dieser Tip noch ist.
Weiss jemand genaueres? (Z.B einen Link wo man mehr drueber lesen kann)
-
Im Endeffekt dürften beide Container vergleichbare Geschwindigkeiten bieten - vector<> braucht im Spitzenwert etwas mehr Zeit zum einfügen (durch die Speicherstrategie gleicht sich das im Durchschnitt aus), deque<> ist etwas langsamer beim Zugriff (aufwendigere Index-Umrechnungen). Was du letztlich verwendest, mußt du selber entscheiden (bzw. eigene Vergleichsmessungen anstellen).
Zwei eindeutige Vorteile von deque<> sind übrigens:
- es bietet push_front() und pop_front()
- es geht mitunter sparsamer mit dem Speicherplatz um
PS: Übrigens kann man sich das regelmäßige Umkopieren beim vector<> auch ersparen, indem man vorher genug Kapazität anfordert (reserve()).
-
Ich würde sagen es kommt drauf an was man braucht.
std::vector hat meist die schnelleren Iteratoren.
std::vector ist meist schneller wenn er selten wachsen muss - was z.B. der Fall ist wenn man immer mal wieder Elemente hinten rausnimmt und neue einfügt, die Grösse aber einen bestimmten Wert nicht überschreitet.
std::deque ist schneller wenn man vorne Elemente einfügen oder löschen will.
std::deque ist oft schneller wenn man Elemente hat die sehr teuer zu kopieren sind.
