Tree mit Nodes und Downcasts
-
dynamic_cast und ausprobieren dürfte sehr teuer sein, wenn du keinerlei Anhaltspunkte hast welche Klasse es ist. Wenn es nichts selbstimplementiertes sein soll, würde ich eher auf den typeid operator zurückgreifen. Der Königsweg ist aber wohl tatsächlich, so etwas generell zu vermeiden.
-
Ich habe beim Parser meiner Sprache im Moment genau dasselbe Problem. Einerseits koennte man das mit virtuellen Funktionen loesen, andererseits ist eine Funktion fuer jede Funktionalitaet etwas viel und man will eigentlich nur die Struktur des Programms mit dem AST ausdruecken.
Man will etwas nicht intrusives, eine Art freie virtuelle Funktion.Im Prinzip bleibt dir nichts anderes ueber als dynamic_cast/typeid. Man koennte jetzt noch ein Typ-Enum drumherum bauen, aber das macht das ganze designtechnisch auch nicht besser, moeglicherweise nur etwas schneller.
-
Das habe ich befürchtet.
Also ich habe einen Baum, der sowohl Ordner hat als auch Elemente. Elemente sind hier jetzt beispielhaft wieder meine lieben Mengen, also einfach Mengen von Zahlen. Es gibt aber auch Untermengen, die im Baum so ausgedrückt sind, dass es sich um Nodes handelt, die Kinder von den MengenNodes sind.
Okay, also z.B. so:
Folder1 - Menge1 (0-100) - Menge2 (101-200) -- Untermenge1 (101,103,105,107,...,199) -- Untermenge2 (102,104,106,108,...,200) - Menge3 (201-300) -- UntermengeA (201-290) -- UntermengeB (leer) - Menge4 (leer)Jetzt gibt es eine Funktion, die dazu genutzt werden kann, Restmengen zu bilden basierend darauf, was die Eltern haben und was exklusiv durch andere Mengen schon ermittelt wurde.
Wendet man die Restmengen-Funktion hier z.B. auf UntermengeB an, ergibt sich 291-300 als Ergebnis.
Der Algorithmus ist in Pseudocode also etwa:
void ErmittleRestmenge(std::string mengenName) // also mit Aufruf mengenName = "Menge4" { Node* elternNode = getNodeByName(mengenName).GetParentNode(); auto elternMengenNode = dynamic_cast<MengenNode*>(&elternNode); Menge ergebnisMenge; if(elternMengenNode) ergebnisMenge = elternMengenNode->GetMenge(); else ergebnisMenge = Menge::GetNatuerlicheZahlenMenge(); // oder eine andere "alles umfassende" // und jetzt alle Nachbarmengen abziehen: [...] return ergebnisMenge; }Ich muss ja rausfinden, ob das Elternelement überhaupt ein Mengennode ist. Polymorphie hieße, ich würde Node eine Methode GetMenge() geben. Das finde ich aber unnatürlich, denn ein Folder hat einfach keine Menge. Selbst wenn der dann
Menge::GetNatuerlicheZahlenMenge()zurückgeben würde, damit der Algorithmus einfach funktioniert, ist das trotzdem in meinen Augen die falsche Aussage. Denn grundsätzlich hat ein FolderNode eben keine Menge.Man könnte natürlich auch sagen, dann liefert FolderNode::GetMenge() auch wirklich nichts zurück, dann würde ErmittleRestmenge() aber nicht so wie gewünscht funktionieren.
Ein andres Beispiel wäre, wenn man rechte Maustaste in einem UI auf eine Baumdarstellung macht und auf "Eigenschaften" klickt. Dann sollen bei einem Folder diverse Infos stehen, bei einer Menge aber andere. Ich fände es nicht schön, wenn dann bei einem Folder trotzdem stehen würde "Menge: " und dahinter dann einfach nichts wäre.
Ich hoffe, die Beispiele erscheinen einleuchtend.
Edit:
Freut mich, dass Kellerautomat das Problem gerade auch hat. Das erscheint mir nämlich so grundsätzlich, dass ich mich gerade für den totalen Vollidioten halte... so ein Problem muss doch längst best-practice-artig oder in der Theorie gelöst sein, das ist doch total grundlegend?!
-
Kellerautomat schrieb:
Ich habe beim Parser meiner Sprache im Moment genau dasselbe Problem. [...] Im Prinzip bleibt dir nichts anderes ueber als dynamic_cast/typeid. Man koennte jetzt noch ein Typ-Enum drumherum bauen, aber das macht das ganze designtechnisch auch nicht besser, moeglicherweise nur etwas schneller.
dynamic_cast/typeid!?
Hier bietet sich das Visitor Pattern an, natürlich in der C++-Variante, d.h. templatisiert um den double dispatch zu vermeiden.
-
Bei mir auch? Hast Du ein Codebeispiel?
-
Vóila:
class NodeType1; class NodeType2; struct NodeVisitor { ~NodeVisitor() { } virtual void visit( NodeType1& node ) = 0; virtual void visit( NodeType2& node ) = 0; }; class MyNodeVisitor : public NodeVisitor { public: void visit( NodeType1& node ) { std::cout << "Ich bin ein Typ 1 Node\n"; } void visit( NodeType2& node ) { std::cout << "Ich bin ein Typ 2 Node\n"; } }; class NodeBase { public: virtual ~NodeBase() { } virtual void accept( NodeVisitor& Visitor ) = 0; }; class NodeType1 : public NodeBase { public: void accept( NodeVisitor& Visitor ) { Visitor.visit( *this ); } }; class NodeType2 : public NodeBase { public: void accept( NodeVisitor& Visitor ) { Visitor.visit( *this ); } }; int main() { std::unique_ptr<BaseNode> Node( new NodeType1 ); MyNodeVisitor v; v.accept( Node.get() ); }Das Dumme am Visitor Pattern ist, dass man den Kontext verliert, weil man die lokale Funktion/Methode verlassen muss, um den konkreten Knotentyp zu behandeln. Inwiefern das für dich problematisch wird musst du selbst abschätzen.
-
Hier die C++-Version:
enum class type { mengen_node, folder_node }; struct basic_node_visitor; struct node { node *parent; std::string name; protected: node(type t) : t(t) {} private: friend class basic_node_visitor; type t; }; struct mengen_node : node { int von, bis; std::vector<std::unique_ptr<mengen_node> > untermengen; mengen_node() : node(type::mengen_node) {} }; struct folder_node : node { folder_node() : node(type::folder_node) {} std::vector<std::unique_ptr<mengen_node> > untermengen; }; struct basic_node_visitor { protected: type get_type(node& n) { return n.t; } }; template <typename CRTP, typename ReturnType=void> struct node_visitor : basic_node_visitor { ReturnType visit(node& n) { switch(get_type(n)) { case type::mengen_node: return static_cast<CRTP*>(this)->do_visit(static_cast<mengen_node&>(n)); case type::folder_node: return static_cast<CRTP*>(this)->do_visit(static_cast<folder_node&>(n)); default: assert(false); } } ReturnType visit(node const& n) { switch(get_type(n)) { case type::mengen_node: return static_cast<CRTP*>(this)->do_visit(static_cast<mengen_node&>(n)); case type::folder_node: return static_cast<CRTP*>(this)->do_visit(static_cast<folder_node&>(n)); default: assert(false); } } }; // =========================================================================== // so wirds benutzt: // header: int ermittle_menge(node& n); // etwas nicht intrusives, eine Art freie virtuelle Funktion // cpp: namespace { struct mengen_ermittler : node_visitor<mengen_ermittler, int> { int do_visit(mengen_node& n) { return n.von; } // ich will nur den mengen_node int do_visit(node& n) { return -1; } // node& matcht den ganzen Rest }; } int ermittle_menge(node& n) { return mengen_ermittler().visit(n); }
-
Dankeschön für die Mühe!
Hm, ich sehe jetzt jedoch keinen Vorteil. Meinen Algorithmus könnte ich dadurch doch gar nicht verbessern?
Schließlich setzt der nicht nur auf einem Node sondern auf einer Kette von Nodes auf. Und ein MengenNode direkt unter einem Folder unterscheidet sich ja vom Typ nicht von einem MengenNode unter einem andren MengenNode. Wäre das der Fall, könnte ich meinen Algorithmus darüber umsetzen (wobei ich auch immer noch gerne wüsste, wie das templatisiert ohne double-dispatch aussähe, wie vom Gast beschrieben :)). Aber in dieser Form mit einer ganzen Klasse und einem zusätzlichen virtuellen Methodenaufruf über accept empfinde ich das eh nicht vorteilhaft, das hat doch noch mehr Overhead als ein simpler dynamic_cast oder nicht?
-
Eisflamme schrieb:
Freut mich, dass Kellerautomat das Problem gerade auch hat. Das erscheint mir nämlich so grundsätzlich, dass ich mich gerade für den totalen Vollidioten halte... so ein Problem muss doch längst best-practice-artig oder in der Theorie gelöst sein, das ist doch total grundlegend?!
Das ist auch total grundlegend, und unter dem Namen "Expression Problem" bekannt.
-
@Twelve Parsecs:
Kannst du mir bitte die Vorteile deiner Version gegenüber meiner erläutern? In deiner Variante muss ein zusätzliches Attribut für den Knotentyp implementiert werden, außerdem fallen nicht behandelte Knotentypen erst zur Laufzeit auf.
Auf der anderen Seite vermeidest du virtuelle Methodenaufrufe, was die Laufzeit verbessert. Überzeugt mich noch nicht so wirklich...
-
Eisflamme schrieb:
Ein andres Beispiel wäre, wenn man rechte Maustaste in einem UI auf eine Baumdarstellung macht und auf "Eigenschaften" klickt. Dann sollen bei einem Folder diverse Infos stehen, bei einer Menge aber andere. Ich fände es nicht schön, wenn dann bei einem Folder trotzdem stehen würde "Menge: " und dahinter dann einfach nichts wäre.
Das ist aber eher ein Hinweis darauf, dass der Begriff "Menge" nicht abstrakt genug ist, um für mehrere konkrete Klassen zu gelten. Vielleicht wäre eher sowas wie "Darstellung" angebracht. Eine virtuelle Ausgabefunktion könnte dann im Fall eines Mengenknotens "Menge: {...}" oder im Fall des Ordners "Ordner" ausgeben.
Aber beim Composite Pattern hat man das Problem ab und zu, dass man nur mit gewissen Elementen arbeiten will. Wenn virtuelle Funktionen jeweils passende Werte zurückgeben, kann man sich die Fallunterscheidung auf Aufruferseite oft sparen.
-
DocShoe schrieb:
@Twelve Parsecs:
Kannst du mir bitte die Vorteile deiner Version gegenüber meiner erläutern? In deiner Variante muss ein zusätzliches Attribut für den Knotentyp implementiert werden, außerdem fallen nicht behandelte Knotentypen erst zur Laufzeit auf.
Auf der anderen Seite vermeidest du virtuelle Methodenaufrufe, was die Laufzeit verbessert. Überzeugt mich noch nicht so wirklich...Du brauchst zwei virtuelle Funktionsaufrufe, einmal accept und einmal visit. Jeder virtuelle Funktionsaufruf bedeutet ein lookup in der vtable und den Aufruf eines Funktionspointers. Ich habe nur ein switch, was etwas mehr als doppelt so schnell sein dürfte.
Ein weiterer Vorteil ist, dass bei sagen wir mal 10 verschiedenen Typen nicht 10 verschiedene virtuelle Funktionen gebraucht werden, sondern ich mit node& alles matchen kann. In meiner Erfahrung will man oft für wenige Typen Sonderfälle und den Rest einfach ignorieren.
Und die Typ-ID hätte ich in einem AST sowieso, weil manchmal nur ein Typ erlaubt ist (was aber vom Kontext abhängt und nicht im Typsystem ausdruckbar ist). Für einen sicheren und schnellen dynamic_cast quasi (assert + static_cast).
-
Eine virtuelle Ausgabefunktion könnte dann im Fall eines Mengenknotens "Menge: {...}" oder im Fall des Ordners "Ordner" ausgeben.
Es ist aber nicht Aufgabe des Knotens die Art der Anzeige vorzugeben. Das soll das UI entscheiden.
DocShoe:
Ja, keine virtuellen Methodenaufrufe, das ist wohl der Hauptvorteil. Wenn das alles ist, ist es aber echt viel Aufwand ggü. Deiner Variante. Dann wiederum sehe ich aber in einer Variante mit virtuellen Methoden überhaupt keinen Vorteil mehr ggü. einer einfachen dynamic_cast-Lösung.Aber: Ich empfinde Visitor jetzt gerade ohnehin als großen Aufwand, nur um Casts zu vermeiden. Wenn man eh node_type hat, wieso nicht einfach die virtuelle Methode
GetType()einführen? Aber von einem einfachen dynamic downcast ist das auch nicht weit weg (virtueller Methodenaufruf ist ja wohl kaum so viel performance-günstiger oder doch?). Und wie gesagt ist Visitor auf Ebene eines Objekts beschränkt.In meinem Ausgangsbeispiel unterscheidet sich der Algorithmus aber nicht ausgehend von dem Typ des Nodes, auf dem er ausgeführt wird, sondern darauf, was dessen Parent für einen Typ hat, also müsste man sich noch mehr verwurschteln, um den Cast wegzukriegen.
Und wie gesagt: Superviel Code und dann ist nur der Cast weg. Da frage ich mich, was an dem Cast überhaupt das Problem ist, dass man so viel Aufwand betreiben will, um den loszuwerden?
Wäre super, wenn mir jemand weiterhelfen könnte, ich sehe gerade überhaupt nicht den Vorteil...
-
Eisflamme schrieb:
Aber in dieser Form mit einer ganzen Klasse und einem zusätzlichen virtuellen Methodenaufruf über accept empfinde ich das eh nicht vorteilhaft, das hat doch noch mehr Overhead als ein simpler dynamic_cast oder nicht?
einfachen dynamic_cast-Lösung
virtueller Methodenaufruf ist ja wohl kaum so viel performance-günstiger oder doch
lol? Bitte messen. Ich schätze mal dynamic_cast ist Faktor 10 langsamer als eine virtuelle Funktion. Vor allem hängt es ab, wie tief die Hierarchie ist. dynamic_cast traversiert schön langsam rekursiv über alle Parents.
Und wenn du nur einen Typ willst, dann nimm das Typ-ID Feld.
-
Ach echt? Okay, aber was spricht dann gegen eine virtuelle Methode, die via enum den Typ zurückgibt? Das sollte doch dann keine Nachteile mehr ggü. dem Visitor mit virtuellen Methoden mehr haben oder welche wären das?
Edit: Also wäre TypID-Feld + nachfolgendem static_cast die zu empfehlende Variante oder wie?
-
Eisflamme schrieb:
wieso nicht einfach die virtuelle Methode
GetType()einführen? Aber von einem einfachen dynamic downcast ist das auch nicht weit weg (virtueller Methodenaufruf ist ja wohl kaum so viel performance-günstiger oder doch?).Doch, ein virtueller Methodenaufruf ist nur eine doppelte Indirektion: Einmal den vptr des Objektes dereferenzieren, dann den Eintrag rausfischen und einen indirekten Aufruf machen. dynamic_cast ist dagegen ein relativ komplexer Algorithmus, um z.B. auch Cross-Casts zu realisieren.
-
Ups, okay.
Hat Visitor ggü. GetType() (oder TypID-Feld, wie auch immer) denn noch einen Vorteil bis auf den (in der Template-Variante) verhinderten Methodenaufruf? Weil wenn nicht, erscheint mir Visitor irgendwie nur notwendig, wenn man viel Performance will bei Nodeaufrufen, stimmt das denn?
Die anderen Vorteile bei wikipedia sind sonst ja egal. Entkopplung Algorithmus von Klasse mache ich mit einer freien Methode eh. Ich sehe schon, dass sich das Pattern für meinen Fall anbietet, weil für den Algorithmus (Visitor) des Ermittelns der Mengen für ein MengenNode etwas anderes herauskommt als für einen FolderNode - ich finde nur nicht, dass dieser Aufwand ausreichend Vorteile bringt, dass ich ihn einbauen sollte?!
Wo liegt die Motivation?
