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 vonNodeAdd
übergeben? Dasmove
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 umnode
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 ummove
Gedanken machen zu müssen (wie einenstd::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 derunique_ptr
noch nicht konstruiert worden ist.
Um dieses Problem zu vermeiden, benutzt manmake_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 umnode
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 ummove
Gedanken machen zu müssen (wie einenstd::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 nicht2...
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 beinew T()
fliegen kann. WennT
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]
nenbad_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 vornew
nutze, aber ich weiß nicht wie ich das vermeiden soll. Das Problem ist ja dass wenn ichNode
als template-Parameter anmake_unique
übergebe, ich dann nicht sagen kann welchenNode
ich jetzt erstellen will, da ich nur den Konstruktor vonNode
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 anmake_unique
, stimmt der Rückgabetyp der Methode nicht mit dem geforderten Rückgabetyp der rein virtuellen Methodecopy
ü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 diemake_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
undAddNode
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
undAddNode
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 mitunique_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.