Vektoren und reserve()

Jay1980

Servus,

mal schauen ob ich das richtig verstanden habe:

Vektoren sind dynamische Container, ich muss mir also selbst keine Sorgen machen, dass push_back() irgendwann ins Leere geht. Intern hat der Vektor aber sehr wohl eine capacity und wenn push_back() da ran kommt, dann erweitert sich der Vektor, das geht aber zu Lasten der Performance, denn da muss dann alles umkopiert werden, es macht also Sinn den Vektor schon vorab mit reserve() eine Richtlinie mitzugeben, wie viele Elemente sich wohl in den Vektor setzen werden.

In Java starten die Container mit einer Standardgröße von 30, wenn ich mich recht erinnere, wie ist die Standardkapazität in C++?

Lieg ich richtig, wenn ich rund 10 % mehr als erwartet reserviere, damit sicher nicht der 'Alles kopieren'-Fall eintritt, ich habe aber dadurch auch keine nennenswerten Nachteile?

Danke vorab.

314159265358979

Es kann passieren, dass dir der Speicher ausgeht.
Die Größe kannst du bereits im Konstruktor übergeben:

std::vector<T> v(30);

Es gibt keine festgelegte Standardgröße, das ist abhängig von der Implementierung.
Java ist scheiße. Die Container dort sind durch und durch inkonsistent.

Warum ist das für dich so wichtig? Man sollte zunächst programmieren und erst am Ende (mit einem Profiler!) nachschauen, wo es Optimierungspotential gibt.

krümelkacker

Jay1980 schrieb:

Vektoren sind dynamische Container, ich muss mir also selbst keine Sorgen machen, dass push_back() irgendwann ins Leere geht. Intern hat der Vektor aber sehr wohl eine capacity und wenn push_back() da ran kommt, dann erweitert sich der Vektor, das geht aber zu Lasten der Performance, denn da muss dann alles umkopiert werden,

Die Komplexität ist jedenfalls immer noch amortisiert linear in der Anzahl der Vektor-Elemente. Das wird dadurch erreicht, dass die Kapazität des Vektors nicht um eine konstante Zahl, sondern um einen gewissen Prozentsatz erhöht. Populär sind die Faktoren 2 und 1.5. libstdc++ (GCC) verdoppelt die Kapazität des Vektors meines Wissens nach. Wie es Microsoft implementiert hat, weiß ich nicht. Der C++ Standard garantiert aber eine amortisiert lineare Laufzeit.

Jay1980 schrieb:

es macht also Sinn den Vektor schon vorab mit reserve() eine Richtlinie mitzugeben, wie viele Elemente sich wohl in den Vektor setzen werden.

Das macht nud dann Sinn, wenn Du die exakte Größe schon vorher kennst. Wenn Du sie nicht exakt kennst, würde ich an Deiner Stelle auch die Finger von reserve lassen.

Jay1980 schrieb:

In Java starten die Container mit einer Standardgröße von 30, wenn ich mich recht erinnere, wie ist die Standardkapazität in C++?

Schreibt das der Sprachstandard vor? Gibt es überhaupt einen Java-Sprachstandard oder beschränkst Du Dich auf Sun's Implementierung? In der C++ Welt sind das zwei Paar Schuhe. Der ISO C++ Standard gibt Dinge vor und Compilerhersteller/StdLib-Entwickler müssen sich daran halten, haben hier aber auch ihre Freiheiten, zB bzgl Initialgröße und "Growth"-Faktor. Beim GCC fängt ein std::vector<T> meines Wissens nach wirklich mit nur einem Element an und die Größe wird dann immer verdoppelt. Zumindest, wenn ich mich richtig erinnere.

Jay1980 schrieb:

Lieg ich richtig, wenn ich rund 10 % mehr als erwartet reserviere, damit sicher nicht der 'Alles kopieren'-Fall eintritt, ich habe aber dadurch auch keine nennenswerten Nachteile?

Das kommt darauf an, wie gut Deine Schätzung ist und wie std::vector implementiert wurde. Wie gesagt, ich würde von reserve die Finger lassen, falls Du die Größe nicht exakt kennst.

kk

theta

Vektoren sind dynamische Container, ich muss mir also selbst keine Sorgen machen, dass push_back() irgendwann ins Leere geht.

Prinzipiell ja, ausser der Fall der 314159... erwähnt hat (punkt 1).

Intern hat der Vektor aber sehr wohl eine capacity und wenn push_back() da ran kommt, dann erweitert sich der Vektor

Ja.

das geht aber zu Lasten der Performance, denn da muss dann alles umkopiert werden

Prinzipiell ja, aber meistens spielt es gar keine Rolle. Benutze dazu einen Profiler o.ä. um herauszufinden ob und wo Du ein Performance Problem hast.

es macht also Sinn den Vektor schon vorab mit reserve() eine Richtlinie mitzugeben, wie viele Elemente sich wohl in den Vektor setzen werden.

Im Normalfall ist reserve() nicht nötig. Bei vielen Elementen kann es durchaus sinnvoll sein. Da hilft ausprobieren / messen. Die Kapazität wächst übrigens nicht linear - sondern tut sich z.B. immer verdoppeln.

In Java starten die Container mit einer Standardgröße von 30, wenn ich mich recht erinnere, wie ist die Standardkapazität in C++?

Meines Wissens ist nach dem Konstruieren capacity() == size(), allerdings weiss ich nicht ob das vom Standard her festgelegt ist.

Lieg ich richtig, wenn ich rund 10 % mehr als erwartet reserviere, damit sicher nicht der 'Alles kopieren'-Fall eintritt, ich habe aber dadurch auch keine nennenswerten Nachteile?

Ich denke nicht, dass das nötig ist, zumindest nicht in den allermeisten Fällen - der Nachteil wäre, dass Du einfach mehr (unnötigen) Code schreibst.

Simon

HighLigerBiMBam

Meines Wissens ist nach dem Konstruieren capacity() == size(), allerdings weiss ich nicht ob das vom Standard her festgelegt ist.

Definitiv nicht.

Notice that, in vectors, the capacity is not necessarily equal to the number of elements that conform the underlying vector content (this can be obtained with member vector::size), but the capacity of the actual allocated space, which is either equal or greater than the content size.

Belli

314159265358979 schrieb:

Die Größe kannst du bereits im Konstruktor übergeben:
std::vector<T> v(30);

Das ist aber was anderes, als mit reserve für eine bestimmte Anzahl von Vektorelementen vorauszuplanen.

Michael E.

HighLigerBiMBam schrieb:

Meines Wissens ist nach dem Konstruieren capacity() == size(), allerdings weiss ich nicht ob das vom Standard her festgelegt ist.

Definitiv nicht.

Notice that, in vectors, the capacity is not necessarily equal to the number of elements that conform the underlying vector content (this can be obtained with member vector::size), but the capacity of the actual allocated space, which is either equal or greater than the content size.

Und wo ist da jetzt das Argument, dass nach dem Konstruieren Ungleichheit gelten darf?

theta

Michael E. schrieb:

HighLigerBiMBam schrieb:

Meines Wissens ist nach dem Konstruieren capacity() == size(), allerdings weiss ich nicht ob das vom Standard her festgelegt ist.

Definitiv nicht.

Notice that, in vectors, the capacity is not necessarily equal to the number of elements that conform the underlying vector content (this can be obtained with member vector::size), but the capacity of the actual allocated space, which is either equal or greater than the content size.

Und wo ist da jetzt das Argument, dass nach dem Konstruieren Ungleichheit gelten darf?

Ich denke, das "Definitiv nicht" bezog sich auf die Aussage bezüglich des Standards - nicht bezüglich des Verhaltens.

Michael E.

theta schrieb:

Michael E. schrieb:

HighLigerBiMBam schrieb:

Meines Wissens ist nach dem Konstruieren capacity() == size(), allerdings weiss ich nicht ob das vom Standard her festgelegt ist.

Definitiv nicht.

Notice that, in vectors, the capacity is not necessarily equal to the number of elements that conform the underlying vector content (this can be obtained with member vector::size), but the capacity of the actual allocated space, which is either equal or greater than the content size.

Und wo ist da jetzt das Argument, dass nach dem Konstruieren Ungleichheit gelten darf?

Ich denke, das "Definitiv nicht" bezog sich auf die Aussage bezüglich des Standards - nicht bezüglich des Verhaltens.

Das denke ich auch. Trotzdem sehe ich kein Argument.

HighLigerBiMBam

Ja ich muss zugeben es war etwas wortkarg. Auch wenn sich vector nach dem konstruieren so verhalten sollte, wäre es gefährlich anzunehmen, dass capacity und size ein und das Selbe sind, bzw. man diese beliebig gegeneinander ersetzen könnte. Sicher können sie identisch sein, aber darauf würde ich mich nicht stützen.

Ich glaube auch nicht, dass diese Gleichheit im Standard definiert ist/sein sollte. Wenn es so ist, wäre ein Link hier sehr nützlich.

Michael E.

Ich denke auch nicht, dass nach dem Konstruieren eines std::vector (egal mit welchem Konstruktor) size == capacity garantiert ist. Allerdings kann man das nicht daraus herleiten, dass diese beiden Größen im Allgemeinen unterschiedlich sein dürfen. Deshalb hat mich dein "definitiv nicht" etwas gestört.

zeusosc

Michael E. schrieb:

Ich denke auch nicht, dass nach dem Konstruieren eines
std::vector (egal mit welchem Konstruktor) size == capacity garantiert ist.
Allerdings kann man das nicht daraus herleiten, dass diese beiden Größen im
Allgemeinen unterschiedlich sein dürfen. Deshalb hat mich dein "definitiv nicht"
etwas gestört.

Meines wissens nach sind capacity und size prinzipiell
unterschiedlich.
Capacität:
gibt die absolute anzahl der elemente an, die gespeichert werden können.
Size:
gibt die absolute anzahl der elemente an, die gespeichert worden sind.

Jetzt die frage:

Michael E schrieb:

[...]kann man das nicht daraus herleiten, dass diese beiden Größen im Allgemeinen unterschiedlich sein dürfen.

Mich würde arg wundern wenn diese nicht unterschiedlich wären.

Der Grund (wie in einem post weiter vorne schon gesagt) ist eine reallocation mit overhead,
damit nicht bei jedem push_back o.ä. ein realloc folgen muss, was performance
einbüßen würde.

grüüüße

HighLigerBiMBam

Sie sind nicht prinzipiell unterschiedlich. Es kann sein, das diese gleich sind und zwar dann, wenn die Kapazität gleich der Anzahl der Element ist (also der Vector für das nächste Element reallozieren müsste).

Belli

Genau - und deshalb sind sie prinzipiell unterschiedlich. Nicht immer und nicht in jedem Fall, aber prinzipiell schon.

Das hier:

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	vector<int> v;

	for(int i = 0; i < 10; v.push_back(++i))
		cout << "Kap.: " << v.capacity() << " Size: " << v.size() << '\n';
}

ergibt bei mir:

Kap.: 0 Size: 0
Kap.: 1 Size: 1
Kap.: 2 Size: 2
Kap.: 3 Size: 3
Kap.: 4 Size: 4
Kap.: 6 Size: 5
Kap.: 6 Size: 6
Kap.: 9 Size: 7
Kap.: 9 Size: 8
Kap.: 9 Size: 9

mit VS 2008 auf WinXP SP3 32bit.

Nein sie sind nicht prinzipiell gleich oder unterschiedlich. Auch nicht, bei einer Beschränkung auf den Standard-Allokator.