Stack overflow with unique_ptr linked list [closed

问题:

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

回答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.

回答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.

回答3:

By default std::unique_ptr calls the operator function of structure std::default_delete that just executes operator delete.

So each operator function of the structure std::default_delete recursively calls itself for data member next of structure node.

As result you get the stack overflow.

You would get the same result if you used ordinary pointers instead of the pointers of type std::unique_ptr but added a destructor to the structure node the following way

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

Or even like

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

for a list with a big number of nodes because the destructor will be called recursively

回答4:

Because when you destroy the head node element, it calls destructor oа unique_ptr, which destroys the second element that calls destructor of the 3rd element which calls ... etс 1mil times.

So, you have 1 mil nested funtion calls (of destructors). Each function call takes memory in stack at least to store return address (and parameters and local variables as well, if needed). Naturally, stack can not provide such amount of memory. You should redesing code to resolve it. For instance, rewrite destructor of Node class so that it finds the last list element and then destroys it and all other nodes from the end in a cicle, not recursievely.