Anfangskapazität des Vektors in C++

Die Speicherimplementierungen von std :: vector variieren erheblich, aber alle, die mir begegnet sind, beginnen mit 0.

Der folgende Code:

#include <iostream>
#include <vector>

int main()
{
  using namespace std;

  vector<int> normal;
  cout << normal.capacity() << endl;

  for (unsigned int loop = 0; loop != 10; ++loop)
  {
      normal.Push_back(1);
      cout << normal.capacity() << endl;
  }

  std::cin.get();
  return 0;
}

Gibt die folgende Ausgabe aus:

0
1
2
4
4
8
8
8
8
16
16

unter GCC 5.1 und:

0
1
2
3
4
6
6
9
9
9
13

unter MSVC 2013.

Als geringfügige Ergänzung zu den anderen Antworten habe ich festgestellt, dass beim Ausführen von Debug-Bedingungen mit Visual Studio ein standardmäßig konstruierter Vektor auf dem Heap immer noch zugewiesen wird, obwohl die Kapazität bei null beginnt.

Insbesondere wenn _ITERATOR_DEBUG_LEVEL! = 0, weist vector etwas Speicherplatz für die Iteratorprüfung zu.

https://docs.Microsoft.com/de-de/cpp/standard-library/iterator-debug-level

Ich fand das nur etwas nervig, da ich damals einen benutzerdefinierten Verteiler verwendete und die zusätzliche Zuteilung nicht erwartete.

Soweit ich den Standard verstanden habe (obwohl ich eigentlich keine Referenz nennen konnte), wurden die Instanzierung von Containern und die Speicherzuweisung aus gutem Grund absichtlich entkoppelt. Dafür haben Sie unterschiedliche, getrennte Aufrufe für

• constructor, um den Container selbst zu erstellen
• reserve(), um einen entsprechend großen Speicherblock vorab zuzuordnen, um mindestens (!) eine gegebene Anzahl von Objekten aufzunehmen

Und das macht sehr viel Sinn. Das einzige Recht, für reserve() zu existieren, besteht darin, Ihnen die Möglichkeit zu geben, möglicherweise kostenintensive Neuzuordnungen zu programmieren, wenn Sie den Vektor wachsen lassen. Um nützlich zu sein, müssen Sie die Anzahl der zu speichernden Objekte kennen oder zumindest eine fundierte Vermutung erstellen können. Wenn dies nicht gegeben ist, halten Sie sich besser von reserve() fern, da Sie lediglich die Neuzuweisung für nicht benötigten Speicherplatz ändern.

Also alles zusammen:

• Der Standard legt absichtlichnoteinen Konstruktor fest, mit dem Sie einen Speicherblock für eine bestimmte Anzahl von Objekten vorbelegen können (was zumindest wünschenswerter ist als das Zuordnen einer implementierungsspezifischen, festen "etwas" unter "Etwas") die Haube).
• Die Zuteilung sollte nicht implizit sein. Um einen Block vorab zuzuordnen, müssen Sie reserve() separat aufrufen, und dies muss sich nicht an derselben Baustelle befinden (könnte/sollte natürlich später sein, nachdem Sie die erforderliche Größe erkannt haben).
• Wenn also ein Vektor immer einen Speicherblock mit definierter Größe der Implementierung vorbelegen würde, würde dies die beabsichtigte Aufgabe von reserve() vereiteln, nicht wahr?
• Was wäre der Vorteil einer Vorabzuordnung eines Blocks, wenn die STL den beabsichtigten Zweck und die erwartete Größe eines Vektors naturgemäß nicht kennen kann? Es wäre ziemlich unsinnig, wenn nicht kontraproduktiv.
• Die richtige Lösung ist stattdessen die Zuweisung und Implementierung eines spezifischen Blocks mit der ersten Push_back() - falls dies nicht bereits zuvor von reserve() explizit zugewiesen wurde.
• Im Falle einer notwendigen Neuzuteilung ist auch die Zunahme der Blockgröße implementierungsspezifisch. Die mir bekannten Vektorimplementierungen beginnen mit einer exponentiellen Zunahme der Größe, beschränken jedoch die Inkrementierungsrate auf ein bestimmtes Maximum, um zu vermeiden, dass große Speichermengen verschwendet werden oder gar Speicherplatz erzeugt wird.

All dies kommt nur dann zum vollen Betrieb und zum Vorteil, wenn es nicht durch einen zuweisenden Konstruktor gestört wird. Sie haben angemessene Standardwerte für allgemeine Szenarien, die bei Bedarf von reserve() (und shrink_to_fit()) überschrieben werden können. Selbst wenn der Standard dies nicht ausdrücklich angibt, bin ich mir ziemlich sicher, dass ein neu konstruierter Vektor keine Vorbelegung darstellt, eine recht sichere Sache für alle aktuellen Implementierungen ist.

Standard gibt keinen Anfangswert für die Kapazität an, aber der STL-Container nimmt automatisch so viele Daten auf, wie Sie eingegeben haben, vorausgesetzt, Sie überschreiten nicht die maximale Größe (verwenden Sie die max_size-Memberfunktion, um zu wissen) wird von realloc gehandhabt, wenn mehr Speicherplatz benötigt wird. Angenommen, Sie möchten einen Vektor mit dem Wert 1-1000 erstellen. Ohne die Verwendung von Reserve führt der Code in der folgenden Schleife normalerweise zu zwischen 2 und 18 Neuzuweisungen:

vector<int> v;
for ( int i = 1; i <= 1000; i++) v.Push_back(i);

Wenn Sie den Code für die Verwendung von reserve ändern, werden während der Schleife möglicherweise 0 Zuordnungen vorgenommen:

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

for ( int i = 1; i <= 1000; i++) v.Push_back(i);

Grob gesagt: Die Kapazität von Vektoren und Strings wächst jedes Mal um einen Faktor zwischen 1,5 und 2.