1

を使用してツリー データ構造を再実装しようとしていstd::unique_ptrますが、その考えは、親ノードが のベクトルに格納されている子を所有するというものですunique_ptr。

インターフェイス上の理由から、ノードがそれ自体を破棄するメソッドが必要です。この場合、ノードは親の子ベクトルから自分自身を消去すると思います。

次の実装は (c++11 コンパイラで) 「動作」しますが、非常に見苦しく、この問題を処理する最適な方法ではないと確信しています。

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

struct Node {
    typedef std::vector<std::unique_ptr<Node>> vec_node_uptr;

    unsigned        id;
    Node*           parent;
    vec_node_uptr   child_nodes;

    // ctor
    Node(unsigned id): id(id){ parent = nullptr; }

    void add_child(Node* new_child){
        new_child -> parent = this;
        child_nodes.push_back( std::unique_ptr<Node>(std::move(new_child) ) );
    }

    int where_am_i(){
        int result_ = 0;
        for(auto& i: this -> parent -> child_nodes) {
            if (this == i.get()) {
                return result_;
            } else {
                result_++;
            }
        }
    }

    void suicide(){
        parent -> child_nodes.erase(parent -> child_nodes.begin()+ where_am_i());
    }
};


int main()
{
    std::unique_ptr<Node> root(new Node(0));

    root -> add_child(new Node(1));
    root -> add_child(new Node(2));

    root -> child_nodes[0] -> add_child(new Node(3));
    root -> child_nodes[0] -> add_child(new Node(4));
    root -> child_nodes[1] -> add_child(new Node(5));
    root -> child_nodes[1] -> add_child(new Node(6));

    root -> child_nodes[1] -> suicide();

    return 0;
}

助言がありますか？たぶん使用std::find？

4

2 に答える 2

1

これは、find_if とラムダを使用して、もう少しエレガントに解決できます。

void suicide() 
{
    auto& parentsChildren = parent->child_nodes;
    parentsChildren.erase(find_if(begin(parentsChildren), end(parentsChildren), 
                           [&](const unique_ptr<Node>& node) { return node.get() == this; }));
}
于 2013-06-07T13:10:51.540 に答える
1

現在のデータ構造で一定の時間where_am_i()が必要な場合は、ノード自体にインデックスまたは反復子を格納する必要があります。これは (a) 重複であり、(b) 親の最後の子ではないノードを削除するたびに、後続のすべての子のインデックス/イテレータを更新する必要があるため、さらに複雑になります...

where_am_i()繰り返しになりますが、ベクトルから要素を削除することはとにかく O(n) であるため、常に最後 (または最後近く) から削除する場合を除いて、constant-time を作成することに実際の利点はない可能性があります。

ただし、通常は最後から削除する場合、および一連の子の所有権を親ノードから譲渡する必要がない場合は、それぞれにインデックスまたはイテレータを格納する必要を回避する、代替のより単純な設計を次に示します。ノード：

std::vectorC++ 標準では、配列と同様に、その内容がメモリ内に連続して配置されることが保証されています。したがって、child_nodesベクトルが実際にその要素を値で格納した場合、つまり、次のように宣言された場合

typedef std::vector<Node> vec_node_uptr;
vec_node_uptr child_nodes;

次に、指定された要素のアドレスからベクトルの最初の要素のアドレスを減算するだけで、定数時間で位置を見つけることができます。ポインター演算で除算を行うことができます。

size_t where_am_i() {
    return this - &parent->child_nodes[0];
}
于 2013-06-07T13:10:56.567 に答える