std :: unique_ptr<>作为基于节点的结构中的指针 [英] std::unique_ptr<> as pointer in a node based structure

问题描述

由于大多数ppl像拼图我，我开始这个问题与一个（坏拼写:)）得到的介绍，注意，如果你不关心它，你可以跳过热身问题），并阅读G问题，因为那是我的真正的SO问题。

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".

在审查潜在新员工
提供的代码示例时，您偶然发现了一个链接列表，其实现使用现代C ++ 11
功能，std :: unique_ptr<>。

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问题：

使用
代码确定（忽略缺少的功能）问题。

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

G问题（根据回答添加2.

1。

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

有没有办法解决在
问题的JG部分中检测到的问题，而不使用原始指针？

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)

回答：

JG：

Answers:
JG :

stackoverflow :)。原因：递归由.clear（）函数触发的unique_ptr<>析构函数
。

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

G：

（???）我不知道，我的直觉是没有，但我想和
专家检查。 p>

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

这么长的故事短：有没有办法在基于节点的结构中使用智能指针，而不是SO的问题？请不要说树木可能不会太深，或类似的东西，寻找一般的解决方案。

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.

推荐答案

您可以迭代地清除它，确保每个节点 next 指针在销毁节点之前为空：

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

这篇关于std :: unique_ptr&lt;&gt;作为基于节点的结构中的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！