18

以下代码编译并运行良好：

#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 中的垃圾收集而调用的析构函数创建了数千深的回溯。因此，我认为段错误是由于函数调用的堆栈空间不足。我有两个问题。首先，这是对段错误的正确评估吗？其次，如果是这样，是否有管理自定义数据结构的好方法，例如需要进行垃圾收集但可能非常大的树。谢谢。

4

4 回答 4

8

这通常不是问题，因为通常您会保持树平衡并且深度为 O(lg N)。

相反，你得到了一个奇怪的单链表，每个指针都有一个副本。这……很奇怪。

真正的单链表将是非常深的递归，但可能会受益于尾调用优化并且不会耗尽堆栈。

您遇到的问题对于您混合两种数据结构确实非常独特。这没有我能看到的好处。

于 2012-12-27T16:10:39.753 回答
4

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

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

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

于 2012-12-27T15:58:58.203 回答
1

这在我看来像是对std::shared_ptr. 还有一些非常糟糕的命名：你的类MyTree不是一棵树，而只是一个节点。树应该是一个单独的类，并且应该删除其析构函数中的所有节点。

话虽如此，就手头的问题而言，这不会有太大变化。您正在递归访问树上的节点（大约是唯一有意义的方式），如果您让树变得太深，堆栈将溢出，无论访问是否是隐式的（通过析构函数调用 in std::shared_ptr）或明确的。一开始就创建这样的树是没有意义的，因为在开始破坏之前创建一个您无法访问其节点的树是没有意义的。

编辑：

考虑到评论中关于垃圾收集的讨论。使用 Boehm 收集器或其他一些垃圾收集器将解决释放元素的问题。但是它仍然不允许你在释放之前访问它们，所以这样的树仍然没有用。（我认为在 C++ 中支持垃圾收集的观点非常强烈，但这不是其中之一。）

于 2012-12-27T17:10:00.477 回答
0

我认为这种类型的错误可以在没有 shared_ptr 的情况下重现。这基本上是一个长递归调用。好的，我刚刚创建并删除了一半的树但是......

struct MyTree {
    MyTree *left;
    int val;
    MyTree()
    {
      left = 0;
    }
    MyTree(MyTree *left_)
     : left(left_) {};

    ~MyTree()
    {
      delete left;
    }
};
int main() {
    MyTree *t = new MyTree();
    for(int i=0;i<100000;i++) {
      t = new MyTree(t);
    }
    delete t;
}

只需在 100000 之后再添加一个零，您就会收到相同的错误消息

于 2012-12-27T21:12:58.250 回答