Probleme beim Includen einer Header-Datei



  • Hallo,
    ich bin neu beim Programmieren in C++ und habe jetzt begonnen eine Node-Klasse für einen Binärbaum zu schreiben:

    Node.hpp:

    #pragma once
    
    template <class T>
    class Node {
    	T value;
    	Node *left;
    	Node *right;
      public:
    	Node (T value);
    	T getValue();
    	Node getLeft();
    	Node getRight();
    	void setLeft(Node &left);
    	void setRight(Node &right);
    	bool isLeave();
    };
    

    Node.cpp:

    #include "Node.hpp"
    #include <iostream>
    
    using namespace std;
    
    template<class T>
    Node<T>::Node (T value)
    {
    	this->value = value;
    }
    
    template<class T>
    inline T Node<T>::getValue() {
    	return value;
    }
    
    template<class T>
    inline Node<T> Node<T>::getLeft() {
    	return *left;
    }
    
    template<class T>
    inline Node<T> Node<T>::getRight() {
    	return *right;
    }
    
    template<class T>
    inline void Node<T>::setLeft(Node<T> &left) {
    	this->left = &left;
    }
    
    template<class T>
    inline void Node<T>::setRight(Node<T> &right) {
    	this->right = &right;
    }
    
    template<class T>
    inline bool Node<T>::isLeave() {
    	return left == nullptr && right == nullptr;
    }
    

    Allerdings musste ich feststellen, dass ich doch einiges noch nicht hinbekomme:

    1. Ich würde "value" gerne als Konstante definieren, allerdings kriege ich das nicht so hin, dass keine Fehlermeldung auftaucht.

    2. funktioniert die Funktion isLeave() nicht. Aus Java kenne ich da sowas wie x == null, was es in c++ nicht zu geben scheint und ich verstehe nicht so wirklich, wie man das alternativ macht

    3. Ich habe eine Test-Main-Funktion:

    int main () {
      Node <int> myobject (75);
      Node <int> myobject2 (100);
      
      myobject.setLeft(myobject2);
      
      cout << myobject.getValue() << endl;
      cout << myobject.isLeave() << endl;
      cout << myobject.getLeft().getValue() << endl;
      cout << myobject.getLeft().isLeave() << endl;
      
      return 0;
    }
    

    Wenn ich diese jetzt in Node.cpp schreibe, geht es, wenn ich das in eine eigene Datei schreibe (und dort natürlich Node include) kriege ich Fehlermeldungen wie "undefined reference to 'Node<int>::Node(int)", woran liegt das.

    1. Die Klasse liegt in einem Unterordner BinaryTree und wenn ich jetzt versuche Node.hpp in einer Datei außerhalb dieses Ordners zu includen, sagt der mir die ganze Zeit "file not found", gibts da nen Trick?

    2. Und zu guter letzt wäre es noch schön, wenn ich eine Rückmeldung bekommen könnte, ob die Getter und Setter von left und right so richtig sind, oder ob man das anders machen würde.

    Vielen Dank!



  • @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.



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

    Fehlermeldungen wie "undefined reference to 'Node<int>::Node(int)", woran liegt das.

    Faustregel: Templates werden nur im Header definiert. Es gibt keine cpp.

    Grund: der Compiler muss den vollständigen Templatecode sehen, wenn das Template benutzt wird, weil erst an dieser Stelle tatsächlich Code mit den echten Datentypen generiert wird.



  • @axels okay, danke. Wieso kann ich in die Variablen left und right eigentlich nur mit * deklarieren und bekomme, wenn ich diesen weglasse eine Fehlermeldung?



  • @manni66 alles klar, dann werde ich das ändern, auch wenn ich das aus Übersichtsgründen nicht so prickelnd finde.



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

    Wieso kann ich in die Variablen left und right eigentlich nur mit * deklarieren und bekomme, wenn ich diesen weglasse eine Fehlermeldung?

    https://en.cppreference.com/w/cpp/language/type#Incomplete_type



  • Hat noch jemand eine Idee, woran das mit dem "File not found"-Problem liegt?



  • #include "BinaryTree/node.hpp"
    

    Sonst musst Du sagen wie genau Du compilierst.



  • @Swordfish Das habe ich schon probiert, geht nicht. Und wie genau ich kompliere kann ich nicht sagen, aber das hier scheint der BEfehl zu sein, mit dem das gemacht wird:
    ..../mingw32-make.exe -j8 SHELL=cmd.exe -e -f Makefile
    ich hoffe das hilft



  • @axels Ich habe unter private jetzt folgendes stehen:

    Node<K, T> *left = nullptr;
    

    und unter public habe ich zum Beispiel eine Funktion

    bool add(K &key, T &value);
    

    Die ich versucht habe folgendermaßen zu implmentieren:

    template<class K, class T>
    inline bool Node<K, T>::add(K &key, T &value) {
    	if(this->key == key)
    		return false;
    	if(this->key > key)
    		left.add(key, value);
    	if(this->key < key)
    		right.add(key, value);
    	return false;
    }
    

    wobei

    left.add(key, value);
    

    für Fehler sorgt. Wenn ich stattdessen

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

    geht das. Wie überspringe ich diesen Zwischenschritt?



  • @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.


Log in to reply