时间戳

首页 > 解决方案 > 堆分配与 std::vector

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

问题描述

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

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();

对于大（或巨大）树来说，它有没有可能更快？

标签： c++performancecontainersheap-memoryc++-standard-library

解决方案

我猜你有一棵大小超过 1000 万个元素（或至少在 100k+ 个元素的范围内）的树来关注这个问题。

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

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

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

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

推荐阅读