Is a recursive destructor for linked list, tree, e

问题:

For my current learning exercise, I'm studying linked lists and trees. I saw a suggestion recently to destroy data structures recursively by having each node delete its child/children. However in nearly all of examples I've found, the node destructor is empty and some managing class handles destruction using some form of iteration and delete. From a reliability and/or stylistic perspective, is there anything inherently bad about the recursive destructor?

What follows is my implementation of my understanding of the two approaches.

Recursive destruction:

#include <iostream>
struct Node {
  static int count;
  Node() : num_(count++), p_next_(0) {}
  ~Node() { 
    std::cout << "entering " << num_ << "\n";
    delete p_next_;
    std::cout << " leaving " << num_ << "\n";
  }
  const int num_;
  Node* p_next_;
};
int Node::count = 0;
int main () {
  Node* p_head = new Node();
  p_head->p_next_ = new Node();
  p_head->p_next_->p_next_ = new Node();
  delete p_head;
  return 0;
}

And here's my take on the managing class handling destruction. Assuming I had defined the following DTOR for Node:

~Node() {std::cout << "Someone deleted " << num_ << "\n";}

I would define the following LinkedList managing class and subsequent main

/* other stuff from above */
class LinkedList {
public:
  LinkedList() : p_head_(new Node()) {
    p_head_->p_next_ = new Node();
    p_head_->p_next_->p_next_ = new Node();
  }
  ~LinkedList() {
    while(Node* p_prev = p_head_) {
      p_head_ = p_head_->p_next_;
      delete p_prev;
    }
  }
private:
  Node* p_head_;
};
int main () {
  LinkedList* p_list = new LinkedList();
  delete p_list;
  return 0;
}

Assuming I'm reading my results correctly, my two implementations do the same thing.

With respect to my recursive destruction example, I think I will almost always need some kind of managing class that holds a copy of head when I'm solving a real problem with code, but the managing class need only delete the head/root node in order to ensure destruction of the entire data structure. It feels more elegant to me, but I've gotten myself into trouble with code that I thought was neat.

Should the managing class be the one responsible for making sure everything gets deleted properly? Or is it better for the underlying data structure to know how to clean itself up? Are there any gotchas that aren't obvious?

Thanks!

--Jordan

edit: A thought occurred to me. If I have an egregiously long chain of Nodes, do I have to worry about a stack overflow during destruction in the first example since recursion is at play?

edit2: I suppose it should have been obvious. And now I just feel just a bit silly. On my machine, if I have more than 64910 nodes, I crash out. So recursion clearly presents a gotcha.

回答1:

There will be a stack memory consumption issue if you do this for linked lists. Destroying such a linked list will cause recursive d'tor of your Node, whereas the recursion depth will grow linearly with the size of your linked list.

Just do the experiment: enter several millions of nodes into your list and then destroy it. I bet you'll get the stack overflow (unless you configured your thread to reserve enormous stack size). Especially in debug build you'll run out-of-stack very early.

OTOH doing this for trees is ok, at least from technical perspective. Tree cleanup is usually implemented recursively anyway, the even fact if the above recursive function belongs to the tree or to the Node is not important.

The recursion depth of destroying the tree will grow logarithmically with the tree depth, which is ok.

回答2:

Think of ownerships of the linked item.

Does it make sense that a Node object owns it next kin? It surely makes sense that a Node owns the attached satellite data, so you should cleanup this when the Node is being destroyed.

The LinkedList owns its nodes, so it should be responsible to destroy them properly without any in-memory-leftovers.

The LinkedList object should be able to add and remove nodes, so from the ownership point of view it is responsible to cleanup them for example by removing every node in the list iteratively.