Tree::GetChildren() - Kopie notwendig?



  • Hi,

    ich habe eine einfache Baumklasse entwickelt. Ein Knoten kann beliebig viele Kinder haben. Diese verwalte ich über unique_ptr.

    Das klappt so weit prima, jetzt bin ich aber auf eine Designhürde gestoßen. Benutzer der Klasse sind bisweilen daran interessiert, welche Kinder es gibt. Sie sollen die Kinder inhaltlich manipulieren können, nicht jedoch Besitz übernehmen o.ä. Wie stelle ich das sicher?

    Dies ist meine aktuelle Variante:

    class TreeNode
    {
    public:
        typedef std::vector<std::unique_ptr<TreeNode>> TreeNodePtrVector;
    
        TreeNodePtrVector& GetChildren() {return children;}
    
    private:
        TreeNodePtrVector children;
    };
    

    Das deckt ja gar nicht ab, was ich eigentlich möchte. Der Benutzer hat viel zu viel Einfluss, kann hier Elemente löschen, verschieben, enteignen usw. Sinnvoller wäre:

    class TreeNode
    {
    public:
        typedef std::vector<std::unique_ptr<TreeNode>> TreeNodePtrVector;
        typedef std::vector<TreeNode*> TreeNodeRefPtrVector; // Name strittig
    
        TreeNodeRefPtrVector GetChildren()
        {
            TreeNodeRefPtrVector result;
            result.resize(children.size());
            for(int n = 0; n < children.size(); ++n)
                result[n] = children[n].get();
            return result; // RVO angenommen
        }
    };
    

    Das hat sichtlichen Overhead. Würdet ihr das so nutzen? Oder gibt es eine bessere Möglichkeit.

    Viele Grüße
    Eisflamme



  • Einfach eine const Referenz zurückgeben?



  • Also ich finde das gut. Was denn für ein Overhead?
    Die Schleife und die paar Pointer-Kopien?
    Jedenfalls besser, als eine Struktur mir unique-ptrs zu bekommen, was mir als Nutzer ja völlig wurscht ist, wie du das intern implementiert hast.



  • Ja, die Schleife.

    Ich fand gerade heraus, dass sebi707s Lösung auch funktioniert, da ich bei einem const vector<unique_ptr<.>> ja trotzdem das, worauf die unique_ptrs zeigen, verändern kann.

    Die andere Überlegung: unique_ptr& und TreeNode* sind nicht ganz dasselbe.

    Wenn ich beispielsweise zwei unique_ptr swappe, werde ich durch TreeNode* auf denselben Node verweisen. unique_ptr& hält jetzt aber einen anderen TreeNode*.

    TreeNode* ist also invariant ggü. Positionsänderungen, die bei mir durchaus vorkommen. Das wäre ja ein weiteres Argument für vector<TreeNode*>. Na ja, je nachdem, was man erwartet, eben.



  • boost hat dereferenzierende iterator-adapter. Da tust Du nur die Iteratoren Deine Sequenz rein und nach außen hin kommt man dann nur an die Refenzen der Kinder. Da könntest Du dann einfach noch begin(), end() usw. mit implementieren und fertig.

    Kann man sich natürlich auch selber entwickeln, wenn man boost nicht so sehr mag.



  • Es fühlt sich irgendwie besser an, keine Kopie des kompletten Vectors zu erstellen, sondern auf den Originaldaten zu arbeiten, zumindest solange die Elemente im kopierten Vector 1:1 denen im internen entsprechen. Etwas anderes wäre es natürlich, wenn der kopierte Vector nur eine Auswahl enthält oder später weiter gefiltert oder sortiert werden soll.

    Wie wäre es, die Kinder an sich im Vector in TreeNode zu belassen und nur den Zugriff darauf nach außen zu gewähren?

    OK, den vector public zu machen ist zu wenig Schutz.

    Aber mit const vector<...>& getChildren() nur den Lesezugriff auf den Vector zu gewähren sollte eigentlich gehen, dann kann man draußen mit const_iterator drübermarschieren.

    class TreeNode
    {
    public:
        typedef std::vector<std::unique_ptr<TreeNode>> TreeNodePtrVector;
    
        const TreeNodePtrVector& GetChildren() {return children;}     // <-- beachte das const
    
    private:
        TreeNodePtrVector children;
    };
    

    Oder etwas in der Richtung TreeNode* getFirstChild() + TreeNode* getNextChild() oder so (Nachteil: der extra Iterator muss in TreeNode gepflegt werden, nicht gerade threadsafe...).

    Oder eine allgemeine Manipulations-Schnittstelle, bei der Du der Klasse TreeNode einen Functor übergeben kannst, und TreeNode läuft dann selbst über die Kinder drüber und wendet den Functor an, ohne die Position der Kinder zu verändern oder sie zu löschen?



  • #include <boost/iterator/indirect_iterator.hpp>
    
    class Foo {
        using vector_type = std::vector< std::unique_ptr< Foo > >;
        vector_type vec_;
    
        using iterator = boost::dereferencing_iterator< vector_type::iterator >;
    
        iterator begin()
        {
           return vec_.begin();
        }
    
        iterator end()
        {
           return vec_.end();
        }
    
        // ...
    }
    


  • indirect_iterator muss es natürlich lauten...


Log in to reply