Ich habe ein kleines Stück Code geschrieben, um zu bestimmen, wie die Speicherzuweisung in einem Vektor erfolgt.
%Vor%Ich habe das mit Visual Studio 2008 und g ++ 4.5.2 unter Ubuntu kompiliert und habe folgende Ergebnisse erhalten:
Visual Studio:
1 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066 1599 2398 3597 5395 8092 12138 18207 27310 40965 61447 92170 138255
%Vor%g ++:
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072
%Vor%Wie Sie sehen können, sind dies zwei sehr unterschiedliche Ergebnisse. Warum ist das so? Ist es nur abhängig vom Compiler oder ist es süchtig nach anderen Faktoren?
Macht es wirklich Sinn, die Kapazität auch für eine große Anzahl von Elementen zu verdoppeln?
Wie der vector wächst, ist die Implementierung definiert. Es können also verschiedene Strategien verwendet werden, die nach dem Einfügen derselben Anzahl von Elementen zu einer anderen Kapazität führen.
Wenn Sie sich darauf verlassen müssen, wie viele Artikel zugeordnet sind, sollten Sie reserve und / oder resize Methoden von vector
Wie Sie sehen können, fügt VS zusätzlichen Platz mit kleineren Chunks hinzu, während G ++ i es mit den Potenzen von 2 tut. Dies sind nur Implementierungen derselben Grundidee: Je mehr Elemente Sie hinzufügen, desto mehr Speicherplatz wird zugewiesen Das nächste Mal (weil es wahrscheinlicher ist, dass Sie zusätzliche Daten hinzufügen).
Stellen Sie sich vor, Sie haben dem Vektor 1 Element hinzugefügt, und ich habe 1000 hinzugefügt. Es ist wahrscheinlicher, dass weitere 1000 hinzugefügt werden, und das ist weniger wahrscheinlich. Dies ist der Grund für eine solche Strategie der Raumzuteilung.
Die genauen Zahlen hängen sicher von etwas ab, aber das ist die Argumentation der Compiler-Hersteller, da sie sie beliebig implementieren können.
Der Standard definiert nur das Verhalten eines Vektors. Was wirklich intern passiert, hängt von der Implementierung ab. Die Verdoppelung der Kapazität führt zu einem amortisierten O (n) -Kosten für das Schieben / Herausspringen von n Elementen, was für einen Vektor erforderlich ist, denke ich. Schauen Sie hier für weitere Details.
Tags und Links c++ vector memory-management