Template Template Problem bei Initialisierung

[ichwillkaffee]

Hallöchen!

Ich sitze schon geraume Zeit vor dem Problem, dass ich Programme ohne einige der Standartbibliotheken wie STL schreiben muss. Also dachte ich, dass ich mir die Datenstrukturen eben selbst erstelle. Ich habe einen AVL Baum und einen Vector implementiert die auch mit primitiven Datentypen einwandfrei funktionieren. Wenn ich aber einen AVL Baum in einen Vector speichern will schmiert das Programm ab.
Hier einige Code-Auszüge:

int main() {
  AVL_Tree<int> t;
  t.insert(8);
  t.insert(11);
  t.insert(2);
  ...
  Vector< int, AVL_Tree > avlvec;
  avlvec.addFirst(t);
  cout << "t inserted"<< endl;
  return 0;
}

Die Ausgabe sieht wie folgt aus:
first setVal
zuweisung
8
zuweisung2
zuweisung fertig
index set
size ++
make: *** [test] Segmentation fault

Quellcode aus den benutzten Klassen:

template <typename T, template <typename> class Cont> class Vector {
private:
  VectorNode<T, Cont> *first, *last;
  int size;
public:
  Vector () {
    size = 0;
    first = new VectorNode<T,Cont> ();
    last = first;
  }
  ...
  void addFirst(Cont<T> t) {
    if (size == 0) {
      cout << "first setVal" << endl;
      first->setValue(t);
      first->setIndex(0);
      cout << "index set" << endl;
      size++;
      cout << "size ++" << endl;
      first->getValue().inOrder(cout);  //hier scheint es zu knallen
      cout << "return" << endl;
      return;
    }
    VectorNode<T,Cont> *new_first = new VectorNode<T,Cont> (t);
    VectorNode<T,Cont> *tmp = first;
    new_first->setNext(tmp);
    first = new_first;
    tmp->setPrev(first);
    tmp->setIndex(1);
    size++;
  }
  ...
  virtual ~Vector() {
    delete first;
  }
};

template <typename T, template <typename> class Cont> class VectorNode {
private:
  VectorNode<T, Cont> *prev, *next;
  int index;
  Cont<T> value;
public:
  VectorNode() {
    next = prev = NULL;
    index = -1;
  }

  VectorNode(Cont<T> t) {
    value = t;
    cout << "VectorNode Baum zugewiesen" << endl;
    next = NULL;
    prev = NULL;
    index = 0;
    cout << "GraphNode erstellt" << endl;
  }
  ...
  Cont<T> getValue() {
    if (index >= 0) {
      return value;
    }
  }
  ...
  virtual ~VectorNode() {
    delete next;
  }
};

template<class T> class AVL_Tree {
private:
  T value;
  AVL_Tree<T> *left;
  AVL_Tree<T> *right;
  int height, size;
  ...
  AVL_Tree() {
    value = T();
    left = NULL;
    right = NULL;
    size = 0;
    height = 0;
  }

  void operator=(AVL_Tree<T> &other) {
    cout << "zuweisung" << endl;
    value = other.value;
    cout << value << " " << endl;
    cout << "zuweisung2" << endl;
    left = other.left;
    right = other.right;
    size = other.size;
    height = other.height;
    cout << "zuweisung fertig" << endl;
  }

  virtual ~AVL_Tree() {
    delete left;
    delete right;
  }
  ...
};

Also wie gesagt es hat alles ganz wunderbar funktioniert bis ich versuchte die Klassen zu kombinieren. Hoffentlich gibt es hier einen Experten, der oder die mir helfen kann. Danke im Voraus

[krümelkacker]

> Ich sitze schon geraume Zeit vor dem Problem, dass ich Programme ohne einige der Standartbibliotheken wie STL schreiben muss.

Wieso das denn? Wer sagt das?

[ichwillkaffee]

Weil unsere Übungsleiterin offensichtlich der Meinung ist, dass es sonst zu leicht wäre...

[brotbernd]

Cont<T> getValue()
{
    if (index >= 0) {
      return value;
    }
}

else ? -> nix -> puff

Der GCC kompiliert das ohne Warnung oder? Das hat mich auch schon öfter genervt.

[ichwillkaffee]

vielleicht kein schöner stil aber auch kein problem. ich benutze g++ und der meckert schon oft genug^^

[brotbernd]

Das sollte kein Stilgemecker sein, sondern dort vermute ich nach Überfliegen den Fehler.

first->getValue().inOrder(cout);  //hier scheint es zu knallen

getValue gibt nix zurück worauf du inOrder aufrufen könntest.

[ichwillkaffee]

ich bin schon ein kkleines sück weiter gekommen und zwar habe ich den überladenen operator im AVL_Baum rausgenommen und durch einen copyconstruktor ersetzt jetzt knallt es erst später

[ichwillkaffee]

ich habe für alle klassen entsprechende copy konstruktoren geschrieben und nun läuft die main durch. allerdings stehe ich nun vor dem problem, dass dann ein seg-fault entsteht:

==3075== HEAP SUMMARY:
==3075== in use at exit: 40 bytes in 1 blocks
==3075== total heap usage: 23 allocs, 38 frees, 584 bytes allocated

[Gast]

ichwillkaffee schrieb:

ich habe für alle klassen entsprechende copy konstruktoren geschrieben und nun läuft die main durch. allerdings stehe ich nun vor dem problem, dass dann ein seg-fault entsteht:

==3075== HEAP SUMMARY:
==3075== in use at exit: 40 bytes in 1 blocks
==3075== total heap usage: 23 allocs, 38 frees, 584 bytes allocated

Du gibst scheinbar Speicher doppelt frei.

In dem Code, den du gepostet hast allerdings (glaube ich) nicht.

Vermutlich erstellt dein Copy-Konstruktor keine neuen Knoten, sondern
verwendet die alten Zeiger und gibt sie beim delete somit doppelt frei.

Hast du den CopyConstructor denn implementiert?
Falls nein, hab ich wohl recht

[Gast]

Der Copy-Constructor sollte (ungetestet) ungefähr so aussehen...

public:
AVL_Tree(const AVL_Tree<T>& toCopy) {
    value = toCopy.value;
    if(toCopy.left != NULL){
        left = new AVL_Tree<T>(*toCopy.left);
    } else{
        left = NULL;
    }
    if(toCopy.right != NULL){
        right=new AVL_Tree<T>(*toCopy.right);
    } else{
        right = NULL;
    }
    size = toCopy.size;
    height = toCopy.height;
}

[ichwillkaffee]

Die Konstruktoren sind implementiert:

AVL_Tree(const AVL_Tree<T> &other) {
    value = other.value;
    left = other.left;
    right = other.right;
    size = other.size;
    height = other.height;
  }

  Vector (const Vector<T,Cont> &other) {
    first = other.first;
    last = other.last;
    size = other.size;
  }

  VectorNode(const VectorNode<T,Cont> &other){
    prev = other.prev;
    next = other.next;
    index = other.index;
    value = other.value;
  }

Ich habe an den Destruktoren nichts geändert... sehe auch noch nicht wo der Fehler sein könnte.

[Gast]

Bei deinem

void operator=(AVL_Tree<T> &other)

, den du ja rausgenommen hast, besteht übrigens genau das gleiche Problem...

Du kopierst nur Zeiger auf Objekte, die beim Löschen eines der beiden
AVL__Bäume zerstört werden und dann gibts den Segmentation-Fault

[brotbernd]

Du kopierst da nur die Zeiger. Nach so einer Kopie wird dann in zwei Destruktoren delete für left und right auf die gleiche Instanz aufgerufen.

[Gast]

EDIT: berndbrot hat recht, ich war nur zu langsam

ichwillkaffee schrieb:

Die Konstruktoren sind implementiert:

AVL_Tree(const AVL_Tree<T> &other) {
    value = other.value;
    left = other.left;
    right = other.right;
    size = other.size;
    height = other.height;
  }

  Vector (const Vector<T,Cont> &other) {
    first = other.first;
    last = other.last;
    size = other.size;
  }

  VectorNode(const VectorNode<T,Cont> &other){
    prev = other.prev;
    next = other.next;
    index = other.index;
    value = other.value;
  }

Ich habe an den Destruktoren nichts geändert... sehe auch noch nicht wo der Fehler sein könnte.

Wieso auch?

Also...

Sobald du eine Kopie von z.B. AVL_Baum erstellst, kopiert er die Zeiger
auf die Kind-Knoten.
Wenn du deinen AVL_Baum jedoch löschst, löschst du auch die Kind-Knoten,
die dann in deinen Kopien (oder im Original) auch nicht mehr verfügbar sind.
Alle Kind-Knoten existieren nur einmal!!!

EDIT2:
Das gleiche Problem besteht auch bei deinem Vector (, der übrigens ne List ist ),
jedoch mußt du hier aufpassen, dass insbesondere last und prev, auf deine neu erstellten
VectorNode verweist.

[ichwillkaffee]

jeah!!! ich hab es gelöst. man braucht nicht nur einen copy constructor sondern muss auch den "=" operator überschreiben *grooße freude*

AVL_Tree() {
    left = NULL;
    right = NULL;
    size = 0;
    height = 0;
  }

  AVL_Tree(T &t) {
    value = t;
    left = NULL;
    right = NULL;
    size = 1;
    height = 0;
  }

  AVL_Tree(const AVL_Tree<T> &other) {
    value = other.value;
    if (other.left != NULL) {
      left = new AVL_Tree<T> (*other.left);;
    } else {
      left = NULL;
    }
    if (other.right != NULL) {
      right = new AVL_Tree<T> (*other.right);
    } else {
      right = NULL;
    }
    size = other.size;
    height = other.height;
  }

  void operator=(AVL_Tree<T> &other) {
    cout << "assignment operator " << endl;
    value = other.value;
    if (other.left != NULL) {
      left = new AVL_Tree<T> (*other.left);
    } else {
      left = NULL;
    }
    if (other.right != NULL) {
      right = new AVL_Tree<T> (*other.right);
    } else {
      right = NULL;
    }
    size = other.size;
    height = other.height;
  }

  virtual ~AVL_Tree() {
    delete left;
    delete right;
  }

danke an alle die geholfen haben ich würd euch ja einen ausgeben...
kann man das thema irgendwo als gelöst abhaken?

[drakon]

Schau dir doch mal das Copy/Swap Idiom an für den Zuweisungsoperator. Im Moment ist das eher unschön wegen Code Verdopplung.
Initialisierungslisten wären auch mal etwas zum nachschlagen.

kann man das thema irgendwo als gelöst abhaken?

Viele ändern den Titel indem sie ein [Gelöst] vorne anhängen.

Wenn du einen ausgeben willst, dann musst du ans Forentreffen kommen.