链表,树等的递归析构函数是不是很糟糕？

Question

对于我目前的学习练习,我正在研究链表和树木.我最近看到一个建议是通过让每个节点删除其子/子来递归地销毁数据结构.然而,在我发现的几乎所有示例中,节点析构函数都是空的,而某些管理类使用某种形式的迭代和删除来处理破坏.从可靠性和/或风格的角度来看,递归析构函数有什么本质上的坏处吗？

以下是我对这两种方法的理解的实现.

递归破坏:

#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;
}

这是我对处理破坏的管理类的看法.假设我为Node定义了以下DTOR:

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

我将定义以下LinkedList管理类和后续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;
}

假设我正确地读取了我的结果,我的两个实现做了同样的事情.

关于我的递归破坏示例,我想我几乎总是需要某种管理类,当我用代码解决一个真正的问题时,它会持有头部的副本,但是管理类只需要删除头部/根节点为了确保破坏整个数据结构.对我来说感觉更优雅,但我已经陷入了我认为整洁的代码的麻烦.

管理类是否应该负责确保所有内容都被正确删除？或者,底层数据结构更好地了解如何清理自己？有没有明显的陷阱？

谢谢!

- 约旦

编辑:我想到了一个念头.如果我有一个非常长的节点链,我是否必须担心在第一个例子中的破坏期间堆栈溢出,因为递归正在发挥作用？

edit2:我想应该是显而易见的.而现在我觉得有点傻.在我的机器上,如果我有超过64910个节点,我就崩溃了.所以递归显然是一个问题.

Answer 1

如果对链接列表执行此操作,则会出现堆栈内存消耗问题.销毁这样的链表将导致你Node的递归,而递归深度将随链表的大小线性增长.

只需进行实验:在列表中输入数百万个节点,然后将其销毁.我打赌你会得到堆栈溢出(除非你配置你的线程来保留巨大的堆栈大小).特别是在调试版本中,你很早就会用完堆栈.

至少从技术角度来看,OTOH为树木做这件事是可以的.树清理通常是递归地实现的,如果上面的递归函数属于树或者Node不重要,则事实就是如此.

破坏树的递归深度将与树深度呈对数增长,这是可以的.