unique_ptr 链表的堆栈溢出

Question

我已经转换了以下链表结构

struct node {
  node* next;
  int v;
};

进入 c++11 版本 - 即不使用指针。

struct node {
  unique_ptr<node> next;
  int v;
};

添加、删除元素和遍历工作正常，但是当我插入大约 100 万个元素时，调用头节点的析构函数时出现堆栈溢出。

我不确定我做错了什么。

{
  node n;

  ... add 10mill elements

} <-- crash here

Answer 1

你没有做错任何事。

当您创建包含 1000 万个元素的列表时，为每个节点分配 make_unique 一切都很好（当然数据不在堆栈上，除了第一个节点！）。

问题是当你去掉列表的头部时：unique_ptr 将负责删除它拥有的下一个节点，其中还包含一个 unique_ptr注意删除下一个节点...等等...

所以最后 1000 万个元素被递归删除，每个递归调用在堆栈上占用一些 space。

Answer 2

默认情况下 std::unique_ptr 调用结构 std::default_delete 的运算符函数，它只执行运算符 delete.

因此结构 std::default_delete 的每个运算符函数递归地调用自身以获取结构 node.

的数据成员 next

结果导致堆栈溢出。

如果您使用普通指针而不是 std::unique_ptr 类型的指针，但通过以下方式向结构节点添加析构函数，您将得到相同的结果

struct node {
  node* next;
  int v;
  ~node() { delete next; } 
};

甚至喜欢

struct node {
  node* next;
  int v;
  ~node() { if ( next ) delete next; } 
};

对于节点数较多的列表，因为析构函数会被递归调用

Answer 3

因为当您销毁头节点元素时，它会调用析构函数 ounique_ptr，它会销毁调用第三个元素的析构函数的第二个元素，而第三个元素调用 ... 等 100 万次。

因此，您有 100 万次嵌套函数调用（析构函数）。每个函数调用至少在堆栈中占用内存以存储 return 地址（如果需要，还包括参数和局部变量）。自然，stack 无法提供这样的内存量。你应该重新设计代码来解决它。例如，重写 Node class 的析构函数，使其找到最后一个列表元素，然后销毁它和循环中末尾的所有其他节点，而不是递归地销毁。

Answer 4

如其他答案中所述，您由于递归隐式析构函数而出现段错误。可以在不诉诸原始指针的情况下解决这个问题，必须信任编译器或编写自定义分配器：

~node() {
    for (std::unique_ptr<node> current = std::move(next);
         current;
         current = std::move(current->next));
}

在这里，您迭代地遍历指针链。这将一次一个地解开一个指针并将所有权 std::move(current->next) 更改为当前。同时，current 拥有的先前未链接的指针将在被移动赋值覆盖时被释放。

您可能会发现显式变体更直接：

current.reset(current->next.release()));

实际上等同于：

current = std::move(current->next));

我更喜欢 move 版本，因为它不会给您留下原始指针。但在那种情况下它没有什么区别。

unique_ptr 链表的堆栈溢出

Stack overflow with unique_ptr linked list

c++

stack-overflow

linked-list

unique-ptr

c++11