Klasse in Klasse verwenden

[tröröö]

Ich weiß schon grundsätzlich, was ein Zeiger ist. Und die Datenstruktur stimmt, das ist nichts, was ich selbst erfunden habe.

Wenn du mir hilfst, das Problem zu lösen, kläre ich dich über diese Datenstruktur auf

[Skym0sh0]

Nein, sie stimmt so nicht.

Wenn das z.B. aus Java übernommen hast, wäre das nicht das gleiche.

Wie SeppJ schon sagte: Du brauchst eine Art von Referenzierung (Referenz oder (Smart-)Zeiger) auf die Kinder-Edges. Ansonsten hast du einen zyklus der nicht aufgebrochen werden kann, weder vom Programmier noch vom Compiler. Die Folge wäre ein unendlich großes Objekt, was ja offensichtlich nicht existieren kann.

Soll das irgendwas Baumartiges sein ? (Quadtree, Octree, Neuronales Netz?)

[tröröö]

Soll das irgendwas Baumartiges sein ? (Quadtree, Octree, Neuronales Netz?)

Diese Datenstruktur nennt sich "winged-edge". Das ist eine Alternative zu B-Reps. Die werden für 3D-Programme verwendet.

Du brauchst eine Art von Referenzierung

Ja, das habe ich auch schon kapiert. C++ kann das nicht kompilieren, weil es beim Kompilieren der Klasse die Klasse halt noch nicht kennt.

Naja, ich werds halt alleine versuchen, das irgendwie mit Zeiger hinzubekommen. Vielleicht braucht ich die auch gar nicht, sondern kann mit Vector arbeiten ...

[daddy_felix]

tröröö schrieb:

Vielleicht braucht ich die auch gar nicht, sondern kann mit Vector arbeiten ...

Da bist du vermutlich irgendwo auf den Tipp gestoßen, ein C-Array ("irgendwas mit Sternchen") durch einen vector zu ersetzen.

Das hat mit deinem Problem nichts zu tun.

[Skym0sh0]

Naja, theoretisch ginge das schon mit einem Vector. Aber die semantische Zuordnung (alá LeftEdge, RightEdge oder wie das war) wäre nicht mehr gegeben.

Für mich sieht das so auf den ersten Blick schon nach einer Struktur aus, die man mit Zeigern umsetzt. Aber da müsste tröörö sich halt um den Speicher kümmern.

(Ich will an der Stelle jetzt gar nichts für oder gegen Smart-Pointer sagen. Die sind ja in letzter Zeit hier im Forum gerade bei Baumstrukturen mal geliebt mal total verpöhnt.)

[daddy_felix]

Skym0sh0 schrieb:

Naja, theoretisch ginge das schon mit einem Vector. Aber die semantische Zuordnung (alá LeftEdge, RightEdge oder wie das war) wäre nicht mehr gegeben.

Nein, sowas geht nicht:

class Edge
{
  std::vector<Edge> edges;
}

Sein eigentliches Problem ist doch, dass die Klasse "Edge" Member der Klasse "Edge" hält. Egal, ob diese individuelle Member sind oder in einem vector gehalten werden.

Das lässt sich nur durch Verwendung von Referenzen/Pointern aufbrechen. Natürlich *könnte* man diese Pointer dann in einem vector halten, aber das ist jetzt erstmal wurscht

[Skym0sh0]

Warte, jetzt bring mich nicht in Bedrängnis. Das geht echt nicht mit dem Vector??!
Das probier ich aus...

[daddy_felix]

Skym0sh0 schrieb:

Warte, jetzt bring mich nicht in Bedrängnis. Das geht echt nicht mit dem Vector??!

achnee, warte mal, der könnte ja auch leer sein.

nein, vielleicht gehts doch...

[Skym0sh0]

Also laut Ideone gehts:

#include <vector>

class X
{
	std::vector<X> vx;

public:
	X()
	: vx{{}, {}, {}}
	{}
};

int main()
{
	X x;
	return 0;
}

Und hier ist sogar noch das "Phänomen", dass ein Laufzeitfehler erzeugt wird, weil ein Zyklus bei der Initialisierung stattfindet.

Aber ist eigentlich auch logisch, weil vector einen Pointer auf T hat und sich um Speicher und alles selbst kümmert.

[daddy_felix]

ok, danke für die Klarstellung.

Aber weiterhin gilt: zwei Instanzen können sich nicht gegenseitig beinhalten.

Es funktioniert somit zwar für eine Baumstruktur, bei der nur in eine Richtung navigiert werden kann. Sowie aber in beide Richtungen navigiert werden soll oder sich zyklische Strukturen ergeben, ist Ende.

[Skym0sh0]

Folgende Aussagen nur unter der Prämisse, dass ich das richtig verstehe, was du meinst (nicht dass wir aneinander vorbei reden):

Doch klar geht das in beide Richtungen.
In einem Binärbaum z.B. kennt jeder Knoten seinen Elternknoten und auch seine (beiden) Kindknoten.
Das einzige, wodrauf man aufpassen muss, ist beim Löschen. Nicht dass aus Versehen der ganze Baum gelöscht wird.

Oder verstehe ich dich da falsch bei den zyklischen Strukturen?

[daddy_felix]

Skym0sh0 schrieb:

Folgende Aussagen nur unter der Prämisse, dass ich das richtig verstehe, was du meinst (nicht dass wir aneinander vorbei reden):

mir geht es immer noch um die Modellierung *ohne Pointer/Referenzen*.

Skym0sh0 schrieb:

Doch klar geht das in beide Richtungen.
In einem Binärbaum z.B. kennt jeder Knoten seinen Elternknoten und auch seine (beiden) Kindknoten.

ok, modellieren wir das doch mal:

A
B1
C1 C2

A kennt B1 (Kind) und C1/C2 kennen B (parent). Wie sollen nun sowohl A als auch C1 und C2 den Knoten B1 halten, dass alle auf dieselbe Instanz zugreifen (ohne Pointer/Referenzen!)?

[Skym0sh0]

Gar nicht, aber genau das wollte ich ja ausschließen; da haben wir aneinander vorbei geredet.

Selbst wenn A nur B(Kind) kennen soll, und wir modellieren das ohne Zeiger, geht das schon nicht.

struct Node
{
    Node child;
};

int main()
{
    Node A;
    Node B;
    A.child = B;

    // ...
}

Wird nicht laufen.
Wenn das aber verschiedene Typen sind, dann geht das wiederum. Aber auch nur, wie du sagst, in eine Richtung:

struct NodeB
{
    //NodeA child;
};

struct NodeA
{
    NodeB child;
};

int main()
{
    NodeA a;
    NodeB b;
    a.child = b;
//    b.child = a;
}

[daddy_felix]

ok, dann hätten wir das auch geklärt

[seldon]

Es handelt sich hier nicht um eine Baumstruktur, wenn ich mich nicht sehr täusche, sondern eher um eine Art Netz. Insbesondere können (und werden) zyklische Objektverweisgruppen entstehen, indem etwa -- jetzt unter der Annahme, dass das alles auf Zeiger umgestellt wäre -- this->LeftSuccessorEdge()->LeftSuccessorEdge()->LeftSuccessorEdge() == this wird.

In einer Baumstruktur wären die Besitzverhältnisse mit unique_ptr einfach zu lösen; hier ist es schwieriger. shared_ptr reicht nicht, da der Graph zyklisch ist, und ich sehe keine einfache Möglichkeit, das mit weak_ptr aufzubrechen.

Ich würde mir wahrscheinlich eine Graphenkopfklasse bauen, die die Edges, Faces und Vertices besitzt und ihre Lebensdauer festlegt, und in den Edges, Faces und Vertices selbst mit nackten Zeigern arbeiten.

[tntnet]

struct Node
{
    Node child;
};

Kann nicht funktionieren. Der Compiler reserviert für die Klasse so viel Speicher, wie für jedes einzelne Element benötigt wird. Hat eine Klasse beispielsweise 2 Member vom Typ int, dann ist die gesamte Klasse eben 2*sizeof(int) groß. Wie groß ist jetzt Node? In dem Beispiel sizeof(Node). Da erkennt man schon die Rekursion der Fragestellung. Man bedenke, dass eine Instanz a einen Member a.child hätte, welches ein Member a.child.child hätte, welches einen Member a.child.child.child hätte...

Ein Zeiger auf Node wäre ok, da sizeof(Node*) bereits exakt definiert ist. Auch ein std::vector<Node> ist ok, da der vector intern ja auch nur ein Zeiger auf die Elemente hält. Ein Node[6] funktioniert wiederum nicht, da dort wieder das gleiche Problem auftritt.

[Nexus]

tntnet schrieb:

Auch ein std::vector<Node> ist ok

Nein, ist es nicht. Templates in der Standardbibliothek verlangen vollständige Typen als Parameter, ausser es steht explizit was anderes (wie z.B. bei unique_ptr ).

[tntnet]

Nexus schrieb:

tntnet schrieb:

Auch ein std::vector<Node> ist ok

Nein, ist es nicht. Templates in der Standardbibliothek verlangen vollständige Typen als Parameter, ausser es steht explizit was anderes (wie z.B. bei unique_ptr ).

Jetzt hast Du mich aber erfolgreich irritiert. Also zumindest bin ich mir unsicher. Hast Du da einen Verweis auf den Standard?

Am Ende der Klassendeklaration ist die Klasse vollständig bekannt. Der Compiler weiß, ob die Klasse alle Voraussetzungen erfüllt. Daher kann er erst mal seine Arbeit erledigen.

Und auch wenn die compilierbarkeit mit einem Compiler kein Beweis ist, ist es erst mal ein Hinweis, dass es so sein könnte und näherer Betrachtung Wert ist. Ich habe hier mal ein Beispiel:

#include <vector>

struct Foo
{
    std::vector<Foo> childs;
};

Mit g++ -Wall -pedantic -c foo.cpp übersetzt ergibt keinen Fehler und noch nicht mal eine Warnung. Die gcc-version ist 4.7.2. Ist der Code standardkonform?

[Skym0sh0]

[...] The template parameter T of unique_ptr may be an incomplete type.

Aber mehr finde ich jetzt grad nicht zu irgendwelchen (un-)vollständigen Typen in der STL.

[camper]

Skym0sh0 schrieb:

[...] The template parameter T of unique_ptr may be an incomplete type.

Aber mehr finde ich jetzt grad nicht zu irgendwelchen (un-)vollständigen Typen in der STL.

17.6.4.8/2