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



  • 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.



  • 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



  • 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.



  • 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?



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



  • 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



  • 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 😉



  • 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



  • 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



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



  • Danke, läuft.

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

    VG
    Cherup


  • Mod

    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.



  • 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



  • 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



  • type_index habe ich ja zusammen mit type_info erwähnt.

    Für so einen Vergleich ist type_info schon ok.



  • 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



  • 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



  • Mechanics schrieb:

    Ich hätt mir von der API her evtl. sowas wie adobe forest vorgestellt:

    Das liest sich ja fast etwas enttäuscht 😃
    Kommt aber noch, etwas in der Art ist mein Ziel. Ich finde die map<type_index, vector<>>-Struktur noch etwas einfacher/übersichtlicher. Wenn die läuft möchte ich den Container dahingehend erweitern, dass man im Konstruktor über einen Parameter auch eine Baumstruktur wählen kann.
    Wie genau ich die Nodes dann anfüge muss ich mir noch überlegen. Auf jedenfall wird man einen neuen Node auch explizit an einen anderen anhängen können.
    Aber das ist noch Zukunftsmusik, jetzt möchte ich erstmal die Iteratoren gut benutzbar machen.

    Mechanics schrieb:

    Du kannst die ja in eigene Iteratorobjekte kapseln, die du dann nicht referenzieren müsstest.

    Meinst du damit eine simple Klasse mit Operatoren, die nur jeweils die Iteratoroperationen weiterreichen?

    Schönen Restabend
    Cherup



  • Cherup schrieb:

    Meinst du damit eine simple Klasse mit Operatoren, die nur jeweils die Iteratoroperationen weiterreichen?

    Naja, schau dir die Beispiele auf der verlinkten Seiten an. Vielleicht kann man das noch einfacher machen, z.B. den Zuweisungsoperator mit dem jeweiligen Templatetyp überladen usw.



  • So,
    das meiste vom "Standard"-Container sollte fertig sein, die Funktionen sind grundlegend getestet. Ich hänge nur immernoch bei den Iteratoren. Die funktionieren zwar auch, aber ich möchte ja auf die Nodes (bzw. die Node-Funktionen) zugreifen können ohne dereferenzieren zu müssen.
    Ich habe mir mal das verlinkte Beispiel angeschaut, da wird ja für jeden Iterator eine eigene Klasse erstellt. Furchtbar viel Schreibaufwand aber Ok... :).

    Jetzt habe ich aber mal wieder ein Brett vorm Kopf oder besser nen ganzen Stapel.

    Zuerst mal das Design der Iteratorklasse: ich brauche eine Referenz auf den vector in der Speichermap und einen Pointer auf das aktuelle Element, soweit richtig?
    Neben den ganzen begin() und end() Funktionen brauche ich auch die Operator-Funktionen. Ausserdem die Zugriffsfunktionen für die Funktionen der Nodes, in denen ich den Pointer quasi dereferenziere, auch richtig?
    Mal ein schnell dahingeschriebenes Beispiel:

    class node_iterator
    {
    public:
        node_iterator();
        node_iterator(std::vector<TreeNode>* ref) : myVector(ref), myPointer(myVector->begin()) {}
    
    //begin und end-Funktionen (...)
    //Operatoren (...)
    
    //Zugriffsfunktionen
    template<typename T> T getValue(){ return myPointer->getValue<T>(); }
    //(...)
    
    private:
    vector<TreeNode*>* myVector;
    TreeNode* myPointer;
    

    Dann stellt sich mir noch die Frage, wie ich am besten eine Instanz des Node_Iterators erstelle. Wenn ich einfach "return Node_Iterator it(...)"(Konstruktoraufruf) zurückgebe, wird dann eine neue Instanz erstellt oder nur bei new? Bin grad etwas verwirrt 😃
    Und dann noch die Lebensdauer... Ich will den Node_Iterator ja zum einen an andere Funktionen übergeben können und möchte ihn nicht manuel löschen müssen. Wäre es da nicht am besten einen smart-Pointer auf Node_Iterator zurückzugeben?

    Ich weiß, die letzten Fragen sind eigentlich Anfängerfragen, aber irgendwie blick ich da grade nicht durch 😕

    Schönen Tag noch
    Cherup


Anmelden zum Antworten