5

由于大多数人都喜欢谜题，我会以（拼写错误 :)）gotw 之类的介绍开始这个问题，请注意，如果您不关心它，您可以跳过热身（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 问题？请不要说树可能不会太深，或者类似的东西，我正在寻找一般的解决方案。

4

1 回答 1

8

您可以迭代清除它，确保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);
}
于 2012-08-28T23:23:55.223 回答