C++ Array von Objekten dynamisch erweitern

[Gluehwurm]

Ich weiss jetzt nicht, ob ich dich richtig verstanden habe, aber intern unterscheidet sich der stl-vector nicht viel von einem *normalen* array (=Pointer auf allokierten Speicher).
Aber: Intern wird zwischen size (enthaltene Elemente) und capacity (allokierter Speicher) unterschieden. Das wird gemacht, damit z.b. nicht bei jedem push_back() neuer Speicher allokiert werden und die alten Elemente kopiert werden müssen.
Deswegen wundert es mich auch, warum in diesem Thread noch nicht erwähnt wurde, dass der Vector am Anfang auf eine angemessene Kapazität gesetzt werden sollte. Es ist natürlich kein Fehler wenn man das nicht berücksichtigt, aber die Performanz kann dadurch schon deutlich leiden. Für Probleme mit dynamischer Größe gibt es bessere Datenstrukturen...

 

[ActiveO2]

also wird automatisch ein bestimmter bereich des Speichers "reserviert" für weitere Elemente?
Und angenommen der Bereich wird zu klein, wird nach einer neuen Speicherstelle gesucht in der alle Elemente der Reihe nach hineinpassen?
*confused*

hab das gerade mal "getestet"

#include "stdafx.h"

#include <iostream>
#include <vector>

using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	int a;
	vector<int> v_a;
	int b;

	for(int i = 0; i<50 ; i++)
	{
		v_a.push_back(i);

		cout << &v_a[i] << endl;
	}
	cout << &a<< endl << &v_a <<endl << &b << endl;

	system("PAUSE");
	return 0;
}

Ausgabe:
Speicheradressen der Vektor-Elemente: 0036C308 bis 0036C8F4
danach:
a-Adr.: 0012FF54
v_a-Adr.: 0012FF38
b-Adr.: 0012FF2C

 

[badday]

Ich muss leider sagen, das ganze nicht zu verstehen (also das was du sagen willst).
Ich fürchte, dass ich da nicht ganz allein bin.

Was genau meinst du mit:
bestimmter bereich
weitere Elemente
Bereich wird zu klein
neuen Speicherstelle er Reihe nach hineinpassen

*also confused*

Gruß,

badday


//Der Beitrag oben war vor der Änderung von ActiveO2


Du meinst also wie es sich bei den "internen" Speicheradressen der Objekte verhält?

Gruß,

badday

 

[Gluehwurm]

also wird automatisch ein bestimmter bereich des Speichers "reserviert" für weitere Elemente?

Genau. Einstellen und abfragen kann man das über die Methoden reserve() bzw. capacity().

Und angenommen der Bereich wird zu klein, wird nach einer neuen Speicherstelle gesucht in der alle Elemente der Reihe nach hineinpassen?

Nein. Es wird ein neuer Bereich im Speicher mit der passenden Größe angefordert. Da diese neue Speicherstelle i.A. ganz wo anders liegt, müssen alle alten Elemente des Arrarys in diesen neuen Speicherbreich kopiert werden. Der alte Speicherbereich wird dann natürlich freigegeben.Das Anfordern von neuem Speicher und das Kopieren ist eine relativ aufwändige Sache, und sollte deshalb wo es geht vermieden werden. Genau deswegen wird auch vom STL-Vector Speicher vorgehalten oder reserviert, auch wenn er im Moment gar nicht gebraucht wird.

 

[7H3 N4C3R]

@Glühwurm:
Das ist aber kein Fehler vom std::vector, sondern sein Design: Ein zusammenhängendes Stück Speicher wird garantiert. Kopieren ist einer der fundamentalsten Bausteine von C++ und den setzt die STL konsequent um. Für schnelle Kopien sollten daher der gespeicherte Typ T z.B. über eine effiziente swap-Implementiertung verfügen. Damit sind Kopien kaum noch teuer (genauer gesagt: Vertauschungen. Da bei einer internen Vergrößerung der alte Vektor-Inhalt weggeworfen wird, kann man aber den Standardkonstruktor bemühen und dann swappen).

Davon abgesehen geschieht das Vergrößern von Vektoren in amortisiert konstanter Zeit, da er immer um den Faktor 2 wächst. Daher ist das Anfügen an Vektoren erstmal unproblematisch. Kennt man die Anzahl an Elementen schon vorher, so kann und sollte man natürlich direkt reserve bemühen oder einen der Iterator-Konstruktoren bemühen.

Braucht man den zusammenhängenden Block Speicher nicht, den std::vector garantiert und erscheint einem das Umkopieren für den eigenen, spezifischen Anwendungsfall zu unperformant (Optimum: diese Ineffizient wird mit einem Profiler als #1 Performanceproblem gemessen), so gibt es genug andere Standardcontainer mit ihren spezifischen Vorzügen und Nachteilen.

 

[Gluehwurm]

Naja, ich hab ja nie gesagt, dass das ein Fehler des Vectors ist. Auch das mit dem exponentiellen Wachstum ist mir bewusst, ich wollte eben nur mal auf die Problematik hinweisen, da es eben andere Standardcontainer auch noch gibt.

Damit sind Kopien kaum noch teuer

Auch Kleinvieh macht Mist

 

[ActiveO2]

danke 7H3 N4C3R und Gluehwurm, darauf wollte ich hinaus

 

[Erdmännchen]

Ich versteh aber jetzt nicht, warum ihr da die Lösung über Vector geht...

ist doch auch ganz einfach so zu lösen:

	int size;
	cout << "Größe des Feldes eingeben: \n";
	cin >> size;
	
	int *feld = new int[size];        //Erzeuge ein Feld mit der Größe size vom Typ Integer

Danach kannst du den Speicher wieder freigeben über

delete[]  feld

Beim TE wäre halt [int] durch [telefonat] zu ersetzen...

 

[badday]

Warum bitte sollte man Arrays nutzen?

 

[ph4nt0m]

@Erdmenchenj: Weil in diesem speziellen Fall die Größe des Arrays selbst zur Laufzeit nicht bestimmt werden kann (sonst wäre deine Lösung durchaus gut). Muuhmann will während der Laufzeit stattdessen nach und nach beliebig Elemente hinzufügen, sodass die endgültig notwendige Array-Größe zu keinem Zeitpunkt genau definiert ist, sondern variabel wächst. Und dafür ist ein Container wie ein std::vector oder std::list nun einmal wesentlich besser geeignet.

 

[Erdmännchen]

danke ph4nt0m, das hab ich wohl übersehen mit dem dynamisch auch noch zur laufzeit...

wobei doch auch das kein problem wäre, wenn man dann das array jedesmal neu aufzieht?

In der Tat bleibt dann wohl die Vector-Lösung als "am handlichsten" über, wenn man nicht selbst ne verkettete Liste aufziehen möchte...