Vectoren

milo51

Naja ok, aber legt der Vector immer so viel Speicherplatz als reserve zurück?
Was passiert denn, wenn auch dieser Speicherbereich überschritten wird?

davie

dann werden alle iteratoren invalidiert und der gesamte inhalt des vectors in einen anderen, größeren speicherbereich kopiert. (wie schon gesagt)

Vellas

Setz dich mal mit dynamischer Speicherallokation und damit häufig verbunden dynamischen Datenstrukturen auseinander, vielleicht kommt dann das Verständnis dafür.

Dynamisch heißt das zur Laufzeit Speicherplatz vom System angefordert wird, das Programm bekommt dabei eine Adresse an der es dann Daten speichern kann. Da kann nichts liegen. Wenn dort was liegen würde, würde dein Programm vermutlich abstürzen.
Um in Speicherbereiche reinzukommen in denen du nichts zu suchen hast müsstest du Beispielsweise in ein Array mehr Werte reinpacken als du darfst.

Vellas

@davie:
Stimmt, wenn ich meinen (ersten) Post so lese, widerspreche ich mir ja auch selbst in meiner Erklärung und meiner Aussage, mit dem Vergrößern durch push_back.
Ich dachte nur er tut es nicht, wenn die Anzahl Elemente die er aufnehmen kann festgelegt wird, aber scheint nicht der Fall zu sein (zumindest gabs keine Probleme als ich das eben mit dem g++ getestet habe). Wenn die nicht angegeben ist, ist ja klar das er es tun muss, wenn man nur beispielsweise 7 Elemente als Default hat am Anfang, wäre das ja bissl wenig meist. *g*

PS: Kenne den Standard eigentlich, aber habe zu wenig Zeit C++ zu proggen seit paar Monaten, da ich kurz vor meinen Prüfungen stehe und mit anderen Sprachen arbeiten muss -.-.

Vellas schrieb:

Laufzeit Speicherplatz vom System angefordert

Ein Prozess fordert immer erst zur Laufzeit seinen Speichern an...

Vellas

Ja, nur kann bei Freispeicheroperationen (new, delete) die Menge bzw. Größe des benötigten Speicherplatzes variabel sein und ist nicht konstant im Programm festgelegt. (Hoffe es ist so klarer was ich meine.)

tntnet

Moin auch,

eine kleine Zusammenfassung: push_back vergrössert den std::vektor immer. Ob er dazu Speicher allokieren soll oder nicht, ist transparent. Den normalen Anwendungsprogrammierer muß es nicht interessieren.

Es gibt 2 Größen im std::vector: die size und die capacity. Die size gibt die aktuelle (logische) Größe des Vektors an. Die capacity gibt die reale Größe an. Die capacity ist immer mindestens so groß wie die size. Die Methode push_back vergrössert die size. Ist die capacity for der Operation gleich groß, wie die size, legt std::vector einen neuen grösseren Speicherbereich an und kopiert die Elemente in diesen. Der alte Speicherbereich wird frei gegeben. Ob die capacity jetzt grösser ist als die size, der Vektor also auf Vorrat Speicher reserviert hat, oder genau so groß wie die size ist, ist implementierungsspezifisch.

Wenn Du mehrere Elemente hinzufügen willst, kannst Du mit reserve dem Vektor anweisen, eine Mindestcapacity zu garantieren. Dadurch werden unnötige Kopieroperationen vermieden.

Im Konstruktor kann übrigens eine initiale Größe, also size angegeben werden. Rufe ich anschliessend push_back auf, wächst der Vektor weiterhin.

Probiere doch einfach mal folgendes Programm aus:

#include <vector>
#include <iostream>

template <typename T>
void info(const std::vector<T>& v)
{
  std::cout << "size=" << v.size() << " capacity=" << v.capacity() << std::endl;
}

int main()
{
  std::vector<int> v1; // vektor ist 0 Elemente groß
  info(v1);
  v1.push_back(5);     // vektor ist jetzt 1 Element groß
  info(v1);

  std::vector<int> v2(3); // vektor ist 3 Elemente groß
  info(v2);
  v2.push_back(5); // vektor ist jetzt 4 Elemente groß!!!
  info(v2);
}

Tommi

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main()
{
	vector<int> foo;
	int capacity;
	for(int i=0; i<10; ++i)
	{
		capacity = foo.capacity();
		cout << "Kapazit\x84t " << setw(2) << (i+1) << ": " << setw(3) << capacity << endl;
		while(foo.size() <= capacity)
			foo.push_back(0);
	}

	cin.get();
}

davie

tntnet schrieb:

eine kleine Zusammenfassung: push_back vergrössert den std::vektor immer. Ob er dazu Speicher allokieren soll oder nicht, ist transparent. Den normalen Anwendungsprogrammierer muß es nicht interessieren.

naja, was vielleicht noch erwähnenswert ist: bei einer vergrößerung von capacity (indirekt über push_back oder direkt über reserve) werden alle zeiger, referenzen und iteratoren auf die elemente des vektors ungültig. das geschieht auch nur (hier) bei erfolgter reallokation und es kann vorkommen, dass ein reserve(new_capacity) capacity auch gar nicht verändert, nämlich dann, wenn new_capacity <= capacity ist. die neue capacity muss auch nicht gleich new_capacity sein, sondern lediglich mindestens so groß. außerdem arbeitet der vektor intern mit rohen speicher, d.h. auf ein element hinter vector[size] zuzugreifen, obwohl es noch innerhalb der capacity wäre, ist auch eine schlechte idee.

Braunstein

Hallo,

Nur als Anmerkung:
Bei den zwei mir bekannte Portierungen (Rouge Wave, STLPort) wird bei notendigen Kopieraktionen, der Speicherbereich jeweils um den Faktor 2 erhöht,

tntnet

@schorsch code: was soll uns dieser Code zeigen? Ein Kommentar wäre hilfreich.

Ich werde das mal ergänzen: der Code zeigt das implementierungspezifische Verhalten von push_back. Es wäre interessant zu sehen, was das Programm mit unterschiedlichen Implementierungen der Stl ausgibt. Gcc 3.3.5 und 4.0.2 liefern:

Kapazitt 1: 0
Kapazitt 2: 1
Kapazitt 3: 2
Kapazitt 4: 4
Kapazitt 5: 8
Kapazitt 6: 16
Kapazitt 7: 32
Kapazitt 8: 64
Kapazitt 9: 128
Kapazitt 10: 256

@tntnet: Wie du schon sagst. Er soll was über das implementierungspezifische Verhalten aussagen. Und zwar darüber, wie die Kapazität am Anfang ist und was passiert, wenn sie überschritten wird. Entschuldigung. Dachte das wäre klar.

@tntnet: Wie du schon sagst. Er soll was über das implementierungspezifische Verhalten aussagen. Und zwar darüber, wie die Kapazität am Anfang ist und was passiert, wenn sie um 1 überschritten wird. Entschuldigung. Dachte das wäre klar.

ups