堆栈溢出与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将负责删除下一个节点......等等...

因此,最终以递归方式删除了10百万个元素,每个递归调用占用了堆栈上的一些空间.

是的，有一种方法：当您创建 unique_ptr 时，您可以提供一个将被调用的自定义删除器，而不是默认的删除器。因此，您可以提供一种使删除迭代而不是递归的方法。 (2认同)
@DavidSchwartz你当然是对的：用一个自定义的删除器替换默认的删除器，该自定义的删除器会迭代列表以重置指针，这需要一点 unique_ptr 的好处，并且看起来非常接近您编写的代码unique_ptr。剩下的主要优势是明确节点的所有权。我认为OP的问题是教育/实验目的，因为在现实世界中我们都会使用`<list>` (2认同)
atZereges：我用 gcc 和 clang 尝试了 O2。clang 现在没有崩溃，但 gcc 仍然崩溃。gcc 是 4.9 clang 是 3.5 (2认同)

Answer 3

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

因此结构的每个运算符函数std::default_delete递归地next为结构的数据成员调用自身node.

结果你得到堆栈溢出.

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

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

甚至喜欢

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

对于具有大量节点的列表,因为将以递归方式调用析构函数