Ich habe angefangen, Vergleiche zwischen:
zu machen Aber dann bemerkte ich, dass sogar auf push_back() die Deque schneller schien. Ich muss etwas falsch machen, ich kann nicht glauben, dass ein allgemeinerer Container einen bestimmten übertreffen würde.
Mein Code mit Google Benchmark:
%Vor%Ergebnisse:
%Vor%Ich merke einige Unterschiede beim Spielen mit der Anzahl der Elemente, aber Deque übertrifft immer Vektor.
BEARBEITEN:
Compiler: gcc version 5.2.1
Kompilieren mit: g++ -O3 -std=c++11 push_front.cpp -lbenchmark -lpthread
Ich denke, dass -O3 tatsächlich instrumentell ist; wenn ich es ausschalte, bekomme ich eine etwas schlechtere Performance.
Ich denke, der Vektor ist langsamer, weil Sie clear() aufrufen, was, abhängig von Ihrer STL-Implementierung, möglicherweise den zugrunde liegenden Array-Speicher freigibt.
Wenn das der Fall ist, hilft Ihr reserve() -Aufruf nicht; und Ihr Vektor wird ständig skaliert, was erfordert, dass jedes Element in den neuen, größeren Speicher verschoben wird.
Es gibt grundsätzlich drei Kostenquellen, die beim kontinuierlichen Anhängen von Elementen an einen dynamischen Container entstehen:
Beginnen wir mit 1. vector fragt nach dem doppelten Speicher, und deque weist Blöcke fester Größe zu ( deque wird normalerweise als ein Array von Arrays implementiert, wobei die Arrays der unteren Ebene eine feste Größe haben). Nach mehr Speicher zu fragen kann länger dauern, als nach weniger zu fragen, aber wenn Ihr Heap nicht sehr fragmentiert ist und Sie nach einem großen Chunk auf einmal fragen, ist das der schnellste Weg, etwas Speicher zu bekommen. Es ist wahrscheinlich schneller, ein Megabyte einmal zuzuweisen und dann 1.000 Mal nach einem Kilobyte zu fragen. Es scheint also klar zu sein, dass vector hier den Vorteil haben wird (bis der Container so groß ist, dass er von der Fragmentierung betroffen ist). Dies ist jedoch nicht der Fall: Sie haben nur 1000 Elemente angefordert. Ich habe den folgenden Code Ссылка geschrieben. Es ist nicht sehr interessant, aber es verwendet im Grunde einen trivialen Allokator, der ein globales erhöht, um zu sehen, wie viele Zuweisungen durchgeführt werden.
vector fragt im Rahmen Ihrer Benchmark 11-mal nach Speicher und deque nur 10. 10. deque fragt immer nach dem gleichen Betrag, vector fragt nach verdoppelnden Beträgen. Außerdem muss vector free 10 mal aufrufen. Und deque 0. Das scheint ein kleiner Gewinn für deque zu sein.
Für interne Buchhaltung hat vector eine einfachere Implementierung als deque . Immerhin ist vector nur ein dynamisches Array und deque ist ein Array von Arrays und ist streng komplexer. Das ist also eindeutig ein Gewinn für vector .
Schließlich Elemente für die Operationen selbst. In deque wird nichts bewegt. Mit vector beinhaltet jede neue Heap-Zuweisung auch das Verschieben aller Elemente. Es ist wahrscheinlich optimiert, um memcpy für triviale Typen zu verwenden, aber es sind sogar 10 Aufrufe von memcpy , um 1, 2, 4, 8 ... 512 Ganzzahlen zu kopieren. Dies ist eindeutig ein Gewinn für deque .
Ich kann spekulieren, dass das Hochdrehen auf O3 sehr aggressives Inlinen von vielen der komplexeren Codepaths in deque erlaubt, was das Gewicht von 2 reduziert. Aber natürlich, wenn Sie nicht viel detaillierter (sehr vorsichtig!) ) Benchmark, werden Sie nie sicher wissen.
Meistens soll dieser Beitrag zeigen, dass er komplexer ist als nur ein spezieller Container gegenüber einem allgemeineren Container. Ich werde jedoch eine Vorhersage machen (meinen Hals herausziehen, um sozusagen abgeschnitten zu werden): Wenn Sie die Anzahl der Elemente um einen Faktor von 2 oder 4 erhöhen, werden Sie deque win nicht mehr sehen. Das liegt daran, dass deque 2x oder 4x so viele Heap-Zuweisungen macht, aber Vektor nur 1-2 mehr macht.
Ich kann auch hier notieren, dass deque tatsächlich eine Art von einer ungeraden Datenstruktur ist; Es ist theoretisch ein Array von Arrays, aber in vielen Implementierungen hat das Array entweder eine bestimmte Größe oder nur ein Element, je nachdem, welches größer ist. Auch einige der großen O-Garantien sind Unsinn. push_back ist nur konstante Zeitkonstante, da in C ++ nur Operationen an den Elementen selbst zum großen O zählen. Ansonsten sollte klar sein, dass das Array der obersten Ebene, da es sich um ein Array von Arrays handelt, proportional zur Größe ist Anzahl der bereits gespeicherten Elemente. Und schließlich hat dieses Top-Level-Array keinen Platz mehr, und Sie müssen es neu zuweisen, indem Sie O (N) -Zeiger verschieben. Also ist es nicht wirklich O (1) push_back .