Kann in einem vector jemals eine Verringerung der Kapazität beim Löschen aller Elemente stattfinden?

[Athar]

Die Frage ist rein akademischer Natur, möchte ich trotzdem aber mal geklärt haben.
Folgender Code:

vector<int> vec;
vec.resize(10);
vec.resize(0);
vec.clear();

Meine Frage ist, ob es vom Standard garantiert ist, dass capacity() den gleichen Wert vor und nach resize(0) bzw. clear() zurückgibt.
Laut Standard verhält sich resize(0) wie erase(vec.begin(),vec.end()) . erase invalidiert keine Iteratoren vor den gelöschten Elementen - bis zu einem resize(1) müsste also garantiert sein, dass keine Reallokation stattfindet. Problematisch wird es bei resize(0) , denn da ohnehin alle Iteratoren invalidiert werden, kann ich gerade keinen Grund finden, der einer Implementation verbieten würde, die Kapazität in diesem Fall zu verringern. Bei clear() sowieso nicht.
Gibt es diesbezüglich noch Stellen im Standard, die ich nicht gesehen bzw. falsch interpretiert habe?

[SeppJ]

Der vector wird seine capacity bei diesen Aktionen nicht verringern. Um diesen Effekt zu erreichen:

Vor C++11:
vector<foo>(foovector).swap(foovector);

C++11:
shrink_to_fit()

[pumuckl]

Der Standard garantiert, dass die Capacity nie verringert wird, mit 1 bzw. 2 Ausnahmen:

1. swap() mit einem vector geringerer capacity (swap tauscht eben wirklich alles)
2. seit C++11 shrink_to_fit(), was genau das macht was der Name sagt: capacity auf die tatsächliche Größe zusammenschrumpfen.

Grund: Die Capacity zu reduzieren erfordert eine Neuallokation von Speicher sowie das Kopieren aller Elemente (falls der vector nicht ganz leer ist) sowie das Freigeben des bis dahin belegten Speichers. Da das auf jeden Fall mehr Zeit kostet als einfach bis zum Destruktor auf die Speicherfreigabe zu warten, muss das immer explizit funktionieren.

in C++98 kannst du shrink_to_fit simulieren, indem du den vector in einen temporären vector kopierst und im selben Atemzug mit ihm swapst:

std::vector<int> myvec;
//füllen, löschen,...

std::vector<int>(myvec).swap(myvec);

[Furble Wurble]

pumuckl schrieb:

Der Standard garantiert, dass die Capacity nie verringert wird, mit 1 bzw. 2 Ausnahmen:

Kannst Du mir bitte sagen, wo das steht?
Ich finde nur die Garantie, dass nach reserve(N) keine Neuallokation stattfindet bis size() > N . (Siehe C++11 23.3.6.3 vector capacity).

Athar schrieb:

Meine Frage ist, ob es vom Standard garantiert ist, dass capacity() den gleichen Wert vor und nach resize(0) bzw. clear() zurückgibt.

Bis man mich also mit der Nase daraufstößt, lautet meine Antwort: "Nein, das ist nicht garantiert. Aber sehr wahrscheinlich."

[SeppJ]

Furble Wurble schrieb:

pumuckl schrieb:

Der Standard garantiert, dass die Capacity nie verringert wird, mit 1 bzw. 2 Ausnahmen:

Kannst Du mir bitte sagen, wo das steht?
Ich finde nur die Garantie, dass nach reserve(N) keine Neuallokation stattfindet bis size() > N . (Siehe C++11 23.3.6.3 vector capacity).

Wenn anderswo nicht gesagt wird, dass eine Neuallokation stattfindet, dann darf auch keine Neuallokation stattfinden.

[pumuckl]

Furble Wurble schrieb:

Kannst Du mir bitte sagen, wo das steht?

Hauptsächlich in den Komplexitätsanforderungen der einzelnen Operationen sowie in den Anforderungen an Iteratorstabilität:
Wie gesagt müsste eine Reduzierung der Kapazität durch Deallokation und Neuallokation erfolgen, vor allem die (tendenziell sehr teure) Kopie der Elemente würde mit einen Komplexität von O(N) zu Buche schlagen, was nicht der Fall ist. Außerdem würde eine Reallokation mit Verschiebung aller Elemente sämtliche Iteratoren in den vector invalidieren.

- resize(sz) ist gleichbedeutend mit erase(begin()+sz, end()), falls sz < size() (§23.3.6.3)
- erase(a, b) Effekt: Invalidiert nur Iteratoren auf oder hinter die gelöschten Elemente. Komplexität: ruft den Destruktor von T nur so oft auf, wie Elemente gelöscht wurden (vor allem: keine Erwähnung von Speicherfreigabe)

Zusammen: resize(0) darf keinen Speicher freigeben.

Bei clear() habe ich grade eine Überraschung erlebt: der Standard (zumindest N3291) beschreibt für vector::clear erstaunlich wenig, vor Allem steht da tatsächlich nichts zu Deallokationen und Komplexität, was mir ehrlich gesagt nach einem Fehler im Standard vorkommt. Vielleicht habe ich den betreffenden Paragraphen aber auch übersehen. Typische Implementierungen setzen clear() allerdings gleich mit resize(0).

SeppJ schrieb:

Wenn anderswo nicht gesagt wird, dass eine Neuallokation stattfindet, dann darf auch keine Neuallokation stattfinden.

Jein. Wenn keine expliziten Komplexitätsanforderungen vorhanden sind (wie bei clear()), wäre eine Deallokation/Neuallokation in meinen Augen standardkonform (wenn auch unsinnig).

[krümelkacker]

shrink_to_fit ist ein "non-binding request to reduce capacity() to size(). [Note: The request is non-binding to allow latitude for implementation-specific optimizations. - end note]"

Also so richtig verlassen kann man sich da scheinbar auch nicht drauf.

[camper]

Furble Wurble schrieb:

pumuckl schrieb:

Der Standard garantiert, dass die Capacity nie verringert wird, mit 1 bzw. 2 Ausnahmen:

Kannst Du mir bitte sagen, wo das steht?
Ich finde nur die Garantie, dass nach reserve(N) keine Neuallokation stattfindet bis size() > N . (Siehe C++11 23.3.6.3 vector capacity).

Und das genügt.
capacity ändert sich nicht, es sei denn:
- eine Operation ändert sie ausdrücklich (reserve, shrink_to_fit), oder
- dies wird durch die Operation impliziert (einfügen bis size>capacity (da immer gilt capacity()>=size() ), swap, oder wenn der vector gemoved wird)

[pumuckl]

krümelkacker schrieb:

Also so richtig verlassen kann man sich da scheinbar auch nicht drauf.

Ist im Grunde das Selbe wie bei reserve(): resere(N) garantiert nur, dass capacity() >= N, nicht capacity() == N.

Konstruiertes Beispiel: Ich implementiere eine Standardbibliothek für ein System, auf dem Speicher nur in 8-byte-Blöcken angefordert werden kann. Eine capacity() von 4 oder 5 macht dann keinen Sinn. Einen vector mit ehemals 16 Elementen auf 9 Elemente zu resizen lässt und dann shrink_to_fitten hat beim shrink_to_fit keinen Effekt, die capacity() bleibt bei 16...

[Furble Wurble]

pumuckl schrieb:

Hauptsächlich in den Komplexitätsanforderungen der einzelnen Operationen sowie in den Anforderungen an Iteratorstabilität:

Du meinst:

C++11 schrieb:

23.2.1 General container requirements
[...]
11 Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

Sowohl erase() als auch clear() invalidieren allerdings (alle) Iteratoren.

pumuckl schrieb:

Wie gesagt müsste eine Reduzierung der Kapazität durch Deallokation und Neuallokation erfolgen, vor allem die (tendenziell sehr teure) Kopie der Elemente würde mit einen Komplexität von O(N) zu Buche schlagen, was nicht der Fall ist. Außerdem würde eine Reallokation mit Verschiebung aller Elemente sämtliche Iteratoren in den vector invalidieren.

- resize(sz) ist gleichbedeutend mit erase(begin()+sz, end()), falls sz < size() (§23.3.6.3)
- erase(a, b) Effekt: Invalidiert nur Iteratoren auf oder hinter die gelöschten Elemente. Komplexität: ruft den Destruktor von T nur so oft auf, wie Elemente gelöscht wurden (vor allem: keine Erwähnung von Speicherfreigabe)

Zusammen: resize(0) darf keinen Speicher freigeben.

Zur Erinnerung: im OP war die Frage nach capacity an zwei Stellen, wo der Vektor keinen Speicher mehr für die Nutzdaten benötigt, weil size()==0 .

vector<int> vec;
vec.resize(10);
const auto cap = vec.capacity(); // 9 < cap
vec.resize(0);  // Vektor leer, D'tor fuer alle aufgerufen, alle(!) Iteratoren invalide
assert(cap == vec.capacity());
vec.clear(); // dto.
assert(cap == vec.capacity());

Der TE hat - wie ich auch - das Problem jetzt irgendeinen Hinweis dafür zu finden, dass nachdem eh alle Iteratoren, Referenzen und Pointer ungültig sind eine Implementierung garantiert die Kapazität beibehält...

Athar schrieb:

[...]
Problematisch wird es bei resize(0) , denn da ohnehin alle Iteratoren invalidiert werden, kann ich gerade keinen Grund finden, der einer Implementation verbieten würde, die Kapazität in diesem Fall zu verringern. Bei clear() sowieso nicht.
Gibt es diesbezüglich noch Stellen im Standard, die ich nicht gesehen bzw. falsch interpretiert habe?

@SeppJ: Kann sein, dass Du recht hast. Und keine Implementierung wird es wohl anders machen, aber da es eine "akademische Frage" ist kann man schon noch ein wenig Standard lesen und diskutieren.

[pumuckl]

camper schrieb:

Furble Wurble schrieb:

Ich finde nur die Garantie, dass nach reserve(N) keine Neuallokation stattfindet bis size() > N . (Siehe C++11 23.3.6.3 vector capacity).

Und das genügt.

Stimmt, einfaches Beispiel:

vector<int> vec;
vec.reserve(12); //N = 12
vec.resize(10);  //size < N
vec.resize(0);   //size < N, a)
vec.clear();     //size < N, b)
vec.resize(11);  //size < N, c)

Wenn a) oder b) hier Kapazität freigegeben hätten, müsste bei c) eine Neuallokation stattfinden => darf nicht sein.

[Athar]

pumuckl schrieb:

Wenn a) oder b) hier Kapazität freigegeben hätten, müsste bei c) eine Neuallokation stattfinden => darf nicht sein.

In der Tat, mit reserve() ist das garantiert. Aber was passiert, wenn du reserve weglässt?
Der vector könnte sich merken, ob reserve aufgerufen wurde oder nicht - falls nicht, dann wäre er nicht mehr an diese Anforderung gebunden.

Mir fehlt da im Standard eine klare Aussage, zum Beispiel ein Hinweis darauf, dass Reallokation nur dann stattfinden darf, wenn es explizit erwähnt wird.

[Michael E.]

pumuckl schrieb:

Die Capacity zu reduzieren erfordert eine Neuallokation von Speicher

Warum?

[pumuckl]

Athar schrieb:

Der vector könnte sich merken, ob reserve aufgerufen wurde oder nicht - falls nicht, dann wäre er nicht mehr an diese Anforderung gebunden.

Ah, also 1) zusätzlichen Platz verbraten, um sich den reserve zu merken, und 2) zusätzliche Zeit verbraten, um zu schauen, was das reserve-Flag sagt und ggf. noch mehr Zeit verbraten, um den Speicher freizugeben, weil der Standard es ja nicht verbietet.

Ja, das dürfte der vector durchaus machen.

Er dürfte auch alle Primzahlen < 2^18 berechnen bei jeder Operation. Wäre zwar lahm, aber nicht abhängig von der Größe, also O(1), durchaus erlaubt. Und hey, er könnte ich rein theoretisch noch ein paar Flags speichern, z.B. im Ctor das Betriebssystem fragen, ob vielleicht eine Webcam angeschlossen ist. Könnte ja sein. Ist ja nicht verboten...

Wie abstrus darf es werden?

[pumuckl]

Michael E. schrieb:

pumuckl schrieb:

Die Capacity zu reduzieren erfordert eine Neuallokation von Speicher

Warum?

Ok, ungenau ausgedrückt.

Die Capacity auf einen Wert != 0 zu reduzieren erfordert eine Neuallokation von Speicher.

[Athar]

pumuckl schrieb:

Wie abstrus darf es werden?

Beliebig. Es ist eigentlich klar, dass das kaum ein vernünftiger Mensch so implementieren würde - wobei die Vorstellung, dass ein vector den Speicher bei einem clear() komplett freigibt, nicht völlig abstrus ist - viele Anfänger rechnen sogar damit. Im Prinzip geht es nur darum, ob man einen konformierenden vector bauen kann, der das tut.

[camper]

pumuckl schrieb:

Die Capacity auf einen Wert != 0 zu reduzieren erfordert eine Neuallokation von Speicher.

Es sei denn, der vector kann einige Elemente selbst enthalten (small-string-Optimierung).

Edit: stellt ein paar zusätzliche Bedingungen an die Elemente (noexcept-move), sonst gibts Probleme beim swap.

[Michael E.]

pumuckl schrieb:

Ok, ungenau ausgedrückt.

Die Capacity auf einen Wert != 0 zu reduzieren erfordert eine Neuallokation von Speicher.

Darum gings mir jetzt gar nicht. Woraus folgt denn, dass neuer Speicher allokiert werden muss? Die Laufzeitumgebung könnte auch*, wenn die erste Hälfte des allozierten Speichers für den vector ausreicht, in die zweite Hälfte ein anderes Objekt speichern. Somit ist die Kapazität gesunken, aber es wurde kein neuer Speicher alloziert.

*: Keine Ahnung, ob sie es kann und ob es erlaubt ist. Deshalb frage ich ja.

[hustbaer]

pumuckl schrieb:

camper schrieb:

Furble Wurble schrieb:

Ich finde nur die Garantie, dass nach reserve(N) keine Neuallokation stattfindet bis size() > N . (Siehe C++11 23.3.6.3 vector capacity).

Und das genügt.

Stimmt, einfaches Beispiel:

vector<int> vec;
vec.reserve(12); //N = 12
vec.resize(10);  //size < N
vec.resize(0);   //size < N, a)
vec.clear();     //size < N, b)
vec.resize(11);  //size < N, c)

Wenn a) oder b) hier Kapazität freigegeben hätten, müsste bei c) eine Neuallokation stattfinden => darf nicht sein.

Die Argumentation würde doch genau so gut für vector<int>().swap(vec) funktionieren, und das implementieren wohl alle (sinnvollerweise) so, dass vec danach capacity() == 0 (bzw. capacity() == smallConstantValue , bei SSO).

[camper]

hustbaer schrieb:

pumuckl schrieb:

camper schrieb:

Furble Wurble schrieb:

Ich finde nur die Garantie, dass nach reserve(N) keine Neuallokation stattfindet bis size() > N . (Siehe C++11 23.3.6.3 vector capacity).

Und das genügt.

Stimmt, einfaches Beispiel:

vector<int> vec;
vec.reserve(12); //N = 12
vec.resize(10);  //size < N
vec.resize(0);   //size < N, a)
vec.clear();     //size < N, b)
vec.resize(11);  //size < N, c)

Wenn a) oder b) hier Kapazität freigegeben hätten, müsste bei c) eine Neuallokation stattfinden => darf nicht sein.

Die Argumentation würde doch genau so gut für vector<int>().swap(vec) funktionieren, und das implementieren wohl alle (sinnvollerweise) so, dass vec danach capacity() == 0 (bzw. capacity() == smallConstantValue , bei SSO).

swap vertauscht die Resourcen der beiden Container. In diesem Fall ist die Änderung von capacity durch die Operation impliziert, bzw. es ist garantiert dass der reservierte Speicher im anderen Container weiterlebt.

vector<int> vec, vec2;
vec.reserve(12); //N = 12
vec.resize(10);  //size < N
vec.swap(vec2);
vec2.resize(0);   //size < N, a)
vec2.clear();     //size < N, b)
vec2.resize(11);  //size < N, c)