Probleme mit Pointern und Arrays (und Pointer-Arrays)

tda

Hallo,

mit folgendem stark reduzierten Quelltext möchte ich die Elemente einer Menge vertauschen (permutieren). Die Menge ist gegeben und außerdem ein Array von z.B. 10 Permutationen. Nun soll meine Menge gemäß der z.B. dritten Permutation vertauscht werden.

Dazu möchte ich die Elemente der Menge zunächst kopieren (in temp ) und dann gemäß der Permutation zuordnen, etwa wie nachstehend beschrieben. Doch irgendwo müsste ich wohl Pointer statt der Variablen selbst verwenden, denn so wie es bisher da steht, ist alles (genauer: die Elemente der Menge) futsch, wenn mit dem Ende der Funktion permutieren mein temp zerstört wird. Kann mir jemand einen Tipp geben, wo?

class ELEMENT {
	// ...
};

class PERMUTATION {
	public:
		short bild(short i) const;
		//...
};

class MENGE {
	public:
		void permutieren(const PERMUTATION *pi);
	private:
		ELEMENT *elemente;
		short anzahl;
	//...
};

short PERMUTATION::bild(short i) const {
	// liefert das Bild von i unter der Permutation zurück
}

void MENGE::permutieren(const PERMUTATION *pi) {
	ELEMENT temp[anzahl];  // speichert temporär die Elemente
	for (short j=0 ; j < anzahl; ++j) {  // j durchläuft die Nummern der Elemente
		temp[j] = elemente[j];
	}
	for (short j=0 ; j < anzahl; ++j) {  // j durchläuft die Nummern der Elemente
		elemente[ pi[3].bild(j) ] = temp[j];  // die Elemente werden schließlich gemäß pi[3] zugeordnet
	}
}

int main() {
	MENGE *m = new MENGE;
	PERMUTATION *pi = new PERMUTATION[10];
	//... (m mit Inhalt füllen und so)
	m->permutieren(pi);
}

Im Wesentlich geht es um die Zeilen 27 und 30. Dort wird umsortiert. Die Frage ist also: wie kann ich machen, dass das Zerstören von temp am Ende der Funktion keine Auswirkungen auf elemente hat?

Ich hoffe, diese kondensierte Fassung des Quelltexts reicht aus. Für Rückfragen stehe ich natürlich gern zur Verfügung. Vielen Dank im Voraus!

SeppJ

Was ist denn das besondere an pi[3]? Sollte der Index von pi nicht auch durchlaufen werden?

P.S.: Die ist schon klar, dass die Standardbibliothek die Benutzung von new, so wie du es hier benutzt, überflüssig macht?
P.P.S.: Dir ist hoffentlich auch klar, dass die Standardbibliothek bereits Permutationsfunktionen anbietet?
P.P.P.S.: Und über die Verwendung von short brauche ich auch nichts zu sagen, oder?

tda

SeppJ schrieb:

Was ist denn das besondere an pi[3]? Sollte der Index von pi nicht auch durchlaufen werden?

Die 3 war in der Tat nur ein Beispiel. Im eigentlichen Programm gibt es in der Funktion permutieren tatsächlich zunächst eine Schleife, die die i durchläuft und es steht dann pi[i].bild(j) an der entsprechenden Stelle. Aber das schien mir für mein Problem unerheblich.

SeppJ schrieb:

Die ist schon klar, dass die Standardbibliothek die Benutzung von new, so wie du es hier benutzt, überflüssig macht?

In dieser stark verkürzten Fassung sicherlich. Ich habe new verwendet, weil die damit erzeugten Objekte

unter Umständen recht groß werden können (z.B. um die 3800 long integer enthalten) und
nicht wie hier in main() , sondern in anderen Funktionen (oder Konstruktoren) erzeugt werden und dann ja nicht am Ende der Funktion zerstört werden sollen.

SeppJ schrieb:

Dir ist hoffentlich auch klar, dass die Standardbibliothek bereits Permutationsfunktionen anbietet?

Nein, da würde mich ein Stichwort (z.B. Funktionsname) interessieren. Ich habe soeben next_permutation entdeckt, aber die hilft mir ja nicht, wenn ich eine ganz bestimmte (gegebene) Permutation anwenden möchte, oder? Denkst du an noch andere, die besser passen könnten?

SeppJ schrieb:

Und über die Verwendung von short brauche ich auch nichts zu sagen, oder?

Äh? Doch, bitte!

(In class PERMUTATION habe ich short gewählt, weil mir das ausreicht und ich damit beim Abspeichern in einer Datei Platz spare, ähnlich bei MENGE::anzahl ; und in der for -Schleife schließlich, weil MENGE::anzahl ja eh nicht größer sein kann.)

Danke im Voraus für weitere Kommentare dazu!

Vicious Falcon

Schau mal hier.

tda

Vicious Falcon schrieb:

Schau mal hier.

Dankeschön.

Aber wenn ich das richtig sehe, gibt es da keine elegantere Möglichkeit, eine ganz bestimmte Permutation zu erreichen, als 20-mal next_permutation aufzurufen, wenn es sich z.B. um die 20. Permutation handelt, oder?

Und da meine Elemente keine Zahlen oder Buchstaben sind und damit kein operator< definiert ist, müsste ich auch den Größenvergleich zweier Elemente erst noch programmieren, oder?

tda

Gibt es denn keine Möglichkeit, z.B. die Zeilen 25, 27 und 30 im Code im allerersten Beitrag so zu ändern, dass nur die Pointer umsortiert werden und die Inhalte unberührt bleiben?

(Ich dachte vielleicht an sowas wie ELEMENT (*temp)[anzahl]; in Zeile 25, aber dazu kenne ich mich eben noch zu wenig mit Pointern aus.)

Oder ist so etwas gar nicht möglich, wenn elemente ein Array von ELEMENT ist und beim Anlegen des Arrays die Reihenfolge der Plätze im Speicher bereits für seine ganze Lebenszeit festgelegt ist?

So etwa wird elemente übrigens erzeugt:

MENGE::MENGE(short anzahl) {
	elemente = new ELEMENT[anzahl];
	//...
}

Vielen Dank für weitere Tipps!

SeppJ

tda schrieb:

Ich habe new verwendet, weil die damit erzeugten Objekte

unter Umständen recht groß werden können (z.B. um die 3800 long integer enthalten) und
Na und? Das machen die Standardcontainer doch sowieso?

nicht wie hier in main() , sondern in anderen Funktionen (oder Konstruktoren) erzeugt werden und dann ja nicht am Ende der Funktion zerstört werden sollen.

Ungewöhnliche Objektlebensdauer ist tatsächlich einer der wenigen Fälle, wo new gerechtfertigt ist. Wobei es mich doch stark wundert, dass ausgerechnet du zu den wenigen Leuten gehörst, die solch eine spezielle Lebensdauer tatsächlich brauchen.

SeppJ schrieb:

Und über die Verwendung von short brauche ich auch nichts zu sagen, oder?

Äh? Doch, bitte!

Du tauscht hier Platz (der vom Compiler wahrscheinlich ohnehin wieder hochgepadded wird) gegen Geschwindigkeit.

SeppJ

tda schrieb:

Gibt es denn keine Möglichkeit, z.B. die Zeilen 25, 27 und 30 im Code im allerersten Beitrag so zu ändern, dass nur die Pointer umsortiert werden und die Inhalte unberührt bleiben?

(Ich dachte vielleicht an sowas wie ELEMENT (*temp)[anzahl]; in Zeile 25, aber dazu kenne ich mich eben noch zu wenig mit Pointern aus.)

Oder ist so etwas gar nicht möglich, wenn elemente ein Array von ELEMENT ist und beim Anlegen des Arrays die Reihenfolge der Plätze im Speicher bereits für seine ganze Lebenszeit festgelegt ist?

Das ist nicht möglich, da du da kein Array von Pointern, sondern ein Array von konkreten Objekten hast.

tda

Danke für die Antworten. Ich habe mir das alles nochmal genauer angeschaut und kann meine Frage jetzt vielleicht ein bisschen konkreter formulieren:

SeppJ schrieb:

Das ist nicht möglich, da du da kein Array von Pointern, sondern ein Array von konkreten Objekten hast.

Das verstehe ich soweit. Nun kommt aber begünstigend hinzu, dass jedes ELEMENT selbst wiederum nur aus Zeigern auf Objekte einer weiteren Klasse (und einem bool ) besteht*:

class ELEMENT {
	private:
		TEIL *a_teil;
		TEIL *b_teil;
		bool info;
	//...
};

Sollte es da nicht möglich sein, eine Kopie von einem ELEMENT (also von den Adressen von a_teil und b_teil , nicht den Inhalten) in temp zu speichern (siehe wieder Zeilen 27 und 30 im ersten Beitrag) und dann - neu geordnet - wieder in die jeweiligen ELEMENT e zurück zu kopieren?

Ganz am Rande: Da sich die Größe der TEIL -Objekte (die selbst wieder Arrays enthalten) erst während der Laufzeit ergibt, konnte ich nur Pointer benutzen und kann den Speicherplatz der TEIL e erst im Konstruktor von ELEMENT anfordern, was vielleicht die Frage nach meinem exzessiven Gebrauch von new beantwortet.

SeppJ

tda schrieb:

SeppJ schrieb:

Das ist nicht möglich, da du da kein Array von Pointern, sondern ein Array von konkreten Objekten hast.

Das verstehe ich soweit. Nun kommt aber begünstigend hinzu, dass jedes ELEMENT selbst wiederum nur aus Zeigern auf Objekte einer weiteren Klasse (und einem bool ) besteht*:
class ELEMENT {
	private:
		TEIL *a_teil;
		TEIL *b_teil;
		bool info;
	//...
};
Sollte es da nicht möglich sein, eine Kopie von einem ELEMENT (also von den Adressen von a_teil und b_teil , nicht den Inhalten) in temp zu speichern (siehe wieder Zeilen 27 und 30 im ersten Beitrag) und dann - neu geordnet - wieder in die jeweiligen ELEMENT e zurück zu kopieren?

Sofern du keine Deep Copy machst, passiert dass doch sowieso schon. Da du eine Deep Copy explizit programmieren müsstest, ist dies bei dir vermutlich der Fall. Falls du dein Objekt schon so programmiert hast, dass eine Tiefkopie erzeugt wird, dann füg ihm eben eine entsprechende Methode zu, um diese zu vermeiden.

Ganz am Rande: Da sich die Größe der TEIL -Objekte (die selbst wieder Arrays enthalten) erst während der Laufzeit ergibt, konnte ich nur Pointer benutzen und kann den Speicherplatz der TEIL e erst im Konstruktor von ELEMENT anfordern, was vielleicht die Frage nach meinem exzessiven Gebrauch von new beantwortet.

Das sind alles keine Gründe für new.

tda

SeppJ schrieb:

tda schrieb:

Sollte es da nicht möglich sein, eine Kopie von einem ELEMENT (also von den Adressen von a_teil und b_teil , nicht den Inhalten) in temp zu speichern (siehe wieder Zeilen 27 und 30 im ersten Beitrag) und dann - neu geordnet - wieder in die jeweiligen ELEMENT e zurück zu kopieren?

Sofern du keine Deep Copy machst, passiert dass doch sowieso schon.

Ich weiß zwar nicht genau, was Deep Copy ist, aber ich vermute mal, dass ich alle Membervariablen quasi „zu Fuß“ einzeln kopiere. Solch eine Funktion ELEMENT::kopieren_von(const ELEMENT &vorlage) habe ich in der Tat auch, aber die benutze ich an dieser Stelle nicht, da ich das Hin- und Herkopieren der Inhalte ja gerade vermeiden will.

Das Kopieren von elemente[j] nach temp[j] und zurück funktioniert auch (wenn ich mir z.B. mal die Speicheradressen der TEIL e jeweils ausgeben lasse), aber nach Ende der Funktion permutieren gibt es einen Segmentation fault , wenn ich danach erneut auf elemente[j] zugreifen will.

Ich vermute ja, dass beim Löschen von temp ja der entsprechende Speicherbereich gelöscht wird - der ja jetzt aber auch gleichzeitig Speicherbereich von elemente ist. Kann das die Ursache sein?

Und kann ich das vielleicht verhindern, indem ich irgendwas mit &temp oder *temp statt temp mache oder so? Oder irgendwie anders? Vielen Dank im Voraus?

SeppJ

tda schrieb:

Ich weiß zwar nicht genau, was Deep Copy ist,

Den Fachbegriff habe ich natürlich genannt, damit du ihn einfach ignorierst .

aber ich vermute mal, dass ich alle Membervariablen quasi „zu Fuß“ einzeln kopiere.

Nein.

Solch eine Funktion ELEMENT::kopieren_von(const ELEMENT &vorlage) habe ich in der Tat auch, aber die benutze ich an dieser Stelle nicht, da ich das Hin- und Herkopieren der Inhalte ja gerade vermeiden will.

Also doch der Inhalte? Dann ja. Was denn nun? Und ist das ein Extra-Member oder dein Kopierkonstruktor/Zuweisungsoperator?

Das Kopieren von elemente[j] nach temp[j] und zurück funktioniert auch (wenn ich mir z.B. mal die Speicheradressen der TEIL e jeweils ausgeben lasse), aber nach Ende der Funktion permutieren gibt es einen Segmentation fault , wenn ich danach erneut auf elemente[j] zugreifen will.

Was ist denn jetzt ein TEIL ?

Ich vermute ja, dass beim Löschen von temp ja der entsprechende Speicherbereich gelöscht wird - der ja jetzt aber auch gleichzeitig Speicherbereich von elemente ist. Kann das die Ursache sein?

So funktioniert das mit dem Kopieren und dem Löschen nicht

Und kann ich das vielleicht verhindern, indem ich irgendwas mit &temp oder *temp statt temp mache oder so? Oder irgendwie anders?

Wenn man nur rät was richtig sein könnte, funktioniert das nicht mit dem Programmieren. Du musst von jedem einzelnen Zeichen in deinem Programm genau wissen, was es macht und wozu.

tda

SeppJ schrieb:

Und ist das ein Extra-Member oder dein Kopierkonstruktor/Zuweisungsoperator?

Ein Member. Den Zuweisungsoperator habe ich für meine Objekte nicht extra definiert.

Was ist denn jetzt ein TEIL ?

Siehe diesen vorigen Beitrag.

Ich vermute ja, dass beim Löschen von temp ja der entsprechende Speicherbereich gelöscht wird - der ja jetzt aber auch gleichzeitig Speicherbereich von elemente ist. Kann das die Ursache sein?

So funktioniert das mit dem Kopieren und dem Löschen nicht

Hm, warum kann ich dann aber, nachdem temp gelöscht wurde, nicht mehr auf elemente zugreifen?

Und kann ich das vielleicht verhindern, indem ich irgendwas mit &temp oder *temp statt temp mache oder so? Oder irgendwie anders?

Wenn man nur rät was richtig sein könnte, funktioniert das nicht mit dem Programmieren. Du musst von jedem einzelnen Zeichen in deinem Programm genau wissen, was es macht und wozu.

Ja, sehe ich ja genauso. Deswegen frage ich ja hier in die Runde, bevor ich drauflos rate: lässt sich aus diesem Gedanken etwas Sinnvolles machen?

Vielen Dank im Voraus für Tipps!