C-Array Dynamisch halten

[Valerio]

Hallo an alle!

Studiere im 1. Semester Informatik an einer FH und wir haben jetzt die 5. Praktikumsaufgabe in Programmieren gestellt bekommen, so ganz blick ich da aber nicht durch.

Es geht um folgendes:

Wir haben uns im Laufe der Praktika ein Programm gebastelt, welches Brüche einliest, ausgibt, berechnet und was auch immer mit diesen anstellt.

Das 5. Praktikum sieht jetzt voraus, dass wir unser aus dem 4. Praktikum erarbeiteten Vektor, das mit zufälligen Brüchen gefüllt wird durch ein C-Array ersetzen.

Das ganze soll natürlich dynamisch gehalten werden. Dazu folgender Auszug aus der Aufgabenstellung:

Teil B: Dynamische Speicherverwaltung

Stellen Sie nun Ihr Programm aus Teil A um auf dynamische Speicherverwaltung. Die Größe des verwendeten CArrays

soll sich nun dem Bedarf anpassen:

1. Unmittelbar nach dem Start der Anwendung gibt es noch gar kein C-Array sondern lediglich einen Zeiger

(Name: pfractions) der mit null initialisiert ist.

2. Jedes Mal, wenn mittels fractions_push_back ein Bruch hinzugefügt wird, soll fractions_push_back

prüfen, ob noch mindestens ein Speicherplatz für ein Bruchobjekt zur Verfügung steht. Falls nicht, soll

fractions_push_back, oder besser eine andere Memberfunktion, den verfügbaren Speicherplatz verdoppeln

und die bisher gespeicherten Elemente in den neuen Speicherplatz kopieren. Der alte Speicherplatz wird danach

nicht mehr benötigt. Für diese Funktionalität braucht man eine weitere Membervariable, die die Größe des

aktuell reservierten Speicherplatzes kennt (Name: fractionsCapacity).

Im Teil A sollte das Array statisch gehalten werden, nur als kleine Anmerkung.

Ich hab mir jetzt folgendes gedacht:

Erste Teilaufgabe von TeilB sagt ja, dass es noch gar kein Array geben soll, stattdessen halt einen Zeiger. Ich hab das jetzt so gemacht, korrigiert mich, falls es falsch ist.

Header-Datei

class Manager

{

private:


	 RandomFraction rnd_;

	 Statistic stat_;


	 //enum {MAX=1000};

	 //Fraction cArray[MAX];

	 Fraction *pfractions;

	 int fractionsCapacity;

	 int c_size;

public:

    friend class Fraction;


	Manager(int c_size=0, int fractionsCapacity=0);

	~Manager(void);


        ....   //einige weitere Memberfunktionen, hier aber überflüssig


	void fractions_push_back(Fraction);

	int fractions_size() const;

	int &operator[](int);

	void erase(int);

	void clear();

	void allocateMemory();


};

fractionsCapacity -> maximale Größe des Arrays Fraction* pfractions -> Zeiger für's Array c_size -> aktuelle größe des arrays CPP-Datei

Manager mng;


Manager::Manager(int c_size, int fractionsCapacity)

{

	/*  for ( int index=0 ; index<MAX ; index++ )

           cArray[index] = 0;*/


	  pfractions = new Fraction(0);    [COLOR="red"]//kann das so stimmen?[/COLOR]

	  this->fractionsCapacity=fractionsCapacity;


	  this->c_size = c_size;

}



void Manager::fractions_push_back(Fraction 

{

	 //cArray[c_size] = b;

	 //++c_size;                                  


	if (mng.fractions_size() >= mng.fractionsCapacity)

	{

		allocateMemory();

		pfractions[c_size++] = b;       [COLOR="red"]//  c_size an dieser stelle richtig?[/COLOR]

	}

}



int Manager::fractions_size() const

{

	return c_size;

}



void Manager::allocateMemory()

{

	 if (pfractions == 0)

		 fractionsCapacity = 1;

	 else

		 fractionsCapacity = fractionsCapacity*2;

}[/code]

Gedacht hab ich mir das ganze so:

Jedes mal wenn ein Objekt mittels fractions_push_back ins Array geschoben werden soll, soll erstmal geprüft werden, ob schon Speicherplatz vorhanden ist. Wenn nicht, dann soll Speicherplatz der Größe 1 angelegt werden. Wenn schon Speicherplatz vorhanden ist, die Kapazität des Arrays aber überschritten wurde, soll der vorhandene Speicherplatz verdoppelt, die vorhandenen Werte des alten Speicherplatzes in den neuen kopiert und der alte Speicherplatz anschließend gelöscht werden.

So müsste das doch dynamisch funktionieren?

Das Problem ist jetzt die Realisierung.. hab bisher nie mit Zeigern gearbeitet und bräuchte deshalb etwas Unterstützung.

Danke im voraus!

MfG

Valerio

[Valerio]

Hab's jetzt mal selbst etwas versucht, funktioniert jetzt zwar einigermaßen, aber kleine Fehler sind noch drin.

Und zwar wird der Vektor ziemlich oft mit den Standartwerten des Konstruktors der Klasse Fraction gefüllt, sprich mit Zähler=0 und Nenner=1, obwohl der zufällig generierte Bruch anders aussieht. Hab das auch mit Einzelschritten im Debugger durchlaufen lassen, bin aber nicht fündig geworden.

Hier mal der aktuelle Quelltext

Header

class Manager

{

private:


	 RandomFraction rnd_;

	 Statistic stat_;

	 std::vector<Fraction> vec_;


	 //enum {MAX=1000};

	 //Fraction cArray[MAX];

	 Fraction *pfractions;

	 int fractionsCapacity;

	 int c_size;

public:

    friend class Fraction;


	Manager(int c_size=0, int fractionsCapacity=0, Fraction *pfractions=NULL);

	~Manager(void);



	void fractions_push_back(Fraction);

	int fractions_size() const;

	int &operator[](int);

	void erase(int);

	void clear();

	void allocateMemory();[/PHP]

[b]CPP[/b]

[PHP]Manager mng;

Manager::Manager(int c_size, int fractionsCapacity, Fraction *pfractions)
{
/* for ( int index=0 ; index<MAX ; index++ )
cArray[index] = 0;*/


this->fractionsCapacity=fractionsCapacity;

this->c_size = c_size;
}


void Manager::fractions_push_back(Fraction
{
//cArray[c_size] = b;
//++c_size;

if (mng.fractions_size() >= mng.fractionsCapacity)
{
allocateMemory();
pfractions = new Fraction[mng.fractionsCapacity];
pfractions[c_size++] = b;
}
else
pfractions[c_size++] = b;
}


int Manager::fractions_size() const
{
return c_size;
}


void Manager::allocateMemory()
{
if (pfractions == 0)
fractionsCapacity = 1;
else
fractionsCapacity = fractionsCapacity*2;
}

Was jetzt noch fehlt ist das Kopieren der Werte und das löschen des alten Speichers. Habe momentan noch keine Idee wie ich da am besten rangehen kann.

[Klotzkopp]

Und zwar wird der Vektor ziemlich oft mit den Standartwerten des Konstruktors der Klasse Fraction gefüllt, sprich mit Zähler=0 und Nenner=1, obwohl der zufällig generierte Bruch anders aussieht. Hab das auch mit Einzelschritten im Debugger durchlaufen lassen, bin aber nicht fündig geworden.

Leider hast du den Teil des Codes, wo du die Fraction-Objekte erstellst, nicht gezeigt.

Was jetzt noch fehlt ist das Kopieren der Werte und das löschen des alten Speichers. Habe momentan noch keine Idee wie ich da am besten rangehen kann.

Kopie des Zeigers anlegen, neues Speicher holen, Objekte umkopieren, alten Speicherbereich über die Kopie freigeben.

[flashpixx]

Irgendwie erschließt sich mir da nicht wirklich der Sinn, warum ich die ganze Struktur umkopieren muss. Ich kann doch das Fraction Objekt direkt auf dem Heap erzeugen und halte in einem Array / Vektor die Zeiger auf die einzelnen Heap-Objekte vor. Wenn ein neues Objekt erzeugt wird, dann wird nur das Array mit den Zeigern vergrößert. Im Destruktor der Struktur lösche ich einfach jedes Heap Objekt durch einmaliges Laufen über das Array.

Das Kopieren von Zeigern sollte in meinen Augen effizienter sein, als das Kopieren von ganzen Objekten (ggf muss es ja sogar ein Deep-Copy sein, wenn ich den Gedanken weiter ausführe)

[Klotzkopp]

Das Kopieren von Zeigern sollte in meinen Augen effizienter sein, als das Kopieren von ganzen Objekten (ggf muss es ja sogar ein Deep-Copy sein, wenn ich den Gedanken weiter ausführe)

Das kommt ganz auf die Größe der Objekte und der Zeiger an. Wir wissen nicht, wie groß ein Fraction-Objekt ist, aber seien es mal 2 32-Bit-Integer. Wenn du den Code für 64 Bit baust, deine Zeiger also 64 Bit groß sind, hast du damit nichts gewonnen, sondern verlierst durch die zusätzliche Indirektion noch Zeit. Zusätzlichen Speicher brauchen die Zeiger auch, und die Objekte liegen nicht mehr garantiert hintereinander im Speicher, was nachteilig sein kann.

Und dank der Rvalue-Referenzen von C++0x und den dadurch möglich gewordenen Move-Konstruktoren kann das Umkopieren sehr billig sein.

Ich nehme an, dass hier einfach nur der Umgang mit Arrays geübt werden soll. Für so etwas nimmt man in C++ normalerweise std::vector.

[flashpixx]

Das kommt ganz auf die Größe der Objekte und der Zeiger an.

Stimmt, da hast Du recht

Für so etwas nimmt man in C++ normalerweise std::vector.

Daran hatte ich auch gedacht

[Valerio]

Hier mal der Teil, in dem das zufällige Fraction Objekt erzeugt wird.

void Manager::createRndFraction()

{


   /* mng.clear();*/


	int MAX_N=0;

    int anzahlBrueche;


	while(true){

	    try {

	    MAX_N = get_int("Eingabe MAX_N: ");

	    anzahlBrueche = get_int("Anzahl: ");

	    }

        catch(std::runtime_error &msg){

		     std::cerr << msg.what() << std::endl;

		     std::cin.clear(); std::cin.sync();

		     continue;	 

	         }		

	    break;		   


	}


	std::cout << std::endl;


	mng.rnd_.MIN_ = -(MAX_N-1);

	mng.rnd_.MAX_ = MAX_N-1;



	int n=0;

	    while (n++<anzahlBrueche)

			{

		      Fraction r(mng.rnd_.get(), mng.rnd_.get());

		      mng.fractions_push_back(r);

		    }


}

[/PHP]

Die zugehörige Get-Funktion:

[PHP]int RandomFraction::get()
{
int tmp=0;

for (;tmp==0;)
{
tmp = rand()%(MAX_-MIN_)+MIN_;
}

return tmp;
}

Und ein Teil der Fraction-Klasse + Konstruktor/Copy-Konstruktor:

class Fraction

{

private:

	int zaehler_;

	int nenner_;

public:

	Fraction(int zaehler_=0, int nenner_=1); //constructor

	Fraction(const Fraction &original);  //copy-constructor



Fraction::Fraction(int zaehler, int nenner)

{

	     zaehler_ = zaehler;

		 nenner_ = nenner;

		 //numberOfObjects_++;



		 cancelDown();

		 adjustSign();

}



Fraction::Fraction(const Fraction &original)

{

	zaehler_ = original.zaehler_;

	nenner_ = original.nenner_;

	//numberOfObjects_++;

}

[/PHP]

Das mit dem Kopieren der Werte habe ich noch nicht ganz verstanden.

Also erstmal eine Kopie meines aktuellen Zeigers anlegen

[PHP]Fraction* pfractionsCopy = pfraction //so richtig?

//Dann neuen Speicher nehmen -> mit pfractionsCopy?

pfractionsCopy = new Fraction[fractionsCapacity] //?

//Wenn es soweit richtig ist, wie kann ich die Objekte am effizientesten kopieren?
//Stehe etwas auf dem Schlauch.

Ich nehme an, dass hier einfach nur der Umgang mit Arrays geübt werden soll. Für so etwas nimmt man in C++ normalerweise std::vector.

So ist es

[Klotzkopp]

• Was tut fractions_push_back?
  
• Die Regel der großen 3: Wenn du einen dieser drei brauchst: Copy-Konstruktor, Copy-Zuweisungsoperator, Destruktor, dann brauchst du alle. Deine Fraction-Klasse braucht keinen dieser drei, somit auch keinen Copy-Konstruktor. Der vom Compiler automatisch generierte tut "das Richtige".
  
• Anstatt im Konstruktor-Rumpf die Member zuzuweisen, benutz Initialisierungslisten.

Fraction* pfractionsCopy = pfraction //so richtig?

Ja.

//Dann neuen Speicher nehmen -> mit pfractionsCopy?

Ja.

//Wenn es soweit richtig ist, wie kann ich die Objekte am effizientesten kopieren?

Das kommt auf die Objekte an. Wenn es POD-Typen sind, kannst du memcpy benutzen. Im allgemeinen Fall nimmst du einfach eine Schleife oder std::copy. Bearbeitet 10. Juni 2011 von Klotzkopp

[Valerio]

Entschuldige wegen dem Doppelpost, hab aber mal ein paar Bilder von meinem momentan Fehler gemacht, damit wird es vielleicht etwas klarer.

Das 1. Bild zeigt den zufällig erzeugten Bruch

Numberofobjects einfach ignorieren =)

Bild1

Das 2. Bild zeigt das, was in pfractions steht, nachdem "geschrieben" wurde.

Bild2

Und das 3. zeigt eine Ausgabe

Bild3

[Klotzkopp]

Solange du nicht umkopierst, ist das nicht weiter verwunderlich. Du legst doch beim Vergrößern ein komplett neues Array von default-initialisierten Fraction-Objekten an.

[Valerio]

• Was tut fractions_push_back?
  
• Die Regel der großen 3: Wenn du einen dieser drei brauchst: Copy-Konstruktor, Copy-Zuweisungsoperator, Destruktor, dann brauchst du alle. Deine Fraction-Klasse braucht keinen dieser drei, somit auch keinen Copy-Konstruktor. Der vom Compiler automatisch generierte tut "das Richtige".
  
• Anstatt im Konstruktor-Rumpf die Member zuzuweisen, benutz Initialisierungslisten.

Das kommt auf die Objekte an. Wenn es POD-Typen sind, kannst du memcpy benutzen. Im allgemeinen Fall nimmst du einfach eine Schleife oder std::copy.

Fractions_push_back soll jeden zufällig erzeugten Bruch an die letzte Stelle des Arrays schieben.

Den Copy-Konstruktor sollten wir im Rahmen eines anderen Praktikums erstellen.

Das mit den Initialisierungslisten kann ich so nicht machen, da wir nur das verwenden dürfen, was in den Vorlesungen durchgenommen wurde. Da achtet der Prof in den Praktika auch ziemlich streng drauf..

[Valerio]

Bekomm's einfach nicht hin.. hab jetzt mehrere Varianten ausgetestet, bei den meisten kam es zu Heap-Fehlern und bei meiner aktuellen liegt das selbe Problem vor, wie eben. Kopiert werden die Objekte auch nicht.

void Manager::fractions_push_back(Fraction 

{

	 //cArray[c_size] = b;

	 //++c_size;                                  // umdrehen?


	if (mng.fractions_size() >= mng.fractionsCapacity)

	{

		allocateMemory();

		pfractions = new Fraction[fractionsCapacity];

	}


	pfractions[c_size++] = b;

}



void Manager::allocateMemory()

{

	 if (pfractions == 0)

		 fractionsCapacity = 1;

	 else

	 {


		 Fraction* pfractionsCopy = pfractions;

		 fractionsCapacity = fractionsCapacity*2;

		 pfractionsCopy = new Fraction[fractionsCapacity];

		 for (int n=0; n<c_size;n++)

		 {

		      pfractions[n] = pfractionsCopy[n];

	     }


		 delete[] pfractionsCopy;

	 }

}


[/PHP]

[Valerio]

Hat sich erledigt.. hab es jetzt hinbekommen =)

Danke dir @Klotzkopp

Bearbeitet 11. Juni 2011 von Valerio