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

[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.

[hustbaer]

Furble Wurble schrieb:

hustbaer schrieb:

OK, das sollte dann reichen

Also sind wir uns einig, dass es die geforderte Garantie nicht gibt?

Weiss nicht.
Von welcher Garantie sprichst du jetzt genau?

[camper]

Furble Wurble schrieb:

Also sind wir uns einig, dass es die geforderte Garantie nicht gibt?

Ich geht mal davon aus, dass das nicht so gemeint ist, wie es dasteht...

Ein Blick sollte auch auf 1102. std::vector's reallocation policy still unclear [NAD] geworfen werden.

[Furble Wurble]

hustbaer schrieb:

Furble Wurble schrieb:

hustbaer schrieb:

OK, das sollte dann reichen

Also sind wir uns einig, dass es die geforderte Garantie nicht gibt?

Weiss nicht.
Von welcher Garantie sprichst du jetzt genau?

Moin!
Ich sprach von der Garantie, dass weder blei clear() noch bei resize(0) sich die capacity aendert, insbesondere verringert werden kann...

campers Link ist interessant. Leider ist die "complex argumentation chain about four different places in the standard", die den TE und mich überzeugen sollte nicht ausgeführt.
Allerdings gebe ich mich geschlagen - gegen ein Konsens im Standardkomitee will ich gar nicht argumentieren...