Probleme beim Includen einer Header-Datei



  • @CptK sagte in Probleme beim Includen einer Header-Datei:

    wobei 
    ```cpp
    left.add(key, value);
    

    für Fehler sorgt.

    Ja. Weil left ein Zeiger ist. Den musst du mit -> de-referenzieren, nicht mit ..

    Wenn ich stattdessen

    Node<K, T> l = left;
    l.add(key, value);
    

    geht das. Wie überspringe ich diesen Zwischenschritt?

    Bist du sicher? Ich kann mir vorstellen dass es "funktioniert" (=du bekommst keine Fehlermeldung) so lange du die Funktion nicht instanzierst. Ich sehe aber keinen passenden Konstruktor mit dem das wirklich funktionieren sollte.
    Ausserdem ist das nicht bloss ein "Zwischenschritt". Es würde ganz was anderes machen.



  • Die Schnittstelle ist aber noch verbesserungswürdig:

    Node *left;
    Node *right;
    // ...
    Node getLeft();
    Node getRight();
    
    void setLeft(Node &left);
    void setRight(Node &right);
    

    Warum werden hier 3 verschiedene Zugriffsmechanismen (Zeiger, Kopie, Referenz) benutzt?
    Besser wäre hier, nur Zeiger zu benutzen.

    PS: Außerdem sollten alle Getter als const markiert werden (const correctness).

    Und isLeave sollte wohl isLeaf heißen (nur die Mehrzahl heißt leaves), s. leaf vs. leave.



  • @hustbaer Ich habe das jetzt so geändert, wodurch meine add jetzt wie folgt aussieht:

    template<class K, class T>
    inline bool Node<K, T>::add(K &key, T &val) {
    	if(this->key > key) {
    		if(left != nullptr)
    			return left->add(key, val);
    		else {
    			Node<K, T> n(key, val);
    			left = &n;
    			return true;
    		}
    	}
    	if(this->key < key) {
    		if(right != nullptr)
    			return right->add(key, val);
    		else {
    			Node<K, T> n(key, val);
    			right = &n;
    			return true;
    		}
    	}
    	return false;
    }
    

    Es funktioniert auch alles dahingehend, dass ich keine Fehler bekomme, wenn ich das aber ausführe und mir das Ergebnis ausgeben lasse, kommt da ganz wildes Zeug raus....



  • @CptK sagte in Probleme beim Includen einer Header-Datei:

    Es funktioniert auch alles dahingehend, dass ich keine Fehler bekomme, wenn ich das aber ausführe und mir das Ergebnis ausgeben lasse, kommt da ganz wildes Zeug raus....

    Das wird daran liegen, dass du in Zeile 7 und 16 lokale Objekte erzeugst und deren Adresse an deine Pointer left und right zuweist. Die lokalen Objekte werden aber bei verlassen des Blocks zerstört und somit zeigen deine Zeiger auf nonsense. Erzeuge deine Objekte dynamisch dann sollte sich das Problem lösen.



  • @axels ahhh okay, das macht Sinn. Jetzt muss ich Objekte, die mittels "new" erzeugt wurden ja auch wieder manuell löschen. Ich habe noch eine remove-Funktion, in der das dann gemacht werden muss, aber wie ist das mit dem Rest, wird das alles automatisch wieder freigegeben, wenn das Programm beendet wird oder muss ich da irgendwie manuell den gesamten Baum vorher löschen?



  • @CptK sagte in Probleme beim Includen einer Header-Datei:

    aber wie ist das mit dem Rest, wird das alles automatisch wieder freigegeben, wenn das Programm beendet wird oder muss ich da irgendwie manuell den gesamten Baum vorher löschen?

    Welcher Rest? Ja, wenn dein Programm beendet wird, gibt das OS den gesamten Speicher wieder frei, nur ist das nicht im Sinne des Erfinders. Wenn du deinen Baum löschen willst löscht du rekursiv von den Blättern beginnend, alle Knoten des Baumes und abschliesend die Wurzel.



  • @axels

    @axels sagte in Probleme beim Includen einer Header-Datei:

    Ja, wenn dein Programm beendet wird, gibt das OS den gesamten Speicher wieder frei, nur ist das nicht im Sinne des Erfinders. Wenn du deinen Baum löschen willst löscht du rekursiv von den Blättern beginnend, alle Knoten des Baumes und abschliesend die Wurzel.

    Das rekusrive löschen würde ich dann im Destructor machen richtig?



  • @CptK Ja



  • Langsam tuts mir leid, dass ich hier viele (vermutlich dämliche) Fragen stellen muss, aber ich hänge wieder bei etwas. Ich habe versucht eine Funktion remove zu schreiben, die einen einzelnen Knoten löscht. Zum einen mault der Compiler an zwei Stellen (die im Code gekennzeichnet sind) und ich habe das Gefühl, dass das ein ziemliches Durcheinander mit Pointern und Co. ist, bei dem ich nicht glaube, dass man das so machen sollte:

    template<class K, class T>
    inline Node<K, T> Node<K, T>::remove(K &key, Node<K, T> &parent) {
    	
    	if(this->key == key) {
    		Node<K, T> res = *this;
    		if(parent == nullptr) { /// FEHLER
    			
    		}
    		// Check if the Node to delete is leaf
    		else if(isLeaf()) {
    			if(key < parent.key)
    				parent.left = nullptr;
    			else
    				parent.right = nullptr;
    		// Check if Node to delete has only one child
    		} else if (!(left == nullptr && right == nullptr) && (left != nullptr || right != nullptr)) {
    			Node<K, T>* next = left != nullptr ? left : right;
    			if(key < parent.key)
    				parent.left = next;
    			else
    				parent.right = next;
    		// Check if Node has a parent and two children
    		} else {
    			Node<K, T> ref = *this, p = *this;
    			if(left->depth() > right->depth()) {
    				ref = *left;
    				while(!ref.isLeaf()) {
    					p = ref;
    					ref = ref.right != nullptr ? *ref.right : *ref.left;
    				}
    			} else {
    				ref = *right;
    				while(!ref.isLeaf()) {
    					p = ref;
    					ref = ref.left != nullptr ? *ref.left : *ref.right;
    				}
    			}
    			ref.left = left;
    			ref.right = right;
    			
    			if(ref.key < p.key)
    				p.left = nullptr;
    			else
    				p.right = nullptr;
    			if(key < parent.key) 
    				parent.left = &ref;
    			else
    				parent.right = &ref;
    		}
    		delete this;
    		return res;
    	}
    	if(this->key > key)
    		return left->remove(key, *this);
    	if(this->key < key)
    		return right->remove(key, *this);
    	return nullptr; /// Fehler
    }
    


  • Gefühlt viel zu aufwendig. Schreibe einfach einen Destruktor für deine Node Klasse der jeweils delete für left und right ausführt.

    template<class K, class T>
    Node<K,T>::~Node<K,T>(){
        if (left != nullptr){
             delete left;
       }
       if (right != nullptr){
          delete right;
       }
    }
    

    Damit sollte rekursiv für left und right jeweils die Destruktoren aufgerufen werden und dort wiederum die derer Kinder.



  • Gibt´s nen Grund, die Kindknoten nicht in einem smart_pointer (std::unique_ptr/std::shared_ptr) zu speichern? Das Interface kann gleich bleiben (Raw-Pointer per .get() zurückgeben), aber der Destruktor wird überflüssig.



  • @axels achso ne die oben geschickte Funktion soll nur einen einzelnen Knoten aus dem Baum löschen und den Rest entsprechend verbinden



  • @axels sagte in Probleme beim Includen einer Header-Datei:

    @CptK Wenn du rohe Zeiger für left und right verwenden willst, musst du diese zu bei Erzeugung des Objekts mit nullptr initialisieren. Dann klappt auch dein Vergleich in isLeave.

    Genau das gleiche Problem hatte ich auch! Hat bei mir funktioniert. Klasse danke für den Tipp!
    Liebe Grüße


Anmelden zum Antworten