C++ Vektor Leistung mit vordefinierten Kapazität

Question

Es gibt 2 Möglichkeiten std zu definieren :: Vektor (die ich kenne):

std::vector<int> vectorOne; 

und

std::vector<int> vectorTwo(300); 

Also, wenn ich nicht definieren, die erste und füllen Sie es mit 300 int's, dann muss es Speicher neu zuweisen, um diese int zu speichern. das würde bedeuten, dass es zum Beispiel nicht die Adresse 0x0 bis 0x300 wäre, aber es könnte Speicher dazwischen zugewiesen werden, weil er danach neu zugewiesen werden muss, aber der zweite Vektor hat bereits diese Adressen für sie reserviert, so dass kein Zwischenraum dazwischen wäre.

Beeinflusst dies die Leistung überhaupt und wie könnte ich dies messen?

Answer 1

std::vector ist garantiert, seine Daten immer in einem kontinuierlichen Speicherblock zu speichern. Das bedeutet, dass beim Hinzufügen von Elementen versucht werden muss, den verfügbaren Speicherbereich zu vergrößern. Wenn etwas anderes im Speicher nach dem Vektor ist, muss es einen freien Block der richtigen Größe irgendwo anders im Speicher finden und alle alten Daten + die neuen Daten dorthin kopieren. Dies ist eine ziemlich teure Operation in Bezug auf die Zeit, also versucht es zu entschärfen, indem Sie einen etwas größeren Block zuweisen als Sie benötigen. Auf diese Weise können Sie mehrere Elemente hinzufügen, bevor die gesamte Reallocate-and-Move-Operation stattfindet.

Vektor hat zwei Eigenschaften: size und capacity. Der ehemalige ist wie viele Elemente es tatsächlich hält, letzteres ist, wie viele Plätze insgesamt reserviert sind. Wenn Sie beispielsweise einen Vektor mit size() == 10 und capacity() == 18 haben, bedeutet dies, dass Sie 8 weitere Elemente hinzufügen können, bevor Sie sie neu zuweisen müssen.

Wie und wann genau die Kapazität steigt, hängt vom Implementierer Ihrer STL-Version ab. Sie können testen, was mit dem folgenden Test auf Ihrem Computer passiert:

#include <iostream> 
#include <vector> 

int main() { 
    using std::cout; 
    using std::vector; 

    // Create a vector with values 1 .. 10 
    vector<int> v(10); 
    std::cout << "v has size " << v.size() << " and capacity " << v.capacity() << "\n"; 

    // Now add 90 values, and print the size and capacity after each insert 
    for(int i = 11; i <= 100; ++i) 
    { 
     v.push_back(i); 
     std::cout << "v has size " << v.size() << " and capacity " << v.capacity() 
      << ". Memory range: " << &v.front() << " -- " << &v.back() << "\n"; 
    } 

    return 0; 
} 

Ich lief es auf IDEOne und bekam die folgende Ausgabe:

v has size 10 and capacity 10 
v has size 11 and capacity 20. Memory range: 0x9899a40 -- 0x9899a68 
v has size 12 and capacity 20. Memory range: 0x9899a40 -- 0x9899a6c 
v has size 13 and capacity 20. Memory range: 0x9899a40 -- 0x9899a70 
... 
v has size 20 and capacity 20. Memory range: 0x9899a40 -- 0x9899a8c 
v has size 21 and capacity 40. Memory range: 0x9899a98 -- 0x9899ae8 
... 
v has size 40 and capacity 40. Memory range: 0x9899a98 -- 0x9899b34 
v has size 41 and capacity 80. Memory range: 0x9899b40 -- 0x9899be0 

Sie die Kapazitätssteigerung sehen und Umschichtungen genau dort passieren und Sie sehen auch, dass dieser spezielle Compiler die Kapazität jedes Mal verdoppelt, wenn Sie das Limit erreichen. Auf einigen Systemen wird der Algorithmus subtiler und wächst schneller, wenn Sie mehr Elemente einfügen (wenn also Ihr Vektor klein ist, verschwenden Sie wenig Platz, aber wenn er feststellt, dass Sie viele Elemente einfügen, werden mehr zugewiesen um zu vermeiden, dass die Kapazität zu oft erhöht werden muss).

PS: Beachten Sie den Unterschied zwischen dem Setzen des size und capacity eines Vektors.

vector<int> v(10); 

einen Vektor mit capacity mindestens 10, und size() == 10 erstellen. Wenn Sie die Inhalte von v drucken, werden Sie sehen, dass es

0 0 0 0 0 0 0 0 0 0 

heißt 10 ganze Zahlen mit ihren Standardwerten enthält. Das nächste Element, das Sie hineinschieben, könnte (und wahrscheinlich wird) eine Neuzuweisung verursachen. Auf der anderen Seite,

vector<int> v(); 
v.reserve(10); 

wird einen leer Vektor, aber mit seiner Anfangskapazität auf 10 statt dem Standard (wahrscheinlich 1) erstellen. Sie können sicher sein, dass die ersten 10 Elemente, die Sie hineinschieben, keine Zuweisung verursachen (und die wahrscheinlich wird aber nicht unbedingt, da reserve die Kapazität tatsächlich auf mehr als das, was Sie angefordert haben, setzen kann).

Answer 2

Sie sollten Reserve() -Methode verwenden:

std::vector<int> vec; 
vec.reserve(300); 
assert(vec.size() == 0); // But memory is allocated 

Dies löst das Problem.

In Ihrem Beispiel wirkt sich dies stark auf die Leistung aus. Sie können erwarten, dass beim Überlauf des Vektors der zugewiesene Speicher verdoppelt wird. Wenn Sie also push_back() in den Vektor N-mal drücken (und Sie haben "reserve()" nicht aufgerufen), können Sie O (logN) -Reallocations erwarten, von denen jede das Kopieren aller Werte verursacht. Daher wird erwartet, dass die Gesamtkomplexität O (N * logN) ist, obwohl sie nicht durch den C++ - Standard spezifiziert ist.

Answer 3

Die Unterschiede können dramatisch sein, denn wenn Daten nicht im Speicher benachbart sind, müssen die Daten möglicherweise aus dem Hauptspeicher abgerufen werden, was 200-mal langsamer als ein 1-Cache-Abruf ist. Dies wird in einem Vektor nicht vorkommen, da Daten in einem Vektor benachbart sein müssen.

siehe https://www.youtube.com/watch?v=YQs6IC-vgmo

Verwendung std :: vector :: Reserve, wenn Sie realloc Ereignisse zu vermeiden. Die C++ - Chrono-Kopfzeile verfügt über Zeitfunktionen, um den Zeitunterschied in hochauflösenden Ticks zu messen.