Forward reservation of memory in tree-like structure

Question

How to nicely reserve memory of tree-like structure? Let's say that this would be implemented by STL vectors:

struct Leaf
{
    int val;
};

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

Now, I can reserve some memory for vector of Branches

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

But how to reserve memory for leaves at the same time (not for example during construction of Branch objects)?

Answer 1

You may consider storing the whole tree in a single array, possibly a vector. Let's say you have a structure Node:

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

vector<Node> tree;

Then the tree[0] is the root of the tree. Each time you want to add a new branch in certain node, let's say tree[i], you do:

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;

Then you can traverse the tree easily by starting from any node (including the root) and looking through its children.

Here is an example of traversing the tree using 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);

This way you can reserve memory for the tree:

tree.reserve(100);