C++: Baumstruktur

[Jörg M. (Gast)]

Hallo zusammen,
ich habe eine Klassenhierachie die einen Art Baum umsetzt, das Ganze 
sieht ungefähr so aus:

class myClass
{
    myClass *parent;
    std::vector<myClass*> childs;

    /*
     * Hier stehen weitere Attribute die für die "eigentliche"
   * Aufgabe der Klasse relevant sind.
     * z.B.: std::string name;
     */
public:
    //Konstruktoren...
    //Baumverwaltung (z.B. insert(), search() usw.
    std::string getName();
  std::string getFullName();
}

Der Ansatz tut soweit. Allerdings finde ich es unschön, dass eine 
Klasse, die einem bestimmten Zweck dient, gleichzeitig Informationen 
über ihre Anordnung in einem Container-Konstrukt beinhaltet. Sowas 
sollte ja normal getrennt sein. Eigentlich, meiner Meinung nach, sollte 
die Klasse garkeine Information beinhalten, dass sie sich in einem - wie 
auch immer gearteten - Container befindet.

Es gibt ja für Baumstrukturen OpenSource-Lösungen, recht bekannt scheint 
tree.hh zu sein, dass sich sehr an der STL orientiert.
Ich würd also gerne meine Klasse umschreiben und dann deren Objekte in 
einem separaten Container (z.B. tree.hh) sammeln.

class myClass
{
    /*
     * Hier stehen jetzt nur noch Attribute die für die "eigentliche"
   * Aufgabe der Klasse relevant sind.
     * z.B.: std::string name;
     */
public:
    //Konstruktoren...
    std::string getName();
  std::string getFullName();
}

tree<myClass> myTree;

So würde das dann aussehen.

Problem dabei:
Wie würde ich denn dann die Funktion getFullName() umsetzen?
Diese liefert mir nicht nur den eigenen Namen, sondern auch die Namen 
aller Eltern, also so eine Art Pfad zum Objekt innerhalb des Baumes. 
Dabei wird eben durch den parent*-Pointer bis zum root iteriert.
Bei der separaten Container-Klasse hat ja mein myClass-Objekt keinen 
Bezug mehr zur Klassenstruktur.

Der Baum selbst stellt natürlich Iteratoren zur Verfügung. Von einem 
Knoten den Elternknoten zu bestimmen ist möglich. Aber ein Knoten 
"besitzt" ja sein myClass Objekt. also bräuchte myClass wiederum einen 
Pointer auf den Knoten. Bin jetzt nicht der fitteste in C++, aber das 
erscheint mir seeehr ungeschickt.
Wie also würdet ihr das lösen?

[Εrnst B. (ernst)]

Evtl als externe Template-Funktion?

template<typename Tree>
std::string getRootPath(Tree::const_iterator x) {
  std::ostringsteeam buffer;
  while (x) {
    buffer << x->getDataPointer()->getName();
    x=x->getParent();
  }
  return buffer.str();
}

(Nur als grobe Idee, Reihenfoge umdrehen, Trennzeichen usw. fehlt.)

[Vlad T. (vlad_tepesch)]

wenn deine Objekte die Einordnung in einen Baum als feste zu ihnen 
gehörige Eigenschaft haben und es sinn macht, dass sie diese Information 
selbst beseitzen, dann ist der generische Baum-Container nicht das 
richtige.

Dennoch würde ich es ein wenig anders umsetzen, als du es oben getan 
hast.

Ich würde eine Basisklasse TreeNode implementieren, die die 
Verwaltungslogik des Baumes enthält und von dieser dann ableiten.
Nachteil ist allerdings, dass man bei Navigation durch den Baum nur 
Basisklassenzeiger hat.

[cc (Gast)]

Wenn ich deine Frage richtig verstehe suchst du nach etwas wie der 
Cheshire Cat bzw. dem Opaque Pointer.

https://en.wikipedia.org/wiki/Cheshire_Cat_idiom

[Dr. Sommer (Gast)]

Vlad Tepesch schrieb:
> Ich würde eine Basisklasse TreeNode implementieren, die die
> Verwaltungslogik des Baumes enthält und von dieser dann ableiten.
> Nachteil ist allerdings, dass man bei Navigation durch den Baum nur
> Basisklassenzeiger hat.
Deswegen macht man ein Template aus dem Baum und dem TreeNode, s.d. man 
immer Referenzen auf die abgeleitete Klasse bekommt.

Wenn du dich entschließt es so zu machen/belassen, solltest du dir das 
aber nochmal überdenken:
Jörg M. schrieb:
> class myClass
> {
>     myClass *parent;
>     std::vector<myClass*> childs;
Was spricht gegen:

class myClass {
  myClass* parent;
  std::vector<myClass> childs;

Wenn die Antwort ist dass es verschiedene Child-Typen gibt und du daher 
Pointer auf die Basistypen verwendest, warum dann nicht:

class myClass {
  myClass* parent;
  std::vector<unique_ptr<myClass>> childs;

[Masl (Gast)]

Danke euch erstmal.

Dr. Sommer schrieb:
> Wenn die Antwort ist dass es verschiedene Child-Typen gibt und du daher
> Pointer auf die Basistypen verwendest, warum dann nicht:class myClass {
>   myClass* parent;
>   std::vector<unique_ptr<myClass>> childs;

Ok, ein unique_ptr ist natürlich schöner als ein raw. Hätt ich eh so 
gemacht, wollte aber mein Beispiel nicht unnötig komplizieren :-)

Dr. Sommer, du würdest also so wie Vlad Tepesch vorgehen?
Das hab ich mir auch scho überlegt, finde aber einen Container schöner 
als eine Basisklasse die, dem jeweiligen Bedarf entsprechend, abgeleitet 
wird.
Nur dann stellt sich eben wieder meine ursprüngliche Frage, nämlich wie 
ein myClass-Objekt auf seine Eltern-Knoten zugreifen kann.

Mir fehlt in C++ noch die Erfahrung, welches Vorgehen "schöner" ist...

[Jörg M. (Gast)]

cc schrieb:
> Wenn ich deine Frage richtig verstehe suchst du nach etwas wie der
> Cheshire Cat bzw. dem Opaque Pointer.
>
> https://en.wikipedia.org/wiki/Cheshire_Cat_idiom

Der Opaque Pointer löst, so wie ich das verstehe, eher ein anderes 
Problem. Ich glaube nicht dass ich den suche :-)

[Dr. Sommer (Gast)]

Masl schrieb:
> Dr. Sommer, du würdest also so wie Vlad Tepesch vorgehen?
> Das hab ich mir auch scho überlegt, finde aber einen Container schöner
> als eine Basisklasse die, dem jeweiligen Bedarf entsprechend, abgeleitet
> wird.
Schöner ja, aber dann hat deine enthaltene Klasse ja keinen direkten 
Zugang zur Baumstruktur, also Eltern & Kinder - auch doof und 
ineffizient.
> Nur dann stellt sich eben wieder meine ursprüngliche Frage, nämlich wie
> ein myClass-Objekt auf seine Eltern-Knoten zugreifen kann.
Indem die Basis-Klasse halt diesen Pointer und die Kinder enthält.
> Mir fehlt in C++ noch die Erfahrung, welches Vorgehen "schöner" ist...
Das kommt immer drauf an. Würde jedenfalls sagen wenn es elementare 
Eigenschaft der Klasse ist in einem Baum zu sein (und sie nicht 
irgendwann in einer Liste auftaucht oder so) darf sie ruhig 
Baum-spezifische Dinge wie parent-Pointer enthalten.

[Εrnst B. (ernst)]

Masl schrieb:
> Das hab ich mir auch scho überlegt, finde aber einen Container schöner

Dann mach halt. Ggfs. mit "treeNode<X>"-Klasse innerhalb von "tree<X>", 
die die Members enthält, die sonst in der Basisklasse wären.

Wenn's dann noch besonders "schön" werden soll: Bastel dir einen 
Iterator in das Tree-Template, der vom aktuellen Knoten zur Wurzel 
läuft, schmeiß den in std::for_each und bastel dir (evtl mit ein paar 
Helfern aus <functional>) so deine Pfad-Ausgabe zusammen.

Und, wenn man noch was dabei Lernen will: für einen Baum kann man einen 
ganzen Berg von unterschiedlichen Iteratoren implementieren, die in 
verschiedenen Reihenfolgen über alle Elemente laufen.

[Vlad T. (vlad_tepesch)]

Dr. Sommer schrieb:
> Deswegen macht man ein Template aus dem Baum und dem TreeNode, s.d. man
> immer Referenzen auf die abgeleitete Klasse bekommt.


stimmt, das ging ja auch (schreib eindeutig zuviel C in letzter Zeit):

template <class T>
class TreeNode
{
public:
  T* parent;
  std::vector<T*> childs;
};


class MyData: public TreeNode<MyData>
{
  int a;
};

damit trennt man auch implementierung Tree-Logik und hat trotzdem 
typisierte Pointer.

[Jörg M. (Gast)]

Das gefällt mir. D.h. ich hab erstmal auch einen generischen Container, 
allerdings "besitzt" der Container meine Objekte nicht sondern ich leite 
davon "Container mit Spezialfunktionen und Daten" ab. Diese Objekte 
bringen dann gleich das Baummanagement und die Navigation durch den Baum 
mit.

Ich werd mal sehen ob man das Prinzip auf die bereits erwähnte tree.hh 
anwenden kann, denn dort wär ja bereits eine gute Baum-Implementierung 
vorhanden.

Danke euch!

[Klaus W. (mfgkw)]

Wieso ableiten?

Mit dem template<class T> Tree... kann man doch gleich die Nutzdaten mit 
dem Typ T vorhalten.
Im template weiß man nicht. welche Daten es sind, und hantiert nur mit 
T.

Zur Verwendung leitet man dann nicht ab, sondern macht sich einfach ein:
Tree<MyData>  meinBaum;
und fertig ist der Lack.

Das ist doch der Witz an Templates, daß man nicht mehr davon ableiten 
muß.

[Dr. Sommer (Gast)]

Klaus Wachtler schrieb:
> Zur Verwendung leitet man dann nicht ab, sondern macht sich einfach ein:
> Tree<MyData>  meinBaum;
> und fertig ist der Lack.
Und was macht man dann in der MyData::getFullName -Funktion, die ja die 
Eltern-Elemente kennen muss?
> Das ist doch der Witz an Templates, daß man nicht mehr davon ableiten
> muß.
Von Template abzuleiten und den Typ der abgeleiteten Klasse als 
Template-Paramter zu übergeben ist gar nicht so unüblich und nennt sich 
CRTP.

[Klaus W. (mfgkw)]

Dr. Sommer schrieb:
> Und was macht man dann in der MyData::getFullName -Funktion, die ja die
> Eltern-Elemente kennen muss?

Daß die Kinder ihre Eltern kennen müssen, kann man doch gleich im 
Template vorsehen.

Dr. Sommer schrieb:
> Von Template abzuleiten und den Typ der abgeleiteten Klasse als
> Template-Paramter zu übergeben ist gar nicht so unüblich und nennt sich
> CRTP.

Daß man das machen kann, weiß ich und habe ich auch nie bestritten.

Ich bezweifle nur, daß es hier Sinn macht - das ist etwas ganz anderes.

[Dr. Sommer (Gast)]

Klaus Wachtler schrieb:
> Dr. Sommer schrieb:
>> Und was macht man dann in der MyData::getFullName -Funktion, die ja die
>> Eltern-Elemente kennen muss?
>
> Daß die Kinder ihre Eltern kennen müssen, kann man doch gleich im
> Template vorsehen.
Und wie kommt man in der Member-Funktion von MyData an die Instanz des 
TreeNode<MyData> und damit den Eltern-Pointer? Wenn MyData von 
TreeNode<MyData> ableiten würde, könnte man einfach this->getParent 
machen.

[Jörg M. (Gast)]

Klaus Wachtler schrieb:
> Wieso ableiten?
>
> Mit dem template<class T> Tree... kann man doch gleich die Nutzdaten mit
> dem Typ T vorhalten.
> Im template weiß man nicht. welche Daten es sind, und hantiert nur mit
> T.
>
> Zur Verwendung leitet man dann nicht ab, sondern macht sich einfach ein:
> Tree<MyData>  meinBaum;
> und fertig ist der Lack.
>
> Das ist doch der Witz an Templates, daß man nicht mehr davon ableiten
> muß.

Hast du den ganzen Thread verfolgt?
Wenn ichs so machen würde hätt ich genau wieder das Problem, wegen dem 
ich den Thread eröffnet habe.
Aber das hat Dr. Sommer ja mittlerweile auch klar gestellt.

[Klaus W. (mfgkw)]

Jörg M. schrieb:
> Der Ansatz tut soweit. Allerdings finde ich es unschön, dass eine
> Klasse, die einem bestimmten Zweck dient, gleichzeitig Informationen
> über ihre Anordnung in einem Container-Konstrukt beinhaltet.

Dr. Sommer schrieb:
> Und wie kommt man in der Member-Funktion von MyData an die Instanz des
> TreeNode<MyData> und damit den Eltern-Pointer?

Ihr könnt mich jetzt steinigen, aber:
Wenn eine Methode aus MyData keine Ahnung davon haben soll, daß sie in 
einem Baum steckt, aber andererseits zu ihrem Elternknoten gehen soll, 
steige ich aus, das ist mir heute zu kompliziert.

PS: vielleicht ist das nicht eher ein Problem, WIE man etwas umsetzen 
will, sondern WAS man eigentlich will?