3

ツリーのような構造のメモリを適切に予約するには? これが STL ベクトルによって実装されるとしましょう:

struct Leaf
{
    int val;
};

struct Branch
{
    std::vector<Leaf> leaves;
};

Branchこれで、 esのベクトル用にいくらかのメモリを予約できます

std::vector<Branch> branches;
branches.reserve(10);

しかしleaves、同時にメモリを予約する方法はありますか (たとえば、Branchオブジェクトの構築中ではありません)。

4

3 に答える 3

2

ツリー全体を単一の配列、場合によってはベクトルに格納することを検討してください。あなたが構造を持っているとしましょうNode：

struct Node
{
    int val;
    vector<size_t> children;
};

vector<Node> tree;

次に、tree[0]はツリーのルートです。特定のノードに新しいブランチを追加するたびに、たとえば、次のtree[i]ようにします。

tree.resize(tree.size()+1);
tree[i].children.push_back(tree.size()-1);
// you can also set the value of the new node:
tree.back().val = 123;

次に、任意のノード（ルートを含む）から開始してその子を調べることにより、ツリーを簡単にトラバースできます。

DFSを使用してツリーをトラバースする例を次に示します。

void dfs(size_t x)
{
    // you can do sth here, for example:
    printf("node: %d, number of children: %d\n", x, tree[x].children.size());

    // go deeper in the tree to the node's children:
    for (size_t i=0; i<tree[x].children.size(); ++i)
        dfs(tree[x].children[i]);
}

// starting DFS from the root:
dfs(0);

このようにして、ツリーのメモリを予約できます。

tree.reserve(100);
于 2012-05-10T09:57:42.607 に答える
1

Leafツリー全体を (またはツリーの一部として) 初期化する前に、事前に初期化された空の s へのポインターのスタックをいくつか作成します。その後、pop Leafスタックからそれを特定のものにアタッチすることができますBranch（そして、 s を目的の値で埋めLeafます...）。もちろん、次のように変更する必要がありstd::vector<Leaf>ますstd::vector<Leaf*>。

スタックが空になると、空Leafの s の別のセットを作成します。

于 2012-05-10T09:46:58.363 に答える
1

Branches用に予約しようとすると、どのくらいのメモリを予約しますか? それぞれに が含まれているstd::vectorため、サイズは可変です。

私の提案は、(空の) es で満たされたベクトルを実際に構築することですBranchが、同時に、次のように s用のスペースを確保することです。Leaf

Branch クラス/構造体のメモリ予約コンストラクタを記述する場合:

struct Branch{
    std::vector <Leaf> leaves;
    Branch (int expectedL = 10){
        leaves.reserve(expectedL);
    }
};

次に、次のことができます。

std::vector<Branch> branches(10);

また

std::vector<Branch> branches(10, 42);

あなたが求めているものとは正確には異なりますが、おそらく役立つでしょう。

于 2012-05-10T09:47:46.377 に答える