Eigener kopier- und auseinandernehmbarer Composite-Tree - Review?



  • Hi,

    ich brauchte eine Baumstruktur, die Kopieren/Moven im Ganzen erlaubt. Zusätzlich sollte man an einzelnen Nodes abschneiden können und Teile dann in einem anderen Baum einfügen, das alles möglichst performant.

    Würde mich über ein kurzes Review und Verbesserungsvorschläge freuen, da ich den Baum recht weitgreifend einsetzen möchte. Viele Methoden-Implementationen habe ich zurzeit noch im Header stehen, die ich später noch auslagern möchte.

    Die Grundstruktur: Es gibt eine Tree-Klasse mit Nodes. Die Basis eines Nodes ist TreeNode. Dann gibt es spezielle Nodes, ein Beispiel dafür ist jetzt TreeRangeNode.

    Der Code ist unten angehängt. Ideone-Link mit ausführbarem Beispielcode findet sich hier: http://ideone.com/70P3o4

    /////
    // Tree.h:
    
    #ifndef TREE
    #define TREE
    
    #include <memory>
    
    class TreeNode;
    
    class Tree
    {
    public:
    	typedef std::unique_ptr<TreeNode> TreeNodePtr;
    
    	Tree();
    	// copy allowed!
    	Tree(const Tree& rhs);
    	// copy
    	Tree& operator=(const Tree& rhs);
    	// move allowed
    	Tree(Tree&& rhs);
    	// move
    	Tree& operator=(Tree&& rhs);
    
    	// dtor not necessary because of unique_ptr
    
    	const TreeNode* GetRootNode() const { return &*rootNode; }
    	TreeNode* GetRootNode() { return &*rootNode; }
    
    private:
    	TreeNodePtr rootNode;
    };
    
    #endif
    
    // Tree.cpp
    /////
    
    #include "Tree.h"
    #include "TreeNode.h"
    
    Tree::Tree() : rootNode(new TreeNode)
    {
    
    }
    
    // ===
    
    Tree::Tree(const Tree& rhs)
    	: rootNode(rhs.rootNode->Clone())
    {
    }
    
    // ===
    
    Tree& Tree::operator=(const Tree& rhs)
    {
    	this->rootNode.reset(rhs.GetRootNode()->Clone());
    	return *this;
    }
    
    // ===
    
    Tree::Tree(Tree&& rhs)
    	: rootNode(std::move(rhs.rootNode))
    {
    }
    
    // ===
    
    Tree& Tree::operator=(Tree&& rhs)
    {
    	rootNode = std::move(rhs.rootNode);
    	return *this;
    }
    
    /////
    // TreeNode.h
    
    #ifndef TREE_NODE
    #define TREE_NODE
    
    #include <memory>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <cassert>
    
    class TreeNode
    {
    public:
    	typedef std::unique_ptr<TreeNode> TreeNodePtr;
    	typedef std::vector<TreeNodePtr> TreeNodePtrVector;
    
    	TreeNode() : parent(nullptr) {}
    
    	// adds newly created node; TreeNode owns new node now
    	void Add(TreeNode* ptr)
    	{
    		ptr->parent = this;
    		children.push_back(TreeNodePtr(ptr));
    	}
    
    	// removes node from current tree and returns it; memory management is no longer maintained by TreeNode
    	TreeNode* Release()
    	{
    		assert(parent && "Releasing root node is not possible. If moving is wished, move whole tree instead.");
    
    		return parent->releaseChild(this);
    	}
    
    	virtual void Foo() const {};
    	virtual TreeNode* Clone() const
    	{
    		return new TreeNode(*this);
    	}
    
    	const TreeNodePtrVector& GetChildren() const { return children; }
    	const TreeNode* GetParent() const { return parent; }
    
    	void AddChildrenFrom(const TreeNode& otherNode)
    	{
    		for (const TreeNodePtr& nodePtr : otherNode.children)
    			Add(nodePtr->Clone());
    	}
    
    	virtual bool IsFolder() const { return true; };
    
    protected:
    	// only for cloning
    	TreeNode(const TreeNode& rhs) : parent(rhs.parent)
    	{
    		AddChildrenFrom(rhs);
    	}
    
    	// release child and return it
    	TreeNode* releaseChild(const TreeNode* child)
    	{
    		// find child
    		auto it = std::find_if(children.begin(), children.end(), [&](const TreeNodePtr& currentChild) {return &*currentChild == child;});
    
    		TreeNode* releasedNode = it->release();
    
    		children.erase(it);
    
    		return releasedNode;
    	}
    
    private:
    	TreeNode* parent;
    	TreeNodePtrVector children;
    };
    
    #endif
    
    /////
    // TreeFolderNode.h
    
    #ifndef TREE_FOLDER_NODE
    #define TREE_FOLDER_NODE
    
    #include <iostream>
    #include "TreeNode.h"
    
    class TreeFolderNode : public TreeNode
    {
    public:
    	TreeFolderNode(int value) : value(value) {}
    
    	void Foo() const override { std::cout << "Folder: " << value << '\n'; }
    
    	TreeNode* Clone() const override
    	{
    		return new TreeFolderNode(*this);
    	}
    
    private:
    	// private copy ctor for cloning
    	TreeFolderNode(const TreeFolderNode& rhs) = default;
    
    	int value;
    };
    
    #endif
    

    Mir ist klar, dass das bei so viel Code wahrscheinlich zu viel verlangt ist, aber vielleicht hat ja jemand trotzdem irgendetwas zu bemängeln.

    Gruß
    Tim



  • 30 Sekunden investiert...
    - Ich würde bei Clone() gerade ein TreeNodePtr zurückgeben.
    - Auch Add(..) würde ich gleich einen TreeNodePtr übergeben - das zeigt auch die Übername des Besitzes an.
    - Und auch bei Release() würde ich einen TreeNodePtr zurückgeben.



  • Hm, verstehe...

    Das erfordert dann natürlich, dass man so adden muss:

    treeNode->Add(Tree::TreeNodePtr(new TreeFolderNode(10)));
    

    Das bläht den Code in meinen Augen ziemlich auf, findest du das ggü. der leichten Intuition, wie die Speicherverwaltung ist, tragbar?

    Edit:
    Bzw. scheint das nicht mal zu funktionieren, ich muss noch move nutzen. Und: Wenn ich den Pointer durch move erstmal "Add"e, kann ich später nicht mehr denselben Zeiger nutzen, um dort Kinder einzufügen. Also die Handhabe von Tree und den Nodes wird durch die unique_ptr im Funktionsaufruf schlechter.

    Und ist unique_ptr nicht auch ein Implementierungsdetail, was den Benutzer gar nicht interessieren sollte? (auch wenn ich typedef nutze)



  • template< typename T, typename... Args >
    std::enable_if_t<std::is_convertible<T,TreeNode::value>, T&>
    emplace_child( Args&&... args )
    {
        static_assert(std::is_convertible< T, TreeNode >::value, "fooofooofooo"); 
        return Add( std::make_unique<T>(std::forward<Args>(args)...) );
    }
    

    oder irgendwie soetwas vielleicht als Notlösung?



  • naja, nen value hier und ein static_assert weniger und so, aus der Hüfte geschossen.



  • Ich finde std::unique_ptr<..> im Interface gut, weil es eine fehlerhafte Benutzung verhindert (oder mindestens erheblich erschwert) und weil es zeigt, was die Absicht ist (z.B. Besitz bei Add(..) übergeben/übernehmen).

    Mit std::make_unique<..>(..) aus C++14 oder einem selbstgemachten make_unique<..>(..) sieht das Ganze dann sehr ordentlich aus. Der Vorschlag von decimad finde ich auch in Ordnung.

    Edit (1)

    Eisflamme schrieb:

    Das bläht den Code in meinen Augen ziemlich auf, findest du das ggü. der leichten Intuition, wie die Speicherverwaltung ist, tragbar?

    Ich sehe das genau umgekehrt: Der Code wird minimal, falls überhaupt aufgebläht und die Verwendung der Interfaces wird dadurch klarer. Die Absicht wird gezeigt.

    Eisflamme schrieb:

    Und: Wenn ich den Pointer durch move erstmal "Add"e, kann ich später nicht mehr denselben Zeiger nutzen, um dort Kinder einzufügen.

    Das mache ich jeweils so, dass ich eine Referenz auf das eingefügte Element zurückgebe - so kannst du die Einfüge-Operationen sogar verknüpfen.

    Edit (2)
    BTW: Mit der unique_ptr<..>-Lösung, brauchst du auch keine Kommentare mehr, die Erklären, wie der Besitz geregelt ist.



  • Hi,

    okay, überzeugt. 🙂 Und ::type muss noch ans Ende. Also die neue Version:

    http://ideone.com/o3b8T0

    In Visual Studio 2013 kompiliert das. Aber das enable_if bei Add substituted nicht bei Ideone, als könnte er TreeType nicht zu TreeType konvertieren, was natürlich sinnlos ist. Wenn ich die enable_if-Zeile bei Add auskommentiere, funktioniert es wie erwartet. Jemand eine Idee? 😞



  • Ich hab kurz überlegt, ob er beim SFINAE versucht TreeNode (Klasse) mit TreeNode (forw. declaration) zu vergleichen, aber innerhalb der Klasse sollte er ja wohl TreeNode kennen, also kann es das nicht sein...



  • Es funktioniert zumindest mit std::is_base_of. Ich glaube, std::is_convertible erlaubt diese Konvertierungen nicht, weil für was es gedacht ist, slicing verhindern möchte.
    Da GetRootNode aber eine Referenz auf den Knoten zurückliefert, schmiert Dein Programm ab, wenn aus dem Baum herausgemoved wurde... Zumindest verwendet Dein Testcode ihn dann munter weiter.



  • Ich verstehe den Zusammenhang zwischen enable_if und der RootNode-Referenz gerade nicht.

    Herausmoven aus dem Baum ist natürlich so ne Sache, dann ist der alte Baum invalid. Man könnte den alten Baum auch wiederbeleben, indem man den rootNode neu erzeugt.

    Was du damit meinst, dass TreeNode munter weiterbenutzt wird, verstehe ich nicht. Nach Move hat sich TreeNode doch nicht verändert, der lebt doch im unique_ptr. Könntest du vielleicht auf die kritische(n) Codezeile(n) verweisen?


  • Mod

    Eisflamme schrieb:

    In Visual Studio 2013 kompiliert das. Aber das enable_if bei Add substituted nicht bei Ideone, als könnte er TreeType nicht zu TreeType konvertieren, was natürlich sinnlos ist. Wenn ich die enable_if-Zeile bei Add auskommentiere, funktioniert es wie erwartet. Jemand eine Idee? 😞

    Der Kopierkonstruktor ist als protected deklariert. Und

    §14.3/3 schrieb:

    For a template-argument that is a class type […], the template definition has no special access rights to the members of the template-argument.

    Wenn ich e.g. den Kopierkonstruktor als public deklariere, bekomme ich außerdem einen Segfault.

    PS: Code bitte stets via Coliru posten.


  • Mod

    decimad schrieb:

    std::is_convertible erlaubt diese Konvertierungen nicht, weil für was es gedacht ist, slicing verhindern möchte.

    😕 is_convertible wird intern mit SFINAE realisiert. Es wird einfach versucht eine copy-initialization durchzuführen.

    libstdc++' <pre><code><type_traits></code></pre>, Zeile 1463 schrieb:

    template<typename _From, typename _To,
               bool = __or_<is_void<_From>, is_function<_To>,
                            is_array<_To>>::value>
        struct __is_convertible_helper
        { typedef typename is_void<_To>::type type; };
    
      template<typename _From, typename _To>
        class __is_convertible_helper<_From, _To, false>
        {
           template<typename _To1>
    	static void __test_aux(_To1);
    
          template<typename _From1, typename _To1,
    	       typename = decltype(__test_aux<_To1>(std::declval<_From1>()))>
    	static true_type
    	__test(int);
    
          template<typename, typename>
    	static false_type
    	__test(...);
    
        public:
          typedef decltype(__test<_From, _To>(0)) type;
        };
    

    Die copy-initialization wird mittels Initialisierung eines Funktionsparameters "simuliert", wobei die Funktion __test_aux<_To1> ist. Also die intuitive Implementierung. Und natürlich schlägt die Deduzierung in Zeile 14 fehl, da kein Move-Konstruktor existiert
    ( std::declval<_From1>() ist ein x- bzw. rvalue) und der Kopierkonstruktor, wie bereits erwähnt, nur protected .

    is_base_of wird i.d.R. durch ein Intrinsic realisiert, es geht aber natürlich auch anders, und zwar indem die Ambiguität einer Konvertierung ausgenutzt wird - access != visibility. Wie auch immer, is_base_of und is_convertible sind zwei völlig verschiedene Dinge.



  • Coliru? Nie gehört, probiere ich nächstes mal gerne aus. 🙂

    Also sollte is_base_of das Problem lösen?

    Der Segfault kommt daher, dass bei:

    Tree a;
    Tree b(std::move(a));
    

    a ungültig wird.

    Was ist denn hier das erwartete/präferierte Verhalten? Es ist ja in Ordnung zu sagen, der gemovete ist ungültig. Man könnte aber auch wieder als Root-Node einen TreeNode neu einfügen, dann ist der Baum gültig aber leer.



  • Ich hab' mir zu dem Zeitpunkt nicht den Quelltext von is_convertible angeschaut, was in ideone wohl auch nur schwerlich geht. In einer der online c++ referenzen steht aber, dass es wohl bei Rückgabewerten per Wert Anwendung finden soll. Dort würde ich erwarten, dass nicht einfach weggesliced wird. Daher stammte meine _Vermutung_ wie is_convertible ausgelegt ist, den einschränkenden Teil hast Du nun aber einfach aus dem Quote herausgenommen.

    Normalerweise erwartet man, dass das ausgemovete Objekt in einem leeren aber gültigen Zustand verbleibt, also dass Zerstörung usw. alles noch definiert ist. Und nicht mehr! Das soll ja zumeist für Parameterverkettungen usw. verwendet werden und ist dann hinterher nur noch als leere Hülle betrachtet.


Log in to reply