5

ppl のようなパズルのほとんどは、この質問を (スペルが間違っています :))gotw のような紹介から始めます。気にしない場合は、ウォームアップ (JG の質問) をスキップして、G の質問を読むことができます。私の「本当のSOの質問」。

潜在的な新入社員から提供されたコード サンプルを確認しているときに、最新の 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 に答える