Pointer-Problem



  • Hallo!

    Ich habe ein großes Problem mit meiner BinaryTreeNode-Klasse und deren Pointern. Vorweg am besten mal eine kurzversion (ohne unnötige Methoden etc.) meiner Klasse, und den Code, der sie benutzt:

    #ifndef _BINARYTREENODE_H
    #define _BINARYTREENODE_H
    
    #include <iostream>
    
    using namespace std;
    
    template <class T> class BinaryTreeNode;
    
    template <class T>
    class BinaryTreeNode
    {
    public:
    	BinaryTreeNode(const T& _Element, const int& _weight);
    	~BinaryTreeNode();
    	BinaryTreeNode(const T& _Element, const int& _weight, BinaryTreeNode& l, BinaryTreeNode& r);
    
    	BinaryTreeNode<T>* left;
    	BinaryTreeNode<T>* right;
    
    	T Element;
    	int weight;
    };
    
    template <class T>
    BinaryTreeNode<T>::BinaryTreeNode(const T& _Element, const int& _weight)
    {
    	Element = _Element;
    	weight = _weight;
    	left = 0;
    	right = 0;
    }
    
    template <class T>
    BinaryTreeNode<T>::~BinaryTreeNode()
    {
    }
    
    template <class T>
    BinaryTreeNode<T>::BinaryTreeNode(const T& _Element, const int& _weight, BinaryTreeNode& l, BinaryTreeNode& r)
    {
    	Element = _Element;
    	weight = _weight;
    	left = &l;
    	right = &r;
    }
    
    #endif
    

    In meinem code will ich folgendes machen: Ich habe 2 BinaryTreeNodes in einem vector gespeichert, nun will ich die beiden daraus löschen und einen neuen BinaryTreeNode erstellen, welcher die beiden als "left" bzw. "right" subtree hat. Dazu rufe ich den entsprechenden Konstruktor auf:

    vector<BinaryTreeNode<char>> nodes; 
    
    // der vector nodes wurde bereits mit einigen nodes gefüllt! 
    
    while(nodes.size() > 1)
    {
    	// concatinate the two smallest nodes
    	BinaryTreeNode<char> l = nodes[0];
    	BinaryTreeNode<char> r = nodes[1];
    	nodes.erase(nodes.begin());
    	nodes.erase(nodes.begin());
    	BinaryTreeNode<char> n(' ', l.weight + r.weight, l, r);
    	nodes.push_back(n);
    
    	// re-sort the vector
    	sort(nodes.begin(), nodes.end(), compareNodes);
    }
    

    Das kuriose ist, dass alles beim ersten Durchlauf der Schleife funktioniert. Beim debuggen sind alle nodes am richtigen Ort. Doch beim 2. Durchlauf, funktioniert es nicht mehr, dann verschachtelt sich eine Node immer und immer wieder, sie zeigt also auf sich selbst. Ich bin mittlerweile mit meinem Latein am Ende und hab wirklich keine Ahnung mehr warum es nicht klappt.

    Der Punkt an dem sich alles verschachtelt tritt erst unmittelbar in der zweiten Zeile der schleife (beim 2. Durchgang) auf.

    Hat jemand eine Ahnung was ich hier falsch mache?

    Lieben Gruß und vielen Dank
    Christian



  • Ui...

    BinaryTreeNode<char> l = nodes[0];
        BinaryTreeNode<char> r = nodes[1];
    

    Du weißt, dass du dir hier auf dem Stack Objekte erstellst, auf die du dann
    später referenzierst? Deine Objekte werden aber nach der while Schleife wieder
    gelöscht -> deine Pointer zeigen ins Nirwana...
    Generell willst du wahrscheinlich eher:

    BinaryTreeNode<char>& l = nodes[0];
        BinaryTreeNode<char>& r = nodes[1];
    

    wobei das aber auch keine gute Idee ist, da beim Umkopieren des Vektors
    aufgrund von Größenwachstum die Zeiger ungültig werden können.

    EDIT: btw: Liegt vector<BinaryTreeNode<char>> nodes; auch auf dem Stack?
    EDIT2: Kennst du den Unterschied zwischen Stack und Heap?
    EDIT3: Bei nodes.push_back(n); wird übrigens auch wieder eine Kopie deines Knoten angelegt

    Gruß,
    CSpille



  • Hallo CSpille!

    Danke für deine Antwort, allerdings hab ich noch einige Fragen. Vorweg: ich bin noch c++ Anfänger! 🙂

    Also ich verstehe nicht ganz, welchen Stack du meinst? Also ich hab eigentlich nur die Nodes in einem vector und verbinde dann die ersten 2 nodes zu einer neuen node (als left und right child) und versuche, diese neue node zum vector hinzuzufügen. Das ganze soll, wenn es mal groß ist ein Algorithmus zum erstellen von Huffman-Codes werden.

    Den Unterschied zwischen heaps und stacks kenne ich, allerdings weiß ich nicht worauf du verweist.

    Da bei dem push_back befehl eine kopie angelegt wird, kann es sein, dass ich einen Copy-Constructor brauche?

    MFG
    Christian



  • l und r sind lokal, du übergibst sie im BinaryTreeNode-Konstruktor als Referenz und holst dir dann deren Adressen.
    Damit zeigen left und right auf die lokalen Nodes, die kurz darauf zerstört werden.



  • bruegge1987 schrieb:

    Den Unterschied zwischen heaps und stacks kenne ich, allerdings weiß ich nicht worauf du verweist.

    Wegen Verwendung des Plural gehe ich mal davon aus, dass du die generellen
    Datenstrukturen kennst, aber nicht auf C++ bezogen.

    Also in C++ kann man Objekte auf dem Heap und auf dem Stack ablegen.
    Auf dem Stack sind diese nur innerhalb des aktuellen Scopes {} gültig,
    auf dem Heap (Erstellung mit new) müssen sie explizit per delete gelöscht werden.

    Okay... Mal ein 'kurzer' Code-Auszug, der dir verdeutlichen soll, was
    eigentlich so passiert:

    #include <iostream>
    #include <vector>
    
    class A{
    int a;
    public: A(int a){
                    this->a = a;
                    std::cout << "create " << a << std::endl;
            }
    
            ~A(){
                    std::cout << "delete  (" << this->a << ")" << std::endl;
            }
    
            A(){
                    this->a = 0;
                    std::cout << "create" << std::endl;
            }
    
            A(const A& a){
                    this->a = a.a;
                    std::cout << "copy " << this->a << std::endl;
            }
    
            void operator=(const A& a){
                    std::cout << "assign " << a.a << " (" << this->a << ")" << std::endl;
                    this->a = a.a;
            }
    
            int getValue() const{
                    return this->a;
            }
    
    };
    
    void doSomething(){
            A a(9);
    }
    
    int main(){
            std::vector<A> vector;
            A* a1 = new A(1);
            A* a2 = new A(2);
            A a3(3);
            A a4b;
            vector.push_back(a3);
            vector.push_back(a4b);
            A* a5 = a1;
            A& a6(*a1);
            {
                    A a4(4);
                    a4b = a4;
                    std::cout << "new value " << a4b.getValue() << std::endl;
                    a5 = &a4;
                    a6 = a4;
                    doSomething();
                    std::cout << "before end of scope" << std::endl;
            }
            // do not dereference a5, its referencing the destroyed a4;
            // EDIT: Da ja entgegen meinem Vorhaben die Referenz nicht umgebogen wird, sondern der operator=() aufgerufen wird, kannst du a6 weiterhin verwenden...
            // the reference a6 is also not usable anymore
            std::cout << "after end of scope" << std::endl;
    
            delete a1;
            // printing elements in vector: (copies of) a3 & a4b
            // value of 'a4b' is 0, as it is a copy
            for(std::vector<A>::const_iterator it = vector.begin(); it!=vector.end(); ++it){
                    std::cout << "elem " << it->getValue() << std::endl;
            }
            // a2 is never deleted -> memory leak;
            return 0;
    }
    

    Ausgabe mit Kommentaren (kann (glaub ich) evtl. leicht abweichen):

    create 1 // Erstellung eines Objektes auf dem Heap -> gültig bis explizit delete aufgerufen wird
    create 2 // analog
    create 3 // Erstellung eines Objektes auf dem Stack
    create // Erstllung eines weiteren Objektes auf dem Stack per Default-Konstruktor (sowas machst du z.B. hier BinaryTreeNode<char> l = nodes[0];)
    copy 3 // Das Objekt wird in deinen Vektor kopiert
    copy 3 // Ein neues Element soll eingefügt werden -> dein Vektor braucht mehr platz -> internes umkopieren -> deswegen keine Referenzen oder Pointer auf Vektor-Elemente verwenden
    copy 0 // Kopie des neu eingefügten Elementes
    delete  (3) // Löschen des alten umkopierten Vektorinhalts
    create 4 // Erstelle neues Objekt auf dem Stack
    assign 4 (0) // Zuweisung des Objektinhalts an anderes Objekt (kein Objekt wird neu erstellt)
    new value 4 // Ausgage des neuen Wertes
    assign 4 (1) // hmm... Hier wollte ich eigentlich nur die Referenz umbiegen... Kommt gleich nen Post zu... Verstehe ich selbst nicht ^^
    create 9 // Erstellen eines neuen Stack-Objektes in der Unterprozedur
    delete  (9) // Zerstörung bei Verlassen der Funktion
    before end of scope
    delete  (4) // Zerstörung des Objektes bei Verlassen des Scopes
    after end of scope
    delete  (4) // Zerstörung des Heap-Objektes per delete (Neuer Inhalt von a1)
    elem 3 // Inhalt Element 0 von Vektor
    elem 0 // Inhalt Element 1 von Vektor, da Kopie immernoch 0 und nicht 4
    delete  (4) // Löschen des Stack-Objektes a4b
    delete  (3) // Löschen des Stack-Objektes a3
    delete  (3) // Löschen des Vektors auf dem Stack (0. Element)
    delete  (0) // Löschen des Vektors auf dem Stack (1. Element)
    

    Ich hoffe, ich verwirre dich nicht zu viel, aber anhand des Beispiels siehst
    du evtl. was eigentlich so alles passiert...

    Gruß,
    CSpille



  • Oh das ist ja prima!! Werd den code gleich mal compilieren und mit dem debugger durchgehen damit ich auch alles verstehe! Vielen vielen Dank für die Mühe!!! 🙂 Ich denke das Problem in meinem Code habe ich nun verstanden und bin auch in der Lage das zu lösen! Ich wusste gar nicht, dass C++ die Objekte in einem Stack UND einem Heap verwaltet. Naja, ich sollte mir vielleicht ein Buch zulegen!

    Also wie gesagt, ich werd' den code nun mal durchforsten und mir die ganzen integer alle der Reihe nach angucken. Vielen Dank nochmal, falls ich was tolles rausfinde, poste ich es hier 😉

    Lieben Gruß
    Christian


Log in to reply