title: Nested shared_ptr destruction causes stack overflow
body: <p>This is a more of design problem (I know why this is happening, just want to see how people deal with it). Suppose I have a simple linked list <code>struct</code>:</p>
  
  <pre><code>struct List {
      int head;
      std::shared_ptr&lt;List&gt; tail;
  };
  </code></pre>
  
  <p>The <code>shared_ptr</code> enables sharing of sublists between multiple lists. However, when the list gets very long, a stack overflow might happen in its destructor (caused by recursive releases of <code>shared_ptr</code>s). I've tried using an explicit stack, but that gets very tricky since a tail can be owned by multiple lists. How can I design my <code>List</code> to avoid this problem?</p>
  
  <p><strong>UPDATE:</strong> To clarify, I'm not reinventing the wheel (<code>std::forward_list</code>). The <code>List</code> above is only a simplified version of the real data structure. The real data structure is a directed acyclic graph, which if you think about it is just a lot of of linked lists with shared tails/heads. It's usually prohibitively expensive to copy the graph, so data sharing is necessary.</p>
  
  <p><strong>UPDATE 2:</strong> I'm thinking about explicitly traversing down the pointer chain and <code>std::move</code> as I go. Something like:</p>
  
  <pre><code>~List()
  {
      auto p = std::move(tail);
      while (p-&gt;tail != nullptr &amp;&amp; p-&gt;tail.use_count() == 1) {
          // Some other thread may start pointing to `p-&gt;tail`
          // and increases its use count before the next line
          p = std::move(p-&gt;tail);
      }
  }
  </code></pre>
  
  <p>This seems to work in a single thread, but I'm worried about thread safety.</p>