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

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?

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

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.

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