如何避免 C++ 中深层嵌套数据结构的析构函数堆栈溢出？

Question

int count;

class MyClass {
    std::shared_ptr<void> p;
public:
    MyClass(std::shared_ptr<void> f):p(f){
        ++count;
    }
    ~MyClass(){
        --count;
    }
};

void test(int n){
    std::shared_ptr<void> p;
    for(int i=0;i<n;++i){
        p = std::make_shared<MyClass>(p);
    }
    std::cout<<count<<std::endl;
}

int main(int argc, char* argv[])
{
    test(200000);
    std::cout<<count<<std::endl;
    return 0;
}

上述程序会在 Visual Studio 2010 IDE 中的“release”版本下导致堆栈溢出。

问题是：如果您确实需要创建一些像上面这样的数据结构，如何避免这个问题。

更新：现在我看到了一个有意义的答案。然而这还不够好。请考虑我已经更新了 MyClass 以包含两个（或更多）shared_ptr，并且每个都可以是 MyClass 或其他一些实例数据。

更新：有人为我更新了标题并说“深度引用计数数据结构”，这与这个问题没有必要相关。实际上，shared_ptr只是一个方便的例子；您可以轻松地更改为具有相同问题的其他数据类型。我还删除了 C++11 标签，因为它也不是 C++11 唯一的问题。

Answer 1

• 使堆栈显式化（即将其放入堆上的容器中）。
• 拥有非不透明指针（非空），以便您可以遍历您的结构。
• 取消将深度递归结构嵌套到堆容器上，使该结构成为非递归结构（通过在进行过程中断开它的连接）。
• 通过迭代上面收集的指针来释放所有内容。

像这样，改变 p 的类型，以便我们可以检查它。

std::shared_ptr<MyClass> p;

~MyClass() {
    std::stack<std::shared_ptr<MyClass>> ptrs;
    std::shared_ptr<MyClass> current = p;

    while(current) {
        ptrs.push_back(current);
        current = current->p;
        ptrs.back()->p.reset(); // does not call the dtor, since we have a copy in current
    }

    --count;
    // ptrs dtor deallocates every ptr here, and there's no recursion since the objects p member is null, and each object is destroyed by an iterative for-loop
}

最后一些提示：

• 如果您想理清任何结构，您的类型应该提供一个返回并释放所有内部shared_ptr的接口，即类似： std::vector>如果您不能将自己限制在 MyClass 中，则可能在 ISharedContainer 接口或其他内容中。
• 对于递归结构，您应该检查是否将相同的对象添加到 ptr 容器中两次。

Answer 2

感谢@Macke的提示，我有一个改进的解决方案，如下所示：

~MyClass(){
   DEFINE_THREAD_LOCAL(std::queue< std::shared<void> >, q)
   bool reentrant = !q.empty();
   q.emplace(std::move(p)); //IMPORTANT!
   if(reentrant) return;

   while(!q.empty()){
       auto pv = q.front();
       q.pop();
   }
}

DEFINE_THREAD_LOCAL是一个宏，它将变量（参数2）定义为具有线程本地存储类型的指定类型（参数1），这意味着有每个正在运行的线程不超过一个实例。由于 thread_local 关键字对于主流编译器仍然不可用，因此我必须假设这样一个宏才能使其适用于编译器。

对于单线程程序，DEFINE_THREAD_LOCAL(type, var) 很简单。

static type var;

此解决方案的好处是它不需要更改类定义。

与@Macke的解决方案不同，我使用 std::queue 而不是 std::stack 来保持销毁顺序。

在给定的测试用例中，q.size() 永远不会超过 1。然而，这只是因为该算法是广度优先的。如果 MyClass 有更多到 MyClass 另一个实例的链接，q.size() 将达到更大的值。

注意：重要的是要记住使用 std::move 将 p 传递到队列。如果你忘记这样做，你就没有解决问题，你只是创建和销毁 p 的新副本，并且在可见代码之后，销毁仍然是递归的。

更新：原始发布的代码有一个问题：q 将在 pop() 调用中进行修改。解决方案是缓存q.front()的值以供以后销毁。

Answer 3

如果您确实必须使用如此奇怪的代码，则可以增加堆栈的大小。您应该在 Visual Studio 的项目属性中找到此选项。

正如已经建议的，我必须告诉您，在处理大量数据结构时应该避免这种代码，并且如果您计划发布软件，增加堆栈大小并不是一个好的解决方案。显然，如果您滥用此功能，它也可能会严重降低您自己的计算机的速度。