std :: unique_ptr <>作为基于节点的结构中的指针

Question

由于大多数人都喜欢谜题,我会用一个(拼写错误:)开始这个问题.想得到介绍,请注意,如果你不关心它,你可以跳过热身(JG问题)并阅读G问题,因为那是我的"真正的问题".

在审查潜在新员工提供的代码示例时,您偶然发现了一个链接列表,其实现使用了现代C++ 11特性,即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问题:

使用此代码确定(忽略缺少的功能)问题.

G问题:( 根据答案添加2.)
1.

有没有办法在不使用原始指针的情况下修复问题的JG部分中检测到的问题？

2.

该修复是否适用于节点包含多个指针的容器(例如,二叉树具有指向左右子节点的指针)

答案:
JG:

堆栈溢出 :).原因:由.clear()函数触发的unique_ptr <>析构函数的递归.

G:

(???)我不知道,我的直觉不是,但我想和专家核实一下.

长话短说:有没有办法在基于节点的结构中使用智能指针而不是最终出现SO问题？请不要说树木可能不会太深,或类似的东西,我正在寻找一般的解决方案.

Answer 1

您可以迭代清除它,确保next在销毁节点之前每个节点的指针都是空的:

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

二叉树比较棘手; 但是你可以通过迭代地切断右边的分支并将它们添加到左下角来将其展平成一个列表,如下所示:

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);
}