堆分配与 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

考虑到 std::unordered_set<uint_32> 的每个实例仍然会在堆上（内部）产生至少一次分配，实际可实现的节省有一个硬性界限。您将节省不到 50% 的必要堆分配。

One important thing is that, once a node is created, it won't be deleted until the whole tree will be deleted.

Re-allocations 仍在 std::vector 中发生。与堆上的不可移动分配相比，这还涉及移动已经分配的节点。根据您的 node 元素具有的其他属性，这可能会更加昂贵。您还需要确保您的 node class 与移动语义兼容。

由于 std::unordered_set 也在堆上分配，您也无法避免由此产生的内存碎片。

总而言之，除非您希望受到堆分配性能的限制，或者您有 order-independent 树遍历的用例，否则压缩 node 实例可能不会值得努力。

一个可能合理的优化是将 std::unordered_set<node*> 换成 std::unordered_set<node>。除非您需要在那个地方进行间接访问（外部指针？），否则这会节省您与您自己的尝试一样多的时间，而不会牺牲调试功能。

为 node 实现必要的散列函数和相等运算符通常很容易。

如果性能是一个真正的问题，并且您对每个节点的 children 数量也有一个（合理的）上限，您可以考虑将 std::unordered_set<uint_32> children 替换为 std::array<uint_32, n> children使用 std::find() 检测碰撞。

原因很简单，确保 node 变为 TriviallyCopyable，从而在内部将 re-allocations 减少为普通的 memcpy。对于最多 16 children 左右，这在内存消耗方面可能是中性的，但仍然更快。

Answer 2

我猜你有一棵大小超过 1000 万个元素（或至少大约有 100k+ 个元素）的树来处理这个问题。

这完全取决于您的数据和树的使用方式。数据的空间性通常值得关注，但如果您也是这种情况，则它并不明显。如果树在构建后被遍历了很多（有点反对被修改了很多）并且只被修改了一点，那么尝试组织数据使得它迭代连续（通常是 std::vector 是有意义的是）。在这种情况下，你 not 想要这样的指针，或者你 not 想要使用单个元素 new/delete 可以肯定，因为这几乎可以保证让您失望（因为您不能指望元素在内存中连续放置）-但这完全取决于您的用例（s ).

一个简单的方法和根本不同的方法是：

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

然后对其进行排序，使 Node 以您迭代树的顺序出现。这是一个有点极端的解决方案，并且有缺点，包括如果正在进行大量随机插入，插入现在会变得昂贵。我也遗漏了如何在树中实现路径，但它通常应该是某种序列（比如在文件系统结构中）。

堆分配与 std::vector

Heap allocation vs std::vector

c++

performance

containers

heap-memory

c++-standard-library