Baum mit unique_ptr?



  • Hallo,

    angenommen ich habe einen einfachen Interpreter wie hier (kann Ausdrücke addieren):

    #include <iostream>
    
    struct Node
    {
    	virtual int eval() = 0;
    };
    
    struct NodeValue : Node
    {
    	int value;
    	NodeValue(int value) : value(value) {}
    	virtual int eval() { return value; }
    };
    
    struct NodeAdd : Node
    {
    	Node *left, *right;
    	NodeAdd(Node *left, Node *right) : left(left), right(right) {}
    	virtual int eval() { return left->eval() + right->eval(); }
    };
    
    int main()
    {
    	Node *node = new NodeAdd(new NodeValue(2), new NodeValue(5));
    	std::cout << node->eval() << "\n"; // 2 + 5 = 7
    }
    

    Das funktioniert soweit (ist mehr oder weniger das selbe wie aus dem Interpreterbau Tutorial).

    Problem ist natürlich dass das so ein Memory Leak ist, da der Speicher nicht wieder freigegeben wird.
    Deswegen würde ich das gerne auf unique_ptr umstellen um das automatisiert aufgeräumt zu bekommen. Mein Versuch:

    #include <iostream>
    #include <memory>
    using namespace std;
    
    struct Node
    {
    	virtual int eval() = 0;
    };
    
    struct NodeValue : Node
    {
    	int value;
    	NodeValue(int value) : value(value) {}
    	virtual int eval() { return value; }
    };
    
    struct NodeAdd : Node
    {
    	unique_ptr<Node> left, right;
    	NodeAdd(unique_ptr<Node> left, unique_ptr<Node> right) : left(move(left)), right(move(right)) {}
    	virtual int eval() { return left->eval() + right->eval(); }
    };
    
    int main()
    {
    	auto node = unique_ptr<Node>(new NodeAdd(unique_ptr<Node>(new NodeValue(2)), unique_ptr<Node>(new NodeValue(5))));
    	std::cout << node->eval() << "\n"; 
    }
    

    Das funktioniert auch, allerdings habe ich ein paar Fragen/Zweifel:

    • Wird hier sämtlicher Speicher korrekt wieder aufgeräumt?
    • Wieso kann ich den unique_ptr überhaupt per Value an den Konstruktor von NodeAdd übergeben? Das move findet ja erst in der Initializer-List "statt", um überhaupt dahin zu kommen müsste doch erstmal eine Kopie des Pointers erstellt werden?
    • Wenn ich node an eine Funktion übergeben will, muss ich selbigen moven. Soweit so gut, aber ich würde jetzt gerne einen Functor um node wrappen, sodass ich diesen wie eine normale Funktion benutzen kann. Dazu würde ich den auch gerne einfach zwischen Funktionen hin und hergeben können ohne mir um move Gedanken machen zu müssen (wie einen std::vector z.B.). Wie macht man das am geschicktesten?


  • 1. Ja. Solange du nicht release aufrufst und den Rückgabezeiger fallen lässt, ist alles sicher.
    2. In zeile 26 erstellst du ein temporäres unique_ptr-Objekt, welches eine rvalue-Referenz ausbildet, wie das bei allen temporären Objekten der Fall ist. Diese wird an den Movekonstruktor vom unique_ptr-Argument gegeben.
    3. Wenn du Objekte an Funktionen übergibst, reicht eine übliche const-Referenz auf das Objekt.



  • happystudent schrieb:

    • Wird hier sämtlicher Speicher korrekt wieder aufgeräumt?

    Nicht, wenn eine Exception auftritt. Ein Compiler darf den Ausdruck zum Beispiel in dieser Reihenfolge auswerten:

    unique_ptr<Node>(new NodeAdd(unique_ptr<Node>(new NodeValue(2)), unique_ptr<Node>(new NodeValue(5))))
                                                  1111111111111111
    											                     2222222222222222222222222222222222
    							 3333333333333333333333333333333333
    

    Wenn das zweite new wirft, wird das Ergebnis des ersten nie freigegeben, weil der unique_ptr noch nicht konstruiert worden ist.
    Um dieses Problem zu vermeiden, benutzt man make_unique :

    std::make_unique<NodeAdd>(std::make_unique<NodeValue>(2), std::make_unique<NodeValue>(5))
    


  • happystudent schrieb:

    Wenn ich node an eine Funktion übergeben will, muss ich selbigen moven. Soweit so gut, aber ich würde jetzt gerne einen Functor um node wrappen, sodass ich diesen wie eine normale Funktion benutzen kann. Dazu würde ich den auch gerne einfach zwischen Funktionen hin und hergeben können ohne mir um move Gedanken machen zu müssen (wie einen std::vector z.B.). Wie macht man das am geschicktesten?

    unique_ptr liefert mit get einen ganz normalen Pointer. Wenn du nicht den Besitzt weitergeben willst, solltest du das verwenden.



  • Der Destruktor ist nicht virtuell.



  • Kleine Randfrage zu den Exceptions bei new

    TyRoXx schrieb:

    happystudent schrieb:

    • Wird hier sämtlicher Speicher korrekt wieder aufgeräumt?

    Nicht, wenn eine Exception auftritt.[...]

    Wenn bei new eine Exception auftritt, dann ist doch eh schon alles zu spät oder? In welchem Anwendungsfall interessiert mich das den?

    Angenommen ich hab ein Programm, bei einer Allokation wird eine Exception geworfen. Meine Annahme ist die Exception wird nur geworfen da mein Rechner aktuell total am Anschlag ist und kein weiterer Speicher mehr zur Verfügung steht. Somit ist auch ein sinnvoller Programmablauf (aus meiner Sicht) nicht mehr möglich, da jede weitere Allokation auch nicht mehr möglich ist. Und somit bleibt doch nur noch der Programmcrash und das Betriebssystem räumt anschließend den Speicher auf.

    Drei Rückfragen:
    (1) Behandelt ihr die mögliche Exceptions die bei "new" auftreten könnten?
    (2) Aus welchem Grund macht ihr das?
    (3) Gibt es dann noch einen sinnvollen Programmablauf?



  • 1 Ja
    2 s.u.
    3 Vermutlich nicht

    2...
    Es macht einfach keinen Sinn sich an jeder 2. Stelle zu überlegen "kann ich hier rumsauen"? Weil es mühsam ist. Wenn ich gleich überall sauber programmiere spare ich mir die Überlegung.
    Und weil man viel zu schnell in Richtung "zu oft rumsauen" driftet. Und dann an Stellen rumsaut wo es doch nicht OK gewesen wäre. Weil halt was übersehen hat und der Fall den man für "kann eh nicht sein" gehalten hat doch vorkommen kann. Oder sich vielleicht auch irgendwo die Regeln geändert haben.
    Und weil es mMn. dämlich ist mal-so, mal-so zu programmieren. Wozu sollte ich die "Fähigkeit" unsauber zu programmieren trainieren? Was bringt mir die?

    Weitere Argument dafür Exceptions "bei new" zu behandeln:

    • bad_alloc ist nicht das einzige was bei new T() fliegen kann. Wenn T ne Klasse ist, dann kann der Konstruktor beliebige Exceptions aus beliebigen Gründen werfen. Und so Sachen wie "File not Found" sind jetzt weder selten noch "unbehandelbar".

    * Wenn bei new int[Ein paar Billionen] nen bad_alloc fliegt ist normalerweise noch gar nix "total am Anschlag", und das Programm kann normal weiterlaufen. Der Versuch z.B. in einem Bildbearbeitungsprogramm ein Bild auf die 10-fache Grösse zu skalieren sollte mMn. nicht dazu führen dass ich das Bildbearbeitungsprogramm neu starten muss wenn ich ohne Fehler weiter arbeiten möchte.



  • jb schrieb:

    Kleine Randfrage zu den Exceptions bei new

    TyRoXx schrieb:

    happystudent schrieb:

    • Wird hier sämtlicher Speicher korrekt wieder aufgeräumt?

    Nicht, wenn eine Exception auftritt.[...]

    Wenn bei new eine Exception auftritt, dann ist doch eh schon alles zu spät oder? In welchem Anwendungsfall interessiert mich das den?

    Angenommen ich hab ein Programm, bei einer Allokation wird eine Exception geworfen. Meine Annahme ist die Exception wird nur geworfen da mein Rechner aktuell total am Anschlag ist und kein weiterer Speicher mehr zur Verfügung steht. Somit ist auch ein sinnvoller Programmablauf (aus meiner Sicht) nicht mehr möglich, da jede weitere Allokation auch nicht mehr möglich ist. Und somit bleibt doch nur noch der Programmcrash und das Betriebssystem räumt anschließend den Speicher auf.

    Drei Rückfragen:
    (1) Behandelt ihr die mögliche Exceptions die bei "new" auftreten könnten?
    (2) Aus welchem Grund macht ihr das?
    (3) Gibt es dann noch einen sinnvollen Programmablauf?

    Deine Beschränkung auf SPEICHER ist javaesk.

    Das delete ruft einen Destruktor auf, der eine im Keller stehende aus Versehen aktivierte Atombombe entschärft. Außerdem werden die Datenbankverbindungen geschlossen, damit der Server sie nicht noch sinnlose 300 Sekunden offen läßt. Und einer der Destruktoren bestellt mir eine Pizza und siehe, ich war nicht mehr hungrig.
    Bald wird der Baum ausgebaut und kann mehr als nur ints verwalten. Auch vielleicht DEatenbankverbindungen. new Node ruft dabei einen Konstruktor auf, der eine Datenbabnkverbindung öffnet, aber im Fehlerfall eine Exception wirft. Also muss man die Exceptions aus new doch behandeln!



  • hustbaer & volkard, vielen Dank für Eure Antworten.
    Ja, ich hab mich nur auf bad_alloc beschränkt. Wenn T irgendwas werfen kann (FileNotFound o.ä.), dann ist es klar das eine sinnvolle Abarbeitung im Programm weiterhin möglich ist/sein sollte.



  • Der grösste Teil meines Beitrages gilt auch wenn es nur um bad_alloc geht.



  • Hallo,

    Danke schonmal für die Antworten. Ich habe den Code jetzt mal abgeändert und versucht die Vorschläge entsprechend umzusetzen:

    #include <iostream>
    #include <memory>
    using namespace std;
    
    struct Node
    {
    	virtual int eval() = 0;
    	virtual unique_ptr<Node> copy() = 0;
    	virtual ~Node() {}
    };
    
    struct NodeValue : Node
    {
    	int value;
    	NodeValue(int value) : value(value) {}
    	virtual int eval() { return value; }
    	virtual unique_ptr<Node> copy() { return unique_ptr<Node>(new NodeValue(value)); }
    };
    
    struct NodeAdd : Node
    {
    	unique_ptr<Node> left, right;
    	NodeAdd(unique_ptr<Node> left, unique_ptr<Node> right) : left(move(left)), right(move(right)) {}
    	virtual int eval() { return left->eval() + right->eval(); }
    	virtual unique_ptr<Node> copy() { return unique_ptr<Node>(new NodeAdd(left->copy(), right->copy())); }
    };
    
    struct Func
    {
    	unique_ptr<Node> node;
    
    	Func(unique_ptr<Node> node) : node(move(node)) {}
    	Func(Func const &other) : node(other.node->copy()) {}
    	Func &operator=(Func const &other) { if (this != &other) { node = other.node->copy(); } return *this; }
    	int operator()(){ return node->eval(); }
    };
    
    void foo(Func func) // Copy
    {
    	Func tmp = func; // Copy asign
    	std::cout << tmp() << "\n";
    }
    
    int main()
    {
    	auto node = make_unique<NodeAdd>(make_unique<NodeValue>(2), make_unique<NodeValue>(5));
    
    	Func func(move(node));
    
    	foo(func);
    }
    

    Passt das so, oder gibt es da noch irgendwelche Probleme die ich übersehen habe?

    Ein potentielles Problem ist wahrscheinlich das ich in der copy Methode nach wie vor new nutze, aber ich weiß nicht wie ich das vermeiden soll. Das Problem ist ja dass wenn ich Node als template-Parameter an make_unique übergebe, ich dann nicht sagen kann welchen Node ich jetzt erstellen will, da ich nur den Konstruktor von Node zur Verfügung habe (was ja so gar nicht erstellt werden kann, da pure virtual).

    Gebe ich aber statt dessen NodeAdd / NodeValue als template Parameter an make_unique , stimmt der Rückgabetyp der Methode nicht mit dem geforderten Rückgabetyp der rein virtuellen Methode copy überein, und es kompiliert (logischerweise) nicht.

    Anscheinend lässt sich ein smart pointer nicht wie ein raw pointer implizit in einen base pointer konvertieren... (kann mich dunkel erinnern damit schonmal Probleme gehabt zu haben).

    Deswegen meine Frage(n): Passt das so und wie würdet ihr das oben genannte Problem angehen?



  • Die verbleibenden new bekommst du so weg:

    //...
        //virtual unique_ptr<Node> copy() { return unique_ptr<Node>(new NodeValue(value)); }
        virtual unique_ptr<Node> copy() { return make_unique<NodeValue>(value); } 
    //...
        //virtual unique_ptr<Node> copy() { return unique_ptr<Node>(new NodeAdd(left->copy(), right->copy())); }
        virtual unique_ptr<Node> copy() { return make_unique<NodeAdd>(left->copy(), right->copy()); } 
    //...
    

    GCC 5.2 kompiliert das fehlerfrei, und ich gehe auch davon aus dass es standardkonform ist.

    Diese beiden new sind zwar auch so unproblematisch, aber alleine schon weil ich mir über sowas gar keine Gedanken machen will, würde ich die make_unique Variante vorziehen.

    ps: Hat mit deiner Frage nix zu tun, aber überleg dir ob du die Benennung der Klassen so beibehalten willst. Ich schreibe Bezeichner in Programmen gerne so wie auch zusammengesetzte Hauptwörter funktionieren. Also so dass ein Schäferhund ein Hund ist und kein Schäfer. Demnach müssten deine Klassen dann ValueNode und AddNode heissen.
    Muss man nicht so machen, aber ich find's angenehmer zu lesen.
    Ich hab' auch den Eindruck dass diese Art der Benamsung wesentlich weiter verbreitet ist als anders rum.



  • hustbaer schrieb:

    Die verbleibenden new bekommst du so weg:
    ...
    GCC 5.2 kompiliert das fehlerfrei, und ich gehe auch davon aus dass es standardkonform ist.

    Stimmt, das kompiliert ja auch bei mir (VS 2013)... da hatte sich anscheinend nur Intellisense aufgehängt - das hat als Fehler folgendes gebracht:

    return type is not identical to nor covariant with return type "std::unique_ptr<Node, std::default_delete<Node>>" of overridden virtual function "Node::copy"

    Aber dann scheint das ja trotzdem zu funktionieren, das ist dann natürlich optimal (Merke an mich: nicht auf Intellisense verlassen sondern immer richtig kompilieren 🤡 ).

    hustbaer schrieb:

    ps: Hat mit deiner Frage nix zu tun, aber überleg dir ob du die Benennung der Klassen so beibehalten willst. Ich schreibe Bezeichner in Programmen gerne so wie auch zusammengesetzte Hauptwörter funktionieren. Also so dass ein Schäferhund ein Hund ist und kein Schäfer. Demnach müssten deine Klassen dann ValueNode und AddNode heissen.

    Ja das hatte ich mir auch schonmal überlegt, aber das Problem ist dann dass die im Intellisense nicht mehr zusammen aufgelistet werden... Also ich find es praktisch wenn man dann z.B. alle Nodes hintereinander in der Autocomplete Liste hat.



  • Hattest du vielleicht versucht als Returntyp unique_ptr<NodeValue> zu verwenden?

    Das geht natürlich nicht, weil virtual sich nicht darum kümmert was per user-defined conversion konvertierbar ist, sondern nur "eingebaute" Konvertierungen von Zeigern bzw. Referenzen erlaubt.
    unique_ptr bietet die Konvertierung allerdings implizit an, was der Grund ist warum es mit unique_ptr<Node> dann geht.

    Ansonsten ja, immer richtig kompilieren. Intellisense verwendet ein anderes Frontend als der eigentliche Compiler.

    happystudent schrieb:

    Ja das hatte ich mir auch schonmal überlegt, aber das Problem ist dann dass die im Intellisense nicht mehr zusammen aufgelistet werden... Also ich find es praktisch wenn man dann z.B. alle Nodes hintereinander in der Autocomplete Liste hat.

    Ja, ich kenne das Argument, war für mich schliesslich selbst ein Grund es ne Zeitlang so wie du zu machen. Bin jetzt aber der Meinung dass die andere Variante besser ist. Weil man einerseits die Bedeutung eines Klassennamen nicht "dekodieren" muss, sondern oft sofort versteht was gemeint ist, und weil es andrerseits einfach die Variant ist die häufiger verwendet wird. (Und gegen den Strom zu schwimmen zahl sich mMn. nur aus wenn man dadurch einen echten Vorteil hat.)



  • In dem Fall braucht man die konkreten Klassennamen sowieso selten. Es gibt vielleicht 1-2 Stellen, wo ein NodeAdd erstellt wird, ansonsten muss man den Namen nicht kennen. Dann kann er auch gleich AddNode heißen.



  • hustbaer schrieb:

    Hattest du vielleicht versucht als Returntyp unique_ptr<NodeValue> zu verwenden?

    Ne, war schon unique_ptr<Node> , aber die Meldung war nach kompilieren, Projekt schließen und wieder öffnen dann auch weg. Intellisense reagiert teilweise auch recht langsam auf Änderungen...

    hustbaer schrieb:

    Ja, ich kenne das Argument, war für mich schliesslich selbst ein Grund es ne Zeitlang so wie du zu machen. Bin jetzt aber der Meinung dass die andere Variante besser ist.

    Mechanics schrieb:

    In dem Fall braucht man die konkreten Klassennamen sowieso selten. Es gibt vielleicht 1-2 Stellen, wo ein NodeAdd erstellt wird, ansonsten muss man den Namen nicht kennen. Dann kann er auch gleich AddNode heißen.

    Stimmt auch wieder, werd das nochmal überdenken.



  • Wobei: Das wichtigste bei Benamsung und allg. "Style-Konventionen" ist mMn. dass man es (wenigstens) pro Projekt einheitlich durchzieht.
    Zumindest in langlebigen Projekten die häufiger erweitert/gändert bzw. allgemein "gewartet" werden.


Anmelden zum Antworten