c++ - 基于 STL 双端队列的树与二叉树的自己实现？

Question

这是跟进 Is a list implementation of binary tree scalable?

树实现的优点或缺点是什么？使用线性数组(STL vector)或 STL deque

而不是单个节点具有左右指针的二叉树？

假设:树将被预先计算，一旦构建就不会被修改，只会用于搜索。

Answer 1

嗯，我想说的是这些:

• 使用指针树，您可以为数据和指向数据的指针使用内存，而使用std::vector，您只需为数据<分配内存/em>(容器处理自身的迭代)
• 如果您使用std::vector，您的内存是本地化的。例如。如果你想访问一棵树的单个完整级别，这将在内存中是顺序的，而单独分配的各个节点，你会像小兔子一样跳过内存访问所有这些
• 如果你分配单独的节点，你实际上没有办法分配它们，除非单独分配。这意味着对 malloc-euqivalent 函数的大量调用。 (在 C 中您可以使用一些技巧来避免这种情况，它们在 C++ 中仍然有效，但是如果您有现成的 std，为什么还要使用 hack: :vector 解决方案)。
• 创建 vector 时，可以使用std::vector.reserve() 预分配所有内存。此外，如果您知道 vector 是如何运行的，您就会知道它会调用一个 malloc - 大约每次您开始树的新级别时，它都会调用一个等价物来保留内存 - 分配的数量应该大致等于 number树中的级别
• 访问 vector 的元素非常简单，在基于 vector 的完全填充的二叉树中导航非常直观且易于使用