c++ - 树状结构中的内存前向预留

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

您可以考虑将整个树存储在一个数组中，可能是一个向量。假设你有一个结构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);

Answer 2

Leaf在初始化整个树（或者可能作为树的一部分）之前，制作一些指向预初始化空的指针堆栈。之后，您可以pop Leaf从堆栈中将其附加到特定的（并用所需的值Branch填充s ......）。Leaf当然，那你应该改变：std::vector<Leaf>到std::vector<Leaf*>.

当 stack 为空时，创建另一组空Leafs。

Answer 3

Branch当您尝试为es保留它时，您到底保留了多少内存？它们中的每一个都包含一个std::vector，因此它的大小是可变的。

我的建议是实际构造一个用 (empty) Branches 填充的向量，但同时为它们的 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);

不完全是您要问的，但也许有帮助。