使用链表堆叠溢出unique_ptr

Question

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

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

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

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

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

我

不确定我做错了什么。

{
  node n;
  ... add 10mill elements
} <-- crash here

Answer 1

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

~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版本，因为它永远不会给你留下原始指针。但在这种情况下，它没有区别。

Answer 2

你在这里没有做错任何事。

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

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

因此，最终 1000 万个元素被递归删除，每个递归调用都会占用堆栈上的一些空间。

Answer 3

默认情况下

，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 4

因为当您销毁头节点元素时，它会调用析构函数 oа unique_ptr，这会破坏调用调用第三个元素的析构函数的第二个元素，该元素调用...ETС 1mil 倍。

因此，您有 1 mil 嵌套函数调用（析构函数）。每个函数调用至少占用堆栈中的内存来存储返回地址（如果需要，还可以使用参数和局部变量）。当然，堆栈无法提供如此多的内存。您应该重新编写代码来解决此问题。例如，重写 Node 类的析构函数，以便它找到最后一个列表元素，然后在 cicle 中销毁它和所有其他节点，而不是递归。