"Container" für beliebig viele Variablen eines beliebigen Types implementieren

[Cherup]

Guten Morgen,

ich versuche mich daran, eine "Container"-Struktur für beliebig viele Variablen eines beliebigen Typs zu implementieren.

Beschreibung:
Aktuell hat die ganze Struktur eine Baum-Form. Jeder Knoten speichert einen Wert, jeder Knotengrad kann die Werte eine Typs speichern und an jeden Knoten können beliebig viele Knoten vom Typ des nächsten Grades angehängt werden.

Der Grund für diese Implementierung ist, dass ich zum üben eine Struktur für IDs der Form (char)(int)(int)(int) (also z.B. P01-31-513) gebaut habe und nun alle IDs in dem Baum speichern möchte.
Ich weiß, ich kanns auch anders lösen, die entsprechenden Operatoren sind für das ID-Struct auch überladen...
Aber ich möchte den Baum am Ende soweit abstrahiert haben, dass ich ihn als eine Art Container benutzen kann um viele Variablen unterschiedlichen Types zu speichern und/oder an Funktionen zu übergeben.

Implementierung:
Dazu nutze ich 2 Klassen: Einmal die Basisklasse TreeNodeBase und die davon abgeleitete Template-Klasse TreeNode mit den Templateparameter T1 und T2.
T1 ist der Datentyp für den aktuellen Knoten, T2 ist der Datentyp für alle angehängten Knoten.
Die Basisklasse ist abstrakt und hat nur rein virtuelle Funktionen.

Der Header-Code schaut bisher so aus:

class TreeNodeBase{
public:
    virtual ~TreeNodeBase() {}
    virtual bool existNode() = 0;
    virtual void pushNewNode() = 0;
    //virtual void getValue() = 0;
    virtual TreeNodeBase* getNode() = 0;
};

template <typename T1, typename T2>
class TreeNode : public TreeNodeBase{
public:
    TreeNode<T1,T2>(T1 value);
    ~TreeNode<T1,T2>();

    bool existNode(T2 value);
    void pushNewNode(TreeNodeBase* node, T2 value);
    T1 getValue();
    TreeNodeBase* getNode(T2 value);

private:
    T1 myValue;
    map<T2, TreeNodeBase*> myNodes;
};

Problem:
1. Offensichtlich kann ich keine neuen Nodes erzeugen, weil die Funktions-Signaturen in TreeNode nicht zu den virtuelen Basisfunktionen passen.
2. Kopfzerbrechen bereitet mir besonders die getValue()-Funktion. Hier ist ja der return-Typ vom T1-Typ der abgeleiteten Klasse abhängig.

Weitere Gedanken/Lösungsansätze:
Ich denke, das ich auf den Parameter T2 verzichten kann, wenn es sein muss.
Ich muss die existNode(T2 value)-Funktion dafür weglassen, die angehängten Knoten als vector speichern und die Suche nach existierenden Knoten anders vornehmen. Die gezielte Rückgabe eines angehängten Knotens wäre dann z.B. über den Index möglich. Es wäre aber schön, wenn ichs doch über die Klasse abfragen könnte bzw mir einen Knoten über den Wert zurückgeben lassen könnte.
Seht ihr da eine Möglichkeit zu? Ich muss ja irgendwie die Funktionssignaturen anpassen.
Gibt es vllt die Möglichkeit, den Parameter der Basisfunktion so zu gestalten, das beim Funktionsaufruf der Datentyp von T2 ermittelt wird? (Ich bin zu 99,9% sicher, dass es nicht geht, die Basisklasse kennt ja T2 nicht, aber fragen schadet ja nicht ).

Grundsätzlich kann ich diese Struktur zum Laufen bekommen, es ist nur nicht gerade angenehm in der Benutzung. Ich nutze dazu die TreeNodeBase-Klasse als quasi leere abstrakte Klasse um einen einheitlichen Datentyp zu haben.
Für die Interessierten, der Header-Code dazu schaut so aus:

class TreeNodeBase{
public:
    virtual ~TreeNodeBase() {}
};

template <typename T1, typename T2>
class TreeNode : public TreeNodeBase{
public:
    TreeNode<T1,T2>(T1 value);
    ~TreeNode<T1,T2>();

    bool existNode(T2 value);
    void pushNewNode(TreeNodeBase* node, T2 value);
    T1 getValue();
    TreeNodeBase* getNode(T2 value);

private:
    T1 myValue;
    map<T2, TreeNodeBase*> myNodes;
};

Den Zugriff auf die Nodes bekomme ich über dynamic_cast.
Wenn ich dann aber z.B. den Wert eines Knotens haben möchte, der an einem Knoten des Startknotens hängt (also eine Reihe aus 3 Knoten), schaut es bereits so aus:

int value = dynamic_cast<TreeNode<int,int>*>(dynamic_cast<TreeNode<int,int>*>(dynamic_cast<TreeNode<char,int>*>(NodeStart)->getNode(1))->getNode(2))->getValue();
//Die Werte 1 und 2 in getNode() sind die gespeicherten Werte der Nodes,
//mit denen sie in der map als key für den Node-Pointer abgespeichert sind

Man stelle sich nur mal vor, man möchte den Wert eines 6. Knotens oder gar eines 15. Knotens haben, da macht der Aufruf schon den halben Programm-Code aus

Noch eine kleine Zusatzbitte: ich bin recht sicher, dass es einen Container für Variablen mit beliebigen Datentypen in der boost-Library gibt (any ist glaube ich die lib), aber ich möchte den Baum selbst implementieren um den Umgang mit templates und Vererbung zu lernen/üben.

Viele Grüße (und vielleicht auch viel Spaß beim Grübeln )
Cherup

[Mechanics]

Die Anforderung ist mir noch nicht ganz klar (und scheint mir jetzt nicht so wiederverwendbar zu sein). Du weißt also, welche Datentypen du auf welcher Ebene haben kannst? Dann ist also auch die Anzahl der Ebenen im Voraus klar?
Wär das dann vielleicht sowas?

Tree<string, int, int, int> tree;

Also, ein Baum mit vier Ebenen mit vorgegebenen Typen? Sowas könnte man vielleicht machen (lohnt sich aber wahrscheinlich nicht).
Oder ist der Typ der Ebene fest, aber quasi dynamisch, weil du einfach Ebenen hinzufügen willst? Also, du hast irgendwo einen Knoten und willst weitere Knoten vom Typ string hinzufügen?
boost::any ist kein tagged union, aber QVariant (aus deinen anderen Beiträge schließe ich, dass du auch Qt benutzt). Mit QVariant könntest du den Typ abfragen. Das wär also vielleicht eine Idee, die Werte nicht über Templates, sondern als QVariants zu speichern. Das wäre wahrscheinlich flexibler, als das was du machen willst. Würde aber die vorgegebene (falls das tatsächlich so ist) Struktur string, int, int, int missachten. Diese Reihenfolge in Baumform zu erzwingen wird aber so oder so schwierig...
Wenn du auch den Container für die Daten selber implementieren willst, das Konzept dahinter nennt sich Type Erasure.

Die Baumknoten würde ich eher verstecken und nur mit Iteratoren arbeiten.

[Cherup]

Danke für deine Antwort,

da hab ich erstmal wieder Aufgaben für Google

Die Anforderung ist relativ simpel: ich möchte eine Struktur haben, in der ich beliebig viele Daten eines beliebigen Typs speichern kann, also eben eine Containerstruktur. Die Datentypen sollen erst zur Laufzeit festgelegt werden und der Container soll jederzeit um eine weitere Schicht mit einem neuen Datentyp erweiterbar sein
Insofern nein, ich weiß nicht welche Datentypen auf welcher Ebene genutzt werden soll und auch die Größe des Baums ist nicht festgelegt.

Die Baumform erschien mir relativ sinnvoll, aber das kann ja auch auf sehr einfache Weise zu einer Liste umgebaut werden.

Wie schon geschrieben, das ganze ist eher zum lernen als für einen konkreten Anwendungsfall. Wobei es durchaus viele sinnvolle Anwendungsmöglichkeiten gibt, z.B. Funktionen, die mehr als 2 Werte mit jeweils unterschiedlichen Datentypen zurückgeben sollen und/oder bei denen die Anzahl der zurückgegebenen Variablen erst zur Laufzeit der Funktion feststeht.

Ich habe einen Artikel zu Type erasure überflogen, das scheint mir vom Konzept her genau das was ich suche. Ich werd mich morgen mal daran machen, die Vorgehensweise und die Vor-und Nachteile des Konzepts zu verstehen und vielleicht schon einen ersten implementierungsversuch machen. Danke nochmal für den Hinweise, das ist ziemlich genau die Art von von Hilfe, die ich bei sowas möchte :). Das Konzept kannte ich noch nicht.

Viele Grüße
Cherup

[Mechanics]

Dann würde ich das Problem erstmal aufteilen. Zum einen brauchst du einen Container für beliebige Daten -> boost::any oder QVariant. Bzw. boost::any hat keine Optimierung für kleine Datentypen, man findet über Google eine Optimierung, die das hat. QVariant hat auch diese Optimierung. D.h., du müsstest dich entscheiden, ob du hier eine fertige Klasse verwenden oder das zum Spass selber schreiben willst.
Das andere Problem wäre dann, daraus einen Baum zu machen. Da würdest du dann keine Templates brauchen, das wären einfach Listen von Zeigern auf die anderen Baumknoten (je nachdem, wie man den Baum aufbaut) und dem Datencontainer.
Du kannst natürlich auch einen generischen Baum mit Templates schreiben, und eine Variante wäre eben der Datencontainer als Templateargument. Einen Baum mit einer schönen API zu schreiben ist auch nicht ganz einfach. Ich würde da wie gesagt die Knoten komplett verstecken und nach außen nur Iteratoren anbieten.

[Cherup]

Danke für die Tipps,

ich werde einen generischen Baum (oder zumindest etwas Baum-artiges )schreiben.
EIne Frage zu boost::any hätte ich: kann das nur mit den Standard-Datentypen (int,string,etc) umgehen oder auch mit Containern wie vectoren, Maps und mit Klassen bzw. Pointern?

QVariant möchte ich nicht nutzen, weil ich es in möglichst reinem C++ haben möchte. Das äußerste der Gefühle ist dabei die boost-Library.

Mechanics schrieb:

du müsstest dich entscheiden, ob du hier eine fertige Klasse verwenden oder das zum Spass selber schreiben willst.

Meinst du damit QVariant = Fertige Klasse und boost::any = Klasse selber schreiben?
Falls ja würde ich mich schon aus dem Grund für any entscheiden, ich mache das ja zum lernen und aus Spaß am Programmieren und dem kreativen arbeiten.

Mechanics schrieb:

Einen Baum mit einer schönen API zu schreiben ist auch nicht ganz einfach.

Genau deshalb will ichs machen, ich will lernen
Ganz abgesehen davon muss ich mir endlich mal nen vernünftigen Programmierstil angewöhnen, das was ich schreibe ist manchmal eher Kot statt Code

Die Knoten zu verstecken und nur mit iteratoren zu arbeiten erscheint mir sehr sinnvoll. Damit sind die Daten und die interne Struktur vollständig gekapselt.

Und an dieser Stelle nochmal ein großes Lob für deine guten Hilfestellungen nicht nur hier sondern auch bei meinen anderen Problemen, finde ich absolut Top
Schönen Abend
Cherup

[Mechanics]

QVariant und boost::any wären beides fertige Klassen. Selber schreiben heißt selber schreiben boost::any kann mit beliebigen Daten umgehen. Das ist auch nicht so schwer, das kann man auch selber schreiben, wenns einem Spass macht. Beide Ansätze (QVariant und any) haben Vor- und Nachteile, da muss man schauen, was einem besser passt.

[Cherup]

Hmm,

ich würde es sehr gerne selber schreiben, aber mir fehlt der Ansatz.
Ich habe ja an sich genau das mit der TreeNode Klasse versucht.
Ich brauche eine abstrakte Basisklasse, um einen einheitlichen Datentyp zu haben, der ohne Parameter auskommt und eine abgeleitete templete-Klasse, in der die Variable gespeichert wird. Nur habe ich dann eben das Problem mit der Typunabhängigen virtuellen Rückgabefunktion.
Es sein denn... das soll(te) sich ja durch das Type Erasure Konzept lösen lassen.

Wäre dieser Ansatz korrekt oder gibt es noch andere/bessere?

[Mechanics]

Schau dir einfach an, wie boost::any funktioniert, das ist wirklich nicht viel Code.

[Cherup]

So,
ganze grundlegend läuft es schonmal, hab mich dabei an der Struktur von any orientiert.
Wo ich gerade hänge ist die typ-Info der gespeicherten Variable und die Suche oder Iteratorrückgabe von Knoten eines bestimmten Typs.

Ich möchte über eine Funktion den Datentyp der gespeicherten Variable abfragen und zurückgeben. Möglichst so, dass ich sie zum casten oder als templateparameter nutzen kann.

Fragen:
1.1: geht das auf einfache/unkomplizierte Weise mit Standard-C++ (c++11) oder geht es besser mit boost?

Falls Standard-C++:
1.2: ist es möglich den Datentyp über eine Funktion zurückzugeben und als cast parameter zu nutzen?

1.3: Ich kann mit typeid() den Typ auslesen oder 2 Datentypen vergleichen, aber welchen Rückgabetyp hat typeid bzw. hat es überhaupt einen?

Das Konzept des Container entspricht jetzt einer zweidimensionalen Liste (ist aber variabel, ein Baum ist auch möglich). Die Knoten werden in einem vector<vector<TreeNode*>> gespeichert.
Die erste Dimension entspricht dem Datentyp und alle Knoten des gleichen Datentyps werden an der entsprechenden Stelle angehängt.
Um z.B. einen iterator über die Knoten eines bestimmten Datentyps zu erhalten soll der Datentyp der getNodeIterator-Funktion mitgeteilt werden.
Über eine interne Liste wird dann der vector-index für die ensprechenden Knoten ermittelt.

Die Frage dazu ist, ob das Konzept sinnvoll ist oder ob es auch einfacher/besser geht?
Insbesondere geht es mir um die Liste mit den Indices der Datentypen.

Viele Grüße
Cherup

[Mechanics]

typeid gibt eine std::type_info zurück. In dem Kontext ist auch std::type_index interessant.

Das ist auch das, was du als "Typ" abfragen könntest, gibts auch in any. Das ganze ist aber relativ langsam. QVariant macht es eben so, dass zusätzlich ein int für den Typ gespeichert wird, und es gibt vordefinierte Typen wie QVariant::Int usw. und du kannst dir einen Wert für deine Typen registrieren lassen. Das ist aber eben der Nachteil, man muss die eigenen Typen registrieren. Wenn man aber häufig die Info über den Typ braucht und nicht weiß, was drinsteckt, dann lohnt sich das wahrscheinlich im Vergleich zu typeid.

Casten und Templateparameter und Laufzeitdynamik passt grundsätzlich nicht zusammen. Du weißt nicht, was in dem Node ist. Du kannst einfach dynamisch da irgendwas rausholen und darauf casten. Was du z.B. machen könntest, wäre den typ zu prüfen, z.B. if (container.type() == typeid(int)), dann weißt du, da ist ein int drin und du kannst was damit anfangen. Oder du speicherst dir irgendwie eine map type_index auf Funktonszeiger, dann brauchst du keine hartkodierten Vergleiche in der Form. Kommt stark drauf an, was du brauchst
Qt macht das auch etwas anders und hat viele Konvertierungsfunktionen, z.B. QVariant::toInt. Da drin wird geprüft, was im Variant steckt und viele Typen können in einen int konvertiert werden, nicht nur, wenn da tatsächlich nur ein int ist. Und man könnte auch eigene Konvertierungen registrieren (früher konnte man den Variant Handler überschreiben, war aber ein ziemlicher Hack, irgendwann in Qt 5 sollte das einfacher gehen, hab ich mir noch nicht angeschaut).

Zweidimensionale Liste hört sich nicht wirklich sinnvoll an, außer du brauchst eben eine zweidimensionale Liste

[Cherup]

Das hat mir schonmal weitergeholfen

Ich habe jetzt eine Type-Variable in jedem Node, in der beim Konstruktoraufruf der Typ der Content-Variable gespeichert wird.
Außerdem natürlich eine getType-Funktion.
Dadurch kann ich alle Nodes gut in einer Map (map<type_info*,vector<TreeNode*>> speichern und kann damit vorläufig alle Managment-Funktionen realisieren.
An sich brauche ich keinen cast mit einem zur Laufzeit ermittelten Typ (was ja auch nicht möglich ist, wie ich gelernt habe :)).
Grundsätzlich kennt man ja die Datentypen der gespeicherten Variablen.

Ich werde mich mal an die implementierung der Container-Klasse machen, die Node-Klasse sollte halbwegs fertig ein.

Ach ja, fällt jemandem vielleicht ein guter Name für den Container ein? Bin grad furchtbar unkreativ

VG
Cherup

[Cherup]

So,

hab die Container-Klasse grundlegend implementiert (ich hoffe halbwegs richtig ;)), werd aber noch weiter daran feilen... Der Compiler spuckt keine Fehler aus.

Jetzt habe ich zum testen mal einen neuen Container erstellt und wollte ihn mit ints befüllen. Das Ergebnis war die Fehlermeldung
"error: undefined reference to `void TreeNodeBase::insert<int>(int)'"

Ich sehe aber keinen Fehler bei der Implementierung (wahrscheinlich irgendwas blödes... ).

Ich hoffe ihr könnt mir weiterhelfen.

Der (reduzierte) Code der Header-Datei:

class TreeNodeBase{
private:
    class TreeNode;

//structors
public:
    TreeNodeBase();
     ~TreeNodeBase();

//functions
public:
    template<typename T> void insert(T value);
    template<typename T1, typename T2> void insert(T1 value, T2 description);

//Classes
private:
    class TreeNode{
    (...)
    };

//Storage
private:
    std::map<std::type_info*, std::vector<TreeNode*>> myNodes;
};

Die dazu gehörenden Funktionen der .cpp:

template<typename T> void TreeNodeBase::insert(T value)
{
    myNodes[const_cast<std::type_info*>(&typeid(T))].push_back(new TreeNode(value));
}
template<typename T1, typename T2> void TreeNodeBase::insert(T1 value, T2 description)
{
    myNodes[const_cast<std::type_info*>(&typeid(T1))].push_back(new TreeNode(value,description));
}

und der Aufruf der insert-Funktion:

TreeNodeBase* myContainer = new TreeNodeBase();
for(int i=0; i<10; i++) myContainer->insert(i); //Fehler
delete myContainer;

Kann man eigentlich das

const_cast<std::type_info*>(&typeid(T))

mit einem Alias versehen? Es ist aufwändig zu schreiben und von der Übersicht will ich gar nicht sprechen...

Wenn das soweit läuft würde ich gern mal eure Meinung zum gesamten Code lesen, wahrscheinlich lässt sich an 1000 Ecken noch was verbessern oder Mist beseitigen.

Viele Grüße und schönen Feiertag
Cherup

[patrick246]

Implementierungen von Funktionstemplates müssen in die .h-Datei.

[Cherup]

Danke, läuft.

Dann werd ich mal durchtesten und evtl noch n bissel was weiterentwickeln.

VG
Cherup

[camper]

Cherup schrieb:

Kann man eigentlich das

const_cast<std::type_info*>(&typeid(T))

mit einem Alias versehen?

Wieso nicht gleich const std::type_info* als map-key? Abgesehen davon ist das sowieso falsch, weil verschiedene typid-Ausdrücke, die sich auf den gleichen Typ bezieht, nicht zwingend das gleiche Objekt liefern.
Für solche Zwecke gibt es std::type_index.

[Cherup]

Vielen Danke für den Hinweis, das hat eine Menge Probleme gelöst, vor allem bei den Iterator-Funktionen

Ich wußte nicht, das typeid für gleiche Datentypen nicht immer den gleichen Wert liefern. Und ich kannte type_index einfach nicht

Viele Grüße
Cherup

[Cherup]

Ok, eine vielleicht noch etwas dumme Frage zu type_index:
Ich möchte den Datentyp des gespeicherten Wertes speichern um sie für Vergleiche zu nutzen. Eine direkte Abfrage ist nicht möglich, weil ich dafür den Typ kennen muss.
Offenbar kann zumindest ich keine Variablen vom Typ type_index deklarieren.
Da type_info ja ungeeignet ist, ist die Frage:

Wie speichere ich sinnvoll den Datentyp?

Mein Lösungsansatz wäre:
Ich hole mir den Hash-Code von type_index und speichere ihn (Typ ist size_t).

Ist das sinnvoll oder gibt es eine bessere Lösung?

Ich habe auch noch ein "kleines" Problem mit den vector-Iteratoren, aber dazu komme ich später.

Viele Grüße
Cherup

[Mechanics]

type_index habe ich ja zusammen mit type_info erwähnt.

Für so einen Vergleich ist type_info schon ok.

[Cherup]

hmm, das type_index hab ich dann wohl mit type_info verwechselt
Wie auch immer, das läuft jetzt.

Daher komm ich jetzt zu den Iteratoren Die Laufen zwar an sich auch, ich habe aber eine Unannehmlichkeit mit den Node-Iteratoren.

Kurze Implementierungserklärung:
Ich stelle 4 Iteratoren bereit, einen um über die map zu iterieren ("list_iterator") und einen für den vector in einem map pair ("node_iterator"), jeweils als const und normale Variante. Für jeden Iterator habe ich eine begin() und end() Funktion.
Die begin() und end() Funktionen der node_iteratoren sind jeweils 4 mal überladen und übernehmen entweder einen template-typ an, eine type_info oder einen const_list_iterator/list_iterator. Ich muss ja wissen, über welchen vector ich iterieren will.

Wenn ich einen node-iterator bekomme, muss ich immer mit (*it_node)->TuWas() bzw (*it_node)->TuWas<T>() darauf zugreifen, das nervt etwas und erschwert zumindest für mich das Code-Verständnis.

Ich gebe mal etwas Beispiel-Code:

//Deklaration
class TreeNodeBase{
public:
    typedef std::vector<TreeNode*>::iterator node_iterator;
    typedef std::vector<TreeNode*>::const_iterator const_node_iterator;
    typedef std::map<std::type_index, std::vector<TreeNode*>>::iterator list_iterator;
    typedef std::map<std::type_index, std::vector<TreeNode*>>::const_iterator  const_list_iterator;

    template<typename T> node_iterator begin();
    node_iterator begin(std::type_index type);

    const_node_iterator begin(std::type_index type) const;

    template<typename T> node_iterator end();
    node_iterator *end(std::type_index type);

    list_iterator begin();
};

//Definition
template<typename T> TreeNodeBase::node_iterator TreeNodeBase::begin(){ return myNodes[typeid(T)].begin(); }
TreeNodeBase::node_iterator TreeNodeBase::begin(std::type_index type){ return myNodes[type].begin(); }

TreeNodeBase::const_node_iterator TreeNodeBase::begin(std::type_index type) const{ return begin(type); }

template<typename T> TreeNodeBase::node_iterator TreeNodeBase::end(){ return myNodes[typeid(T)].end(); }
TreeNodeBase::node_iterator TreeNodeBase::end(std::type_index type){ return myNodes[type].end(); }

TreeNodeBase::list_iterator TreeNodeBase::begin(){ return myNodes.begin(); }

//Iterieren durch <int>-Nodes:
vector<int> myints; //Bloß zum speichern, myContainer ist eine Instanz des Containers
for(auto it=myContainer->begin(typeid(int)); it!=myContainer->end<int>(); ++it){
    myints.push_back((*it)->getValue<int>()); //Hier ist das (*it)
}

Ich bin sicher, dass man den iterator irgendwie besser zurückgeben kann, aber wie?
Und ist diese Art der Implementierung gut/sinnvoll?

Viele Grüße
Cherup

[Mechanics]

Naja, du reichst die internen Iteratoren von vector usw. raus. Du kannst die ja in eigene Iteratorobjekte kapseln, die du dann nicht referenzieren müsstest.
Ich hätt mir von der API her evtl. sowas wie adobe forest vorgestellt:

http://stlab.adobe.com/group__asl__tutorials__forest.html