Baum-Design

zum komischen baum:

nur GNodes können Kinder haben, Node* root wird immer vom Typ GNode sein, da Node ohnehin rein virtuell ist.

Aber wie ich deine Antwort jetzt verstanden habe sollte ich die Alternative mit der statischen Methode nehmen, oder?
Dabei sollte ich aber noch beachten dass parent != 0 ist, da ich meine Kinder sonst in die Luft hänge ...

Hmm du hast die Vorgehensweise grad so schön erklärt, kannst du das auch für die von mir gewünschte Funktion

deleteSubtree(GNode* n)
{
    noch unklar....
}

Sinn und Zweck soll es sein einen Baum ab einem bestimmten Knoten rekursiv zu löschen.

meine Gedanken dazu:

Ich muss den Baum erstmal hinabsteigen... bis auf SNodes, oder LNodes, die können eh keine Kinder haben

std::list<Node*>::iterator iter;
for(iter = children.begin(); iter!= children.end(); iter++)
{
    Node* tmp = *iter;
    if(tmp->type == SNode)
    {
        delete SNode;
    }
    else( Node::deleteSubTree(tmp) );
}

stopp da geht was schief... so lösche ich nur die Snodes...
falls du das so schön in worte fassen kannst wie das vorgehen sein sollte... wäre schön. Ich häng da irgendwo...

so nachdem ich mir das mal aufgemalt habe bin ich zu folgendem gekommen:

Node::removeSubtree(GNode* n)
{
    std::list<Node*>::iterator iter;
while(! list.empty())
{
    for(iter = children.begin(); iter!= children.end(); iter++)
    {
        Node* tmp = *iter;
        if(tmp->type == SNode)
        {
            delete SNode;
            iter = list.erase(iter);
        }
        else( Node::delete(tmp) );
    }
}
}

Ich hoffe das könnte hinhaun

volkard

Mir scheint, es geht einfacher.

static Node::deleteSubtree(GNode* toDel)
{
    std::list<Node*>::iterator iter;
    for(iter = toDel->children.begin(); iter!= toDel->children.end(); iter++)
    {
        Node* tmp = *iter;
        if(tmp->type == SNode)
        {
            delete SNode;
        }
        else{
             removeSubtree(tmp);
        };
    }
    Node::delete(toDel);
}

ich habs mir mal kurz angeschaut, das sollte hinkommen, das prinzip hab ich mal auf schmierpapier probiert, sah gut aus,

das einzige.. ich

mach mir sorgen weil aus den listen nichts gelöscht wird...

Wenn nämlich delete(node*)

jetzt die kinder weitergeben will, was passiert dann?
die liste ist nicht leer, aber der speicherbereich wurde doch schon freigegeben.

Dann ist es auch klar was du willst. Eine Methode "Tree::removeNode(Node* node)", die sich das parent schnappt, die children von node an parent zuweist, vorher den children das neue parent verpasst. Damit ist node befreit und kann gelöscht werden.

Das Kinder weitergeben könnte Probleme machen, oder?

l'abra d'or

Wie wäre diese Kombi:

void
Node::removeNode(Node* rem) {
  while( !rem->children.empty() ) {
    Node* n = rem->children.pop_fron();
    n->parent = rem->parent;
  }
  // rem->children is empty
  delete rem;
}

void
Node::removeSubtree( Node* n ) {
  delete n;
}

Node::~Node() {
  while( !children.empty() ) {
    delete children.pop_back();
  }
}

delete node; macht die ganze node samt children platt.
Können wir direkt für removeSubtree nehmen.

hmm die lösung hatte mir gefallen nur meckert er grad rum:

error: type ‘void’ argument given to ‘delete’, expected pointer

sg::GroupNode::~GroupNode()
{
    while( !children.empty() )
    {
        delete this->children.pop_back();
    }
}

ich kanns mir leider nicht ganz erklären,
vlt hängst damit zusammen, dass children eine list vom virtuellen basistypen ist?

std::list< Node* > children

shisha schrieb:

error: type ‘void’ argument given to ‘delete’, expected pointer
sg::GroupNode::~GroupNode()
{
    while( !children.empty() )
    {
        delete this->children.pop_back();
    }
}
ich kanns mir leider nicht ganz erklären,

Was verstehst Du denn an der Fehlermeldung nicht? Steht doch klipp und klar da. Tipp: pop_back tut nicht genau das, was Du erwartest.

omg, danke.

ich frag mich zwar, wer entschieden hat dass pop void als rückgabetyp hat, aber so ist alles klar

bevor ich noch mehr dummheiten anstelle:
wenn ich delete weglasse, sollte ja alles klappen?

pop ruft den destruktor auf und hauts aus der liste raus?!

shisha schrieb:

ich frag mich zwar, wer entschieden hat dass pop void als rückgabetyp hat

Da gibt es auch eine gute Begründung für. Ausnahme-Sicherheit. Wenn pop_back eine Kopie des Elements zurückgeben soll, dann müsste man es so machen:

template<typename T>
T my_pop_back(vector<T> & vec)
{
  T ret = vec.back();
  vec.pop_back();
  return ret;
}

Hier kann aber nicht mehr die "starke Garantie" (strong guarantee) gegeben werden. Bei der Rückgabe von ret muss eine Kopie erstellt werden, was fehlschlagen kann. my_pop_back leitet die Ausnahme weiter an den Aufrufer. Das Element ist dann aber verloren gegangen und auch nicht mehr im Vektor vorhanden.

shisha schrieb:

bevor ich noch mehr dummheiten anstelle:
wenn ich delete weglasse, sollte ja alles klappen?

pop ruft den destruktor auf und hauts aus der liste raus?!

pop_back entfernt das letzte Element aus dem Vektor. Da Du einen Vektor aus Zeigern hast, passiert nichts weiter. Zeiger haben sozusagen Destruktoren, die nichts tun -- genauso wie jeder andere "skalare Typ" auch (int, double, ...). Wenn Du das, worauf der Zeiger zeigt, löschen willst, könntest Du das zB so machen:

template<typename Pointee>
void delete_pointees(vector<Pointee*> & vop)
{
  while (!vop.empty()) {
    delete vop.back();
    vop.pop_back();
  }
}