Kann in einem vector jemals eine Verringerung der Kapazität beim Löschen aller Elemente 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)

[hustbaer]

@camper
Mir ist klar was passiert.
Hier ging es aber glaube ich um die Frage was und vor allem wo der Standard das garantiert bzw. vorschreibt.

Gibt es eine Passage in der Beschreibung von vector::swap (oder sonstwo) die das wirklich klar sagt, oder ist es nur impliziert?

[Furble Wurble]

hustbaer schrieb:

Gibt es eine Passage in der Beschreibung von vector::swap (oder sonstwo) die das wirklich klar sagt, oder ist es nur impliziert?

Es steht explizit im Std., dass capacity() mitgetauscht wird. (kein Exemplar zur Hand... )
Etwas unterspezifiziert, bzw. ungenau finde ich jetzt, ob in campers Beispiel, die Eigenschaft "für diesen Vector wurde reserve() aufgerufen" "mitgeswapped" wird.

[Shade Of Mine]

hustbaer schrieb:

Gibt es eine Passage in der Beschreibung von vector::swap (oder sonstwo) die das wirklich klar sagt, oder ist es nur impliziert?

Der Standard verlangt, dass iteratoren gültig bleiben nur eben jetzt auf den anderen Container verweisen.

[hustbaer]

OK, das sollte dann reichen

[Furble Wurble]

hustbaer schrieb:

OK, das sollte dann reichen

Also sind wir uns einig, dass es die geforderte Garantie nicht gibt?
Diejenigen, die das Gegenteil behauptet haben sind schließlich einen Beweis schuldig geblieben.
Was fuer den Standard spricht: eine definitive Aussage in die eine oder andere Richtung wäre eine Einschränkung der Implementierung. (Speicher wird immer
freigebeben/nie freigegeben).

@pumuckl: Polemik ignoriert.