是一个递归析构函数的链表，树等等？ [英] Is a recursive destructor for linked list, tree, etc. bad?
问题描述
对于我目前的学习，我正在学习链表和树。我最近看到一个建议，通过让每个节点删除其子/子，递归地销毁数据结构。然而在几乎所有的例子中，我发现，节点析构函数是空的，一些管理类使用某种形式的迭代和删除处理销毁。从可靠性和/或风格的角度来看，递归析构函数有什么本质上的坏处吗？
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.
递归销毁：
#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：
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";}
我将定义以下LinkedList管理类和后续主
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?
谢谢！
- Jordan
--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：我想它应该是显而易见的。现在我只是觉得有点傻。在我的机器上，如果我有超过64910个节点，我崩溃了。
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.
推荐答案
如果你这样做的话，会有堆栈内存消耗的问题。销毁这样的链表会导致你的 Node 递归，而递归深度会随着链表大小线性增长。
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.
只要做实验：在你的列表中输入几百万个节点，然后销毁它。我敢打赌你会得到堆栈溢出（除非你配置你的线程保留巨大的堆栈大小）。特别是在调试版本中，你很早就会运行out-of-stack。
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这样做对于树是可以的，至少从技术角度来看。树清除通常以递归方式实现，即使上述递归函数属于树或 Node 也不重要。
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.
这篇关于是一个递归析构函数的链表，树等等？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
