在破坏期间使用std :: shared_ptr的Segfault可能是由于堆栈上的函数调用太多

Question

以下代码编译并运行正常:

#include <memory>
struct MyTree {
    std::shared_ptr <MyTree> left;
    std::shared_ptr <MyTree> right;
    int val;
    MyTree(
        std::shared_ptr <MyTree> left_,
        std::shared_ptr <MyTree> right_,
        int val_
    ) : left(left_), right(right_), val(val_) {};
};
int main() {
    std::shared_ptr <MyTree> t(
        new MyTree( std::shared_ptr <MyTree>(),
                    std::shared_ptr <MyTree>(),
                    0)
    );  
    for(int i=0;i<10000;i++) {
        t.reset(new MyTree(t,t,0));
    }
}

但是,当for循环从10000更改为100000时,我收到段错误.查看gdb中的结果,看起来像std :: shared_ptr中的垃圾收集调用的析构函数会创建一个数千深的回溯.因此,我认为段错是由于函数调用从堆栈中耗尽.我有两个问题.首先,这是对segfault的正确评估吗？其次,如果是这样,是否有一种很好的方法来管理自定义数据结构,例如需要进行垃圾回收的树,但可能非常大.谢谢.

Answer 1

这通常不是问题,因为通常你保持树平衡,深度为O(lg N).

相反,你得到了一个奇怪的单链表,每个指针都有一个副本.那是......奇怪的.

一个真正的单链表将是非常深的递归,但可能会受益于尾调用优化而不会耗尽堆栈.

您遇到的问题对于混合两种数据结构而言非常独特.哪个没有我能看到的好处.

Answer 2

你的评估对我来说完全正确。看起来删除子子树的递归调用超出了 yoru 堆栈大小。但这与shared_ptr我期望数据结构上的任何递归算法也会以同样的方式失败无关。

如果在您的平台上可能的话，处理此类大型结构的需求的最简单方法就是简单地增加堆栈的大小（例如ulimit）以允许自然递归算法发挥作用。

如果这是不可能的，您将不得不自己遍历节点，将遍历结果存储到某种容器中，这样您就可以砍掉子节点，而不需要对树结构进行完全深度遍历。