C++ smart_ptr doesn't cause stack overflow?

Question

I am a SWE learning C++, and building 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 gets deleted or goes out of scope, then head will be deleted, and each next node will be deleted recursively too.

And this is exactly what happens. However, when working with really long lists (~20M nodes), it surprisingly still works OK. Shouldn't it crash because of a stack overflow?

In order to very roughly estimate the size of my OS's 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 at iteration number ~175K, much less than the 20M nodes that I was able to deallocate before. What is going on? Am I missing something about the way unique_ptr works?

Answer 1

In your example you have indeed recursion, the real reason behind it not reaching stack overflow could be because it's a tail-call recursion which could be optimized to an iterative solution.

With this snippet 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 on the cout statement and inspecting the stack trace you clearly see that behavior is recursive:

The behavior is shown also here by using a base destructor to track when ~Node() returns.

Since the next node must be destroyed before returning from the destructor, which leads to invoking ~Node() again. This behaviour would be the same by using raw pointers and deleting next pointer directly in the destructor, which indeed has already been answered here.