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



  • 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



  • Es fällt mir eh schwer, in deinem Design durchzublicken und es mir immer noch / wieder nicht mehr klar, was du eigentlich willst ^^
    Du wolltest ja ursprünglich sowas wie einen Baum, jetzt hast aber irgendwie den Typ als Map Index... Also musst du vor allem selber mit deinem Code zurechtkommen können 😉

    Iteratoren habe ich vor allem ins Gespräch gebracht, als es noch um einen Baum ging. Ein Baum ist eben eine baumartige Anordnung von Werten. Das geht aber nicht, du brauchst noch zusätzlich Metadaten, deswegen braucht man also Tree Nodes. Die sollten den Benutzer aber nicht interessieren. Der Benutzer sollte möglichst nur mit den eigentlichen Werten arbeiten und nicht die Internas der Baumstruktur manipulieren können. Also holt man sich einen Iterator, z.B. Post Order oder Pre Order, und arbeitet mit dem. Dann kann der Benutzer z.B. sagen, er will an der Iteratorposition ein neues Element einfügen. Alles versteckt, man sieht nie irgendwelche TreeNodes, kann sie nicht anlegen oder löschen. Ich sprech da mehr oder weniger aus Erfahrung, ich hab mal nebenbei so eine Baumstruktur hingerotzt und da sind die TreeNodes Teil der public API, das gefällt mir überhaupt nicht. Das war also die Intention hinter den Iteratoren, obs bei dir noch die beste Lösung ist, weiß ich nicht.

    Es ist ok, wenn der Iterator nur einen Zeiger bekommt und den kapselt. Der muss nicht gültig sein, wenn der Baum nicht mehr gültig ist. Da brauchst auch keine smart pointer und musst dir auch keine Gedanken über Kopien machen.



  • Ok, also passt das Design 🙂
    Was ich will ist relativ simpel:
    einen Container, der beliebig viele Werte eines beliebigen Typs speichern kann, und das um des Lerneffekts willen möglichst komplett selbstgeschrieben.

    Das Design mit der map habe ich jetzt erstmal gewählt um einen allgemeinen Container zu haben (Baum ist ja etwas spezieller) und weil ich mit maps und vectoren mehr Erfahrung habe als mit Bäumen.
    Wenn der "Standard"-Container soweit fertig ist, will ich ihn dahingehend erweitern, dass er auch (aber nicht nur) eine Baum-Struktur annehmen kann.
    So hab ich also zwei in einem: einen "Any-Container" und einen "Any-Tree" in einer Klasse 🙂

    Das Problem mit den Iteratoren bezieht sich im wesentlichen darauf, dass es etwas nervt die vector-iteratoren dereferenzieren zu müssen und das gleichzeit (aus meiner Sicht) zuviel vom Innenleben preisgegeben wird.

    Schönen Abend
    Cherup



  • So,
    ich habe mal mehr oder weniger zum lernen einen Iterator geschrieben und den ganzen Container in train umbenannt (man kann alles mögliche darin durch die Gegend verfrachten und er kann recht groß werden 😉 ), die Nodes heißen jetzt waggon. Ich bin ja wieder sooo kreativ 😃
    Die Erweiterung zum Tree und zur List stehen noch aus.

    Ich würde mich freuen, wenn ihr euch den Code mal anschaut, mir eure Meinung dazu sagt und Verbesserungsvorschläge gebt.

    Da ich hier aber eher ungern 550 Zeile Code posten möchte ist noch die Frage, wo ich den Code am besten hochlade...
    copyCode.de ist nicht so gut geeignet, die Code-Anzeige ist einfach zu schmal.
    Ist ideone.com besser? An sich brauchts ja keinen online-Compiler...

    Viele Grüße
    Cherup


Anmelden zum Antworten