c++ - std::unique_ptr<> as pointer in a node based structure

Question

Since most of the ppl like puzzles I,ll start this question with a (bad spelling :))gotw like introduction, note that if you dont care about it you can skip the warmup(JG question) and read the G question since that is my "real SO question".

During review of the code samples provided by potential new employees you stumbled upon a linked list whose implementation uses modern C++11 feature, an std::unique_ptr<>.

template <typename T> 
struct Node { 
   T data; 
   std::unique_ptr<Node<T>> next; 
   Node () {} 
   Node(const T& data_): data(data_) {} 
   Node(Node& other) { std::static_assert(false,"OH NOES"); } 
   Node& operator= (const Node& other) { 
     std::static_assert(false,"OH NOES"); 
     return *new Node(); 
   } 
public: 
   void addNext(const T& t) { 
      next.reset(new Node<T>(t)); 
   }
};

template<typename T>
class FwdList
{
    std::unique_ptr<Node<T>> head;
public:
    void add(const T& t)
    {
        if (head == nullptr)
            head.reset( new Node<T>(t));
        else {
            Node<T>* curr_node = head.get();
            while (curr_node->next!=nullptr) {
                curr_node = curr_node->next.get();
            }
            curr_node->addNext(t);
        }
    }
    void clear() {
        head.reset(); 
    }
 };

JG question:

Determine(ignoring the missing functionality) problem(s) with this code.

G question: (added 2. based on answers)
1.

Is there a way to fix the problem(s) detected in JG part of the question without the use of raw pointers?

2.

Does the fix work for the containers where node contain more than one pointer(for example binary tree has pointers to left and right child)

Answers:
JG :

stackoverflow :). Reason:recursion of the unique_ptr<> destructors triggered by .clear() function.

G:

(???) I have no idea, my gut feeling is no, but I would like to check with the experts.

So long story short: is there a way to use smart pointers in node based structures and not end up with SO problems? Please don't say that trees probably wont get too deep, or something like that, im looking for general solution.

Answer 1

You can clear it iteratively, making sure that each node's next pointer is empty before destroying the node:

while (head) {
    head = std::move(head->next);
}

A binary tree is trickier; but you can flatten it into a list by iteratively cutting off right-hand branches and adding them to the bottom left, something like this:

node * find_bottom_left(node * head) {
    while (head && head->left) {
        head = head->left.get();
    }
    return head;
}

node * bottom = find_bottom_left(head.get());

while (head) {
    bottom->left = std::move(head->right);
    bottom = find_bottom_left(bottom);
    head = std::move(head->left);
}