C ++ smart_ptr not causing stack overflow?

Question

I participate in C ++ SWE training and build a simple LinkedList class using std :: unique_ptr as references to head and next . This is the basic structure:

 template <class T> struct LinkedListNode { T value; std::unique_ptr<LinkedListNode<T>> next; // For debugging. ~LinkedListNode() { std::cout << "destructed for value " << this->value << std::endl; } }; template <class T> struct LinkedList { std::unique_ptr<LinkedListNode<T>> head; }; 

Using smart pointers, I expect that when a LinkedList instance is deleted or out of scope, then the head will be deleted, and each next node will also be deleted recursively.

And this is exactly what is happening. However, when working with really long lists (~ 20M nodes), this surprisingly still works fine. Shouldn't it crash due?

To very roughly estimate the size of my OS stack, I wrote the following script:

 int main() { struct s { static void p(int i) { std::cout << i << std::endl; p(i+1); }; s::p(0); } 

And it crashed on iteration number ~ 175K, much smaller than the 20M nodes that I could free earlier. What's happening? Am I missing something about how unique_ptr works?

Answer 1

In your example, you really have recursion, the real reason why it does not reach is because the tail call recursion , which can be optimized for an iterative solution.

With this piece of code:

 struct Node { int value; std::unique_ptr<Node> next; Node(int value, Node* next) : value(value), next(next) { } ~Node() { if (value == 0) cout << "foo" << endl; } }; int main() { Node* node = new Node(0, nullptr); for (int i = 1; i <= 5; ++i) node = new Node(i, node); delete node; return 0; } 

By placing a breakpoint in the cout statement and checking the stack trace, you can clearly see that the behavior is recursive:

The behavior is also shown here , using the base destructor for tracking when returning ~Node() .

Since the next node must be destroyed before returning from the destructor, which leads to the repeated call of ~Node() . This behavior would be the same, using the source pointers and deleting the next pointer directly in the destructor that was already answered here .