c++.de :: Kann in einem vector jemals eine Verringerung der Kapazität beim Löschen aller Elemente stattfinden?

pumuckl Moderator 11:50:05 26.07.2012 Titel:

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:

C++:
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 Mitglied 13:04:34 26.07.2012 Titel:

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. Mitglied 13:11:53 26.07.2012 Titel:

pumuckl schrieb:

Die Capacity zu reduzieren erfordert eine Neuallokation von Speicher

Warum?

pumuckl Moderator 13:13:38 26.07.2012 Titel:

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 Moderator 13:16:29 26.07.2012 Titel:

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 Mitglied 13:22:19 26.07.2012 Titel:

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 Mitglied 16:38:47 26.07.2012 Titel:

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. Mitglied 16:39:19 26.07.2012 Titel:

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 Mitglied 16:42:31 26.07.2012 Titel:

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:

C++:
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 Mitglied 16:45:06 26.07.2012 Titel:

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:

C++:
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.

C++:
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)