木のような構造のメモリの前方予約

Question

木のような構造のメモリをうまく予約するには？のは、これはSTLベクトルによって実装されるだろうと言ってみましょう：

struct Leaf 
{ 
    int val; 
}; 

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

今、私はBranch ES

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

のベクトルのためのいくつかのメモリを予約することができます。しかし、同時にleavesのためのメモリを確保する方法（ありません例えば、Branchオブジェクトの構築中）？

Answer 1

事前に初期化された空のポインタをいくつか作成して、ツリー全体（またはツリーの一部として）を初期化する前に空のLeafを作成します。その後、popLeafをスタックから取り出し、それを特定のBranchに添付することができます（そして、Leafを希望の値で埋める...）。もちろん、変更する必要があります：std::vector<Leaf>〜std::vector<Leaf*>。

スタックが空の場合は、空のLeafの別のセットを作成します。

Answer 2

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

私の提案は、実際には（空）Branch ESで満たされたベクターを構築することですが、同時に準備このような彼らのLeafのためのスペースは、：

あなたはコンストラクタを予約するメモリを書く場合支店クラス/構造体のために：

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

は、あなたが行うことができます。

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

または

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

あなたが求めているのは正確ではありませんが、おそらくそれが役に立ちます。

Answer 3

ツリー全体を単一の配列（おそらくベクトル）に格納することを検討することもできます。あなたが構造Nodeを持っているとしましょう：

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

vector<Node> tree; 

その後tree[0]は、ツリーのルートです。

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; 

その後、あなたは（ルートを含む）の任意のノードから始まり、その子を見ることにより、簡単にツリーをトラバースすることができます：あなたは、特定のノードに新しいブランチを追加するたびに、あなたはない、のは、tree[i]を言わせて。ここで

は、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);