c++ - 堆分配与 std::vector

Question

我需要在代码的关键部分创建一棵多树。标准方法是使用类似的东西:

struct node{ // or class
   ... data ...
  std::unordered_set<node*> children
};

node* root;

一个重要的事情是，一旦创建了一个节点，on 就不会被删除，直到整个树被删除为止。

显而易见的方法是使用new和delete语句来管理堆上的这些数据。完成。

我想知道是否值得探索使用 std::vector 而不是直接使用 new/delete 的性能:

struct node{ // or class
   ... data ...
  std::unordered_set<uint_32> children
};

std::vector<node> tree;
uint_32 root; // probably always 0, fist element of vector

删除树只需使用tree.clear();

对于大(或巨大)树来说，它是否有可能更快？

Answer 1

我猜您有一棵大约有 1000 万多个元素大小的树(或者至少有 10 万多个元素左右)来关心这个问题。

这完全取决于您的数据和树的使用方式。数据的空间性通常令人担忧，但如果您也是这种情况，则它并不明显。如果树在构建后被遍历了很多次(在某种程度上与被修改了很多相反)并且只被修改了一点点，那么尝试组织数据以使其连续迭代是有意义的(作为 std::vector 通常是)。在这种情况下，您不想要拥有这样的指针，或者更确切地说，您不想要使用单个元素new/delete 当然，因为这几乎肯定会让您感到困扰(因为您不能指望元素在内存中连续放置) - 但这一切都取决于您的用例。

一个简单的方法和完全不同的方法是:

std::vector< std::pair<PathInTree, Node> > tree;

然后对其进行排序，使节点按照您迭代树的顺序出现。这是一个有点极端的解决方案，并且有一些缺点，包括如果发生大量随机插入，插入现在可能会变得昂贵。我还遗漏了如何在树中实现 Path，但它通常应该是某种序列(例如在文件系统结构中)。