Stack overflow with unique_ptr linked list [closed]

Question

I've converted the following linked list struct

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

into a c++11 version - that is not using the pointers.

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

Adding, removing elements and traversing works fine, however when I insert roughly 1mil elements, I get a stack overflow when when the destructor of the head node is called.

I'm not sure what I'm doing wrong.

{
  node n;

  ... add 10mill elements

} <-- crash here

Answer 1

You are making nothing wrong here.

When you create your list of 10 millions elements, allocation each node with make_unique everything is fine (Of course the data is not on the stack, except perhaps the first node !).

The problem is when you you get rid of the head of your list: unique_ptr will take care of the deleting the next node that it owns, which also contains a unique_ptr that will take care of deleting the next node... etc...

So that in the end the 10 millions elements get deleted recursively, each recursive call taking some space on the stack.

Answer 2

As explained in the other answers, you segfault because of the recursive implicit destructor. It is possible to fix this without resorting to raw pointers, having to trust the compiler or writing a custom allocator:

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

Here you iteratively go through the chain of pointers. This will, one at a time, unchain one pointer and change ownership std::move(current->next) to current. At the same time the previous unchained pointer, owned by current, will be released while being overwritten by the move assignment.

You may find the explicit variant more straightforward:

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

Is effectively the same as:

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

I prefer the move version, because it does at no time leave you with a raw pointer. But in that case it does not make a difference.