Std :: Vektor Größe nach unten verkleinern

Question

Der C++ Standard scheint keine Aussage über Nebenwirkungen auf die Kapazität durch resize(n), mit n < size() oder clear() zu treffen.

Es macht eine Aussage über fortgeführte Anschaffungskosten push_back und pop_back machen - O (1)

kann ich eine Implementierung vorstellen, die die übliche Art von Kapazität ändert tut ala CLRS Algorithmen (zB Doppel beim Vergrößern, halbieren, wenn abnehmend size to < capacity()/4). (Cormen Lieserson Rivest Stein)

Hat jemand eine Referenz für Implementierungseinschränkungen?

Answer 1

Der Aufruf resize() mit einer kleineren Größe hat keinen Einfluss auf die Kapazität eines vector. Es wird keinen Speicher freigeben.

Der Standard Idiom für Speicher von einem vector befreit ist swap() es mit einer leeren temporären vector: std::vector<T>().swap(vec);. Wenn Sie die Größe nach unten ändern möchten, müssen Sie von Ihrem ursprünglichen Vektor in einen neuen lokalen temporären Vektor kopieren und dann den resultierenden Vektor mit Ihrem Original austauschen.

Aktualisiert: C++ 11 hinzugefügt, um eine Memberfunktion shrink_to_fit() für diesen Zweck, es ist eine unverbindliche Anfrage capacity()-size() zu reduzieren.

Answer 2

Eigentlich funktioniert der Standard festlegen, was passieren soll:

Dies ist von vector, aber das Thema ist das gleiche für alle Behälter (list, deque, etc ...)

23,2 .4.2 Vektor capacity [lib.vector.capacity]

void resize(size_type sz, T c = T());

6) Effekte:

if (sz > size()) 
    insert(end(), sz-size(), c); 
else if (sz < size()) 
    erase(begin()+sz, end()); 
else 
    ; //do nothing 

Das heißt: weniger Wenn die Größe ist als die Anzahl der Elemente zu resize angegeben, werden diese Elemente aus dem Container gelöscht werden. Bezüglich capacity() hängt das davon ab, was erase() tut.

ich es in der Norm nicht finden können, aber ich bin mir ziemlich sicher, dass clear() sein definiert:

void clear() 
{ 
    erase(begin(), end()); 
} 

Daher sind die Auswirkungen clear() auf capacity() hat sich auch auf die Auswirkungen gebunden erase() auf sie. Nach dem Standard:

23.2.4.3 vektor modifiers [lib.vector.Modifikatoren]

iterator erase(iterator position); 
iterator erase(iterator first, iterator last); 

4) Komplexität: Der Destruktor von T die Anzahl der Male gleich der Anzahl der gelöschten Elemente genannt ....

Dies bedeutet, dass die Elemente wird zerstört, aber die Erinnerung bleibt erhalten. erase() hat keinen Einfluss auf die Kapazität, daher haben resize() und clear() auch keine Wirkung.

Answer 3

Die Kapazität wird niemals abnehmen. Ich bin mir nicht sicher, ob der Standard dies explizit angibt, aber es ist impliziert: Iteratoren und Verweise auf Vektorelemente dürfen nicht durch resize(n) if n < capacity() ungültig gemacht werden.

Answer 4

Als ich nach gcc (mingw) guckte, ist der einzige Weg, die Vektorkapazität freizusetzen, was mattnewport sagt. Swaping es mit anderen temporären Vektor. Dieser Code macht es für gcc.