std::vector und Pointer-management



  • Hallo,

    ich versuche mir gerade eine Baum-Struktur zu bauen. Dazu bin ich bis jetzt (nur ein Ausschnitt) wie folgt vorgegangen:

    #include <vector>
    #include <iostream>
    
    template <class T>
    class node
    {
    public:
        T value;
        std::vector<node<T>*> children;
    };
    
    template <class T>
    class tree
    {
        std::vector<node<T>> nodes;
    public:
    
        node<T> base;
    
        void add_child_to_base(node<T> const &node)
        {
            nodes.push_back(node);
            base.children.push_back(&nodes.back()); // Problem
        }
    };
    
    int main()
    {
        tree<int> t;
        node<int> n;
        n.value = 42;
    
        t.add_child_to_base(n);
        t.add_child_to_base(n);
        t.add_child_to_base(n);
    
        for (auto const &i : t.base.children) {
            std::cout << i->value << ' '; // Ausgabe: 141889544 42 42
        }
    }
    

    Also vom Prinzip hab ich in der Baum Klasse versteckt alle Knoten in einem vector gespeichert, in den jeweiligen Kindknoten verwalte ich dann nur einen vector aus Pointern auf diese Daten.

    Problem ist jetzt die markierte Zeile, bzw. auch die Zeile darüber: Dadurch dass der vector ja dynamisch wächst werden durch das push_back jedes mal wenn der vector wachsen muss die Pointer in den Kind-Knoten invalidiert, wodurch der ganze Baum hinüber ist. Wie man an der Ausgabe sehen kann hat der ersten node::value nicht den Wert 42 sondern irgendeinen random Wert.

    Wie würde man dieses Problem am besten lösen? Keinen vector benutzen (aber was dann?)? Wenn ich den Speicher mit reserve vorab reserviere funktioniert alles problemlos, aber das kann ja auch nicht die Lösung sein, weil ich ja vorab ja nicht weiß wie groß der Baum werden muss (unter Umständen sehr groß).



  • Warum speicherst du nicht direkt die Children in den Nodes? Tree.nodes ist m.E. überflüssig (einzig ein Root-Node wird dort benötigt).



  • Th69 schrieb:

    Warum speicherst du nicht direkt die Children in den Nodes? Tree.nodes ist m.E. überflüssig (einzig ein Root-Node wird dort benötigt).

    Naja, ich kann doch in node keinen std::vector<node> speichern? Dann meckert der Compiler ja von wegen unvollständigem Typ, daher hab ich Pointer genommen.

    Oder vestehe ich dich jetzt falsch?



  • Nimm vector<int> und speichere den Index. Dann bau einen schicken Proxy drumrum.


  • Mod

    happystudent schrieb:

    Naja, ich kann doch in node keinen std::vector<node> speichern? Dann meckert der Compiler ja von wegen unvollständigem Typ, daher hab ich Pointer genommen.

    Oder vestehe ich dich jetzt falsch?

    Das ist im Prinzip richtig, lässt sich aber unter Umständen umgehen.
    Idee: ersetze vector<node> durch vector<node_space> wobei node_space so definiert wird, dass es ein node exakt enthalten kann.

    #include <cstdlib>
    #include <utility>
    #include <algorithm>
    #include <iostream>
    #include <new>
    
    template <typename T>
    class node;
    
    template <typename T>
    struct node_space_detail // pseudo-node um typische Werte für alignment und size zu bekommen
    {
         T value;
         std::vector<void*> children;
    };
    
    template <typename T>
    struct node_space
    {
        alignas(node_space_detail<T>) char data_[sizeof(node_space_detail<T>)];
    
        node<T>& data() { return reinterpret_cast<node<T>&>(data_); }
        const node<T>& data() const { return reinterpret_cast<const node<T>&>(data_); }
    
        template <typename... U>
        node_space(U&&... args) { new((void*)&data_)node<T>(std::forward<U>(args)...); }
    
        node_space(node_space& other) { new((void*)&data_)node<T>(other.data()); }
        node_space(const node_space& other) { new((void*)&data_)node<T>(other.data()); }
        node_space(node_space&& other) { new((void*)&data_)node<T>(std::move(other.data())); }
        node_space(const node_space&& other) { new((void*)&data_)node<T>(other.data()); }
    
        node_space& operator=(const node_space& rhs) { data()=rhs.data(); return *this; }
        node_space& operator=(node_space&& rhs) { data()=std::move(rhs.data()); return *this; }
    
        ~node_space() { data().~node<T>(); }
    
        void swap(node_space& other) { swap(data(),other.data()); }
    };
    
    template <class T>
    class node
    {
    public:
        T value;
        std::vector<node_space<T>> children;
    // eventuell hier noch im Destruktor ein static_assert um Layoutidentität mit std::vector<node<T>> tzu prüfen
    };
    
    template <class T>
    class tree
    {
    public:
    
        node<T> base;
    
        void add_child_to_base(node<T> const &node)
        {
            base.children.emplace_back(node);
        }
    };
    
    int main()
    {
        tree<int> t;
        node<int> n;
        n.value = 42;
    
        t.add_child_to_base(n);
        t.add_child_to_base(n);
        t.add_child_to_base(n);
    
        for (auto const &i : t.base.children) {
            std::cout << i.data().value << ' '; // Ausgabe: 42 42 42
        }
    }
    

    ist noch ein bisschen unschön, wird aber die - im Grunde überflüssige - Indirektion los. Ausgangspunkt ist dabei, dass das Layout von std::vector typischerweise tatsächlich nicht von T abhängt.



  • camper schrieb:

    Idee: ersetze vector<node> durch vector<node_space> wobei node_space so definiert wird, dass es ein node exakt enthalten kann.

    Wenn du schon C++11 verwendest, warum nicht gleich direkt std::aligned_storage ?



  • Wäre es nicht interessant, in dem node auch einen parent zu speichern?...



  • Hallo,

    danke schonmal an alle für die Antworten. Kurz ein paar Antworten.

    roxy schrieb:

    Nimm vector<int> und speichere den Index. Dann bau einen schicken Proxy drumrum.

    Würd ich gerne vermeiden, wenns auch einfacher bzw. "intuitiver" geht.

    hardware schrieb:

    Wäre es nicht interessant, in dem node auch einen parent zu speichern?...

    Wie gesagt, das ist nur ein kleiner Ausschnitt und um das Problem zu verdeutlichen braucht es keinen parent.

    camper schrieb:

    ist noch ein bisschen unschön, wird aber die - im Grunde überflüssige - Indirektion los. Ausgangspunkt ist dabei, dass das Layout von std::vector typischerweise tatsächlich nicht von T abhängt.

    Das sieht ganz schön krass aus... also hier im Forum liest man ja immer das rohes new, void pointer, reinterpret_cast und explizites Destruktor aufrufen quasi Todsünden sind, das ist jetzt hier alles auf einmal drin... Das verunsichert mich jetzt ein wenig 😃

    Bevor ich aber weitermache, will bzw. muss ich erst etwas klären was ich nicht verstehe:

    Und zwar habe ich ja selbst gemeint "Naja, ich kann doch in node keinen std::vector<node> speichern?". Auf diese Aussage bin ich gekommen, nachdem ich das folgende versucht habe zu kompilieren:

    struct test
    {
        test t; // Fehler: Unvollständiger Typ ist unzulässig
    };
    

    Wenn man also kein Objekt von "sich selbst" speichern kann, kann man doch auch sicher keinen vector davon speichern dachte ich mir.

    Jetzt hab ich das aber einfach mal ausprobiert:

    struct test
    {
        std::vector<test> t; // Funktioniert!
    };
    

    und es kompiliert anstandslos! Wie kann das sein? Warum kann ich kein einzelnes Objekt in der Klasse haben (da Typ unvollständig) aber einen vector aus mehreren solchen Objekten schon?? Das macht doch gar keinen Sinn?


  • Mod

    aligan schrieb:

    camper schrieb:

    Idee: ersetze vector<node> durch vector<node_space> wobei node_space so definiert wird, dass es ein node exakt enthalten kann.

    Wenn du schon C++11 verwendest, warum nicht gleich direkt std::aligned_storage ?

    hatte ich für den Moment vergessen, ändert aber auch nur die Deklaration von data_. Einfacher wird es dadurch nicht, allerdings könnte man das Ganze verallgemeinern, vielleicht gibt es auch soetwas in boost schon.

    Also etwa

    template <typename T, typename Model> // provide storage for object of T (may be incomplete at the point of instantiation of type_storage)
    struct typed_storage                        // using Model as reference (sizeof(T)==sizeof(Model), alignof(T)==alignof(Model))
    {
        alignas(Model) char data_[sizeof(Model)];
    
        T& data() { return reinterpret_cast<T&>(data_); }
        T& data() const { return reinterpret_cast<const T&>(data_); }
    
        template <typename... U>
        typed_storage(U&&... args) { new (static_cast<void*>(data_)) T(std::forward<U>(args)...); }
    
        typed_storage(typed_storage& other)        : typed_storage(other.data()) {}
        typed_storage(const typed_storage& other)  : typed_storage(other.data()) {}
        typed_storage(typed_storage&& other)       : typed_storage(std::move(other.data())) {}
        typed_storage(const typed_storage&& other) : typed_storage(std::move(other.data())) {}
    
        typed_storage& operator=(const typed_storage& rhs) { data()=rhs.data(); return *this; }
        typed_storage& operator=(typed_storage&& rhs)      { data()=std::move(rhs.data()); return *this; }
    
        ~typed_storage()
        {
            static_assert( sizeof(T) == sizeof(Model), "" );
            static_assert( alignof(T) == alignof(Model), "" );
            data().T();
        }
    };
    

    und dann einfach node_space<T> durch typed_storage<node<T>, node_space_detail<T>> ersetzen.

    happystudent schrieb:

    Das sieht ganz schön krass aus... also hier im Forum liest man ja immer das rohes new, void pointer, reinterpret_cast und explizites Destruktor aufrufen quasi Todsünden sind, das ist jetzt hier alles auf einmal drin... Das verunsichert mich jetzt ein wenig 😃

    Todsünden sind sie in der Regel dann, wenn es Alternativen gibt. das rohe new ist ein placement new - dazu gehört normalerweise ein expliziter Destruktoraufruf, so wie beim normalen new ein delete folgt. Natürlich könnte man den Destruktoraufruf durch einen unique_ptr o.ä. durchführen lassen, nur müsste man dafür einen extra Deleter schreiben. Und der enthielte dann auch nur wieder den Destruktoraufruf...

    happystudent schrieb:

    Wenn man also kein Objekt von "sich selbst" speichern kann, kann man doch auch sicher keinen vector davon speichern dachte ich mir.

    Da ein vector-Objekt die Elemente nicht direkt selbst enthält ist diese Schlussfolgerung nicht zwingend.

    happystudent schrieb:

    Jetzt hab ich das aber einfach mal ausprobiert:

    struct test
    {
        std::vector<test> t; // Funktioniert!
    };
    

    und es kompiliert anstandslos! Wie kann das sein? Warum kann ich kein einzelnes Objekt in der Klasse haben (da Typ unvollständig) aber einen vector aus mehreren solchen Objekten schon?? Das macht doch gar keinen Sinn?

    Ein vector enthält typischerweise nur ein paar Zeiger. Zeiger können auch für unvollständige Typen definiert werden. Es ist also nicht soo überraschend, dass der Compiler das akzeptiert. Es könnte sogar funktionieren.
    Fakt ist aber auch, dass der Standard es ausdrücklich verbietet, Templates der Standardbibliothek mit unvollständigen Typen zu instantiieren (mit ein paar expliziten Ausnahmen). Das Resultat ist folglich undefiniertes Verhalten.



  • camper schrieb:

    Todsünden sind sie in der Regel dann, wenn es Alternativen gibt. das rohe new ist ein placement new - dazu gehört normalerweise ein expliziter Destruktoraufruf, so wie beim normalen new ein delete folgt. Natürlich könnte man den Destruktoraufruf durch einen unique_ptr o.ä. durchführen lassen, nur müsste man dafür einen extra Deleter schreiben. Und der enthielte dann auch nur wieder den Destruktoraufruf...

    Ok, aber ist das wirklich alles notwendig für so ein "allerwelts" Problem? Weil in meiner Vorstellung wären diese Dinge halt nicht so verteufelt wenn man sie bereits für solche einfachen Sachen benötigt, da die einem dann ja ständig über den Weg laufen würden?

    Spricht zum Beispiel etwas gegen folgende Lösung:

    #include <iostream>
    #include <vector>
    #include <memory>
    
    template <class T>
    class node
    {
    public:
    	T value;
    	std::vector<std::shared_ptr<node<T>>> children;
    };
    
    template <class T>
    class tree
    {
    public:
    	node<T> base;
    
    	void add_child_to_base(node<T> const &n)
    	{
    		base.children.push_back(std::make_shared<node<T>>(n));
    	}
    };
    
    int main()
    {
    	tree<int> t;
    	node<int> node;
    	node.value = 42;
    
    	t.add_child_to_base(node);
    	t.add_child_to_base(node);
    	t.add_child_to_base(node);
    
    	for (auto const &node : t.base.children) {
    		std::cout << node->value << '\n';
    	}
    }
    

    ?

    Hier benutze ich halt einen shared_ptr mit einem unvollständigem Typ was auch soweit hinhaut, nur: ist das auch UB? Wäre ja ziemlich blöd, weil smart pointer ja "normalen" pointern ziemlich nahe kommen sollten und wenn man die nicht mit unvollständigen Typen verwenden kann wäre das ja nicht gegeben... Oder ist das eine der expliziten Ausnahmen die du erwähnt hast?


  • Mod

    happystudent schrieb:

    Hier benutze ich halt einen shared_ptr mit einem unvollständigem Typ was auch soweit hinhaut, nur: ist das auch UB? Wäre ja ziemlich blöd, weil smart pointer ja "normalen" pointern ziemlich nahe kommen sollten und wenn man die nicht mit unvollständigen Typen verwenden kann wäre das ja nicht gegeben... Oder ist das eine der expliziten Ausnahmen die du erwähnt hast?

    shared_ptr ist eine der erwähnten Ausnahmen (das ist ein wesentliches Designziel bei shared_ptr). Das ist also grundsätzlich in Ordnung so, nur eben möglicherweise letzlich nicht ganz so effizient.



  • camper schrieb:

    shared_ptr ist eine der erwähnten Ausnahmen (das ist ein wesentliches Designziel bei shared_ptr). Das ist also grundsätzlich in Ordnung so, nur eben möglicherweise letzlich nicht ganz so effizient.

    Ahh, Ok, jetzt glaub ich hab ich kapiert 🙂

    Das mit der Effizienz ist jetzt nicht ganz so extrem wichtig, dann werde ich die einfachere Lösung verwenden. Auf jeden Fall vielen Dank für die Erklärungen 👍


Anmelden zum Antworten