C++ smart_ptr 不会导致堆栈溢出？

Question

我是一名学习 C++ 的 SWE，并使用 std::unique_ptr 作为对 head 和 next 的引用构建了一个简单的 LinkedList 类。这是基本结构:

template <class T>
struct LinkedListNode {
    T value;
    std::unique_ptr<LinkedListNode<T>> next;

    // For debugging.
    ~LinkedListNode() {
        std::cout << "destructed for value " << this->value << std::endl;
    }
};

template <class T>
struct LinkedList {
    std::unique_ptr<LinkedListNode<T>> head;
};

使用智能指针，我希望当 LinkedList 实例被删除或超出范围时，head 将被删除，并且每个 next 节点将被递归删除也是。

而这正是发生的事情。然而，当处理非常长的列表(~20M 节点)时，令人惊讶的是它仍然可以正常工作。它不应该因为堆栈溢出而崩溃吗？

为了非常粗略地估计我的操作系统堆栈的大小，我编写了以下脚本:

int main() {
    struct s {
        static void p(int i) {
        std::cout << i << std::endl;
        p(i+1);
    };
    s::p(0);
}

它在迭代次数 ~175K 时崩溃，比我之前能够解除分配的 20M 节点少得多。到底是怎么回事？我是否遗漏了 unique_ptr 的工作方式？

Answer 1

在你的例子中你确实有递归，它没有达到堆栈溢出的真正原因可能是因为它是一个 tail-call recursion可以优化为迭代解决方案。

使用这段代码:

struct Node
{
  int value;
  std::unique_ptr<Node> next;

  Node(int value, Node* next) : value(value), next(next) { }

  ~Node()
  {
    if (value == 0)
      cout << "foo" << endl;
  }
};

int main()
{
  Node* node = new Node(0, nullptr);
  for (int i = 1; i <= 5; ++i)
    node = new Node(i, node);

  delete node;

  return 0;
}

通过在 cout 语句上放置一个断点并检查堆栈跟踪，您可以清楚地看到该行为是递归的:

还显示了行为 here通过使用基本析构函数来跟踪 ~Node() 何时返回。

由于 next 节点必须在从析构函数返回之前被销毁，这导致再次调用 ~Node()。通过使用原始指针并直接在析构函数中删除下一个指针，此行为将是相同的，这确实已经得到回答here .