Geek asks and answers

Direct memory backup in a tree structure

How nice to reserve the memory of the tree structure? Let's say that this will be implemented by STL vectors:

struct Leaf
{
    int val;
};

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

Now I can reserve some memory for the vector Branches

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

But how to reserve memory for leavesat the same time (not for example when building objects Branch)?

+3
source share
3 answers

You might consider saving the whole tree in one array, possibly in a vector. Let's say you have a structure Node:

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

vector<Node> tree;

Then tree[0]is the root of the tree. Every time you want to add a new branch to a specific 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;

, node ( ) .

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 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);
+2

Leaf (, , ). pop Leaf Branch ( Leaf ...). , : std::vector<Leaf> std::vector<Leaf*>.

, Leaf s.

+1

, Branch es? std::vector, .

My suggestion was to actually build a vector filled with (empty) Branches, but at the same time reserve space for its Leafs, for example:

if you write a memory reservation constructor for the Branch / struct class:

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

then you can do:

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

or

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

Not quite what you ask for, but maybe it helps.

+1
source

More articles:


All Articles