pool - 数据结构的资源池

Question

当实现一个基本的数据结构时，如stack, queues, linked listet al. 我应该通过动态分配内存来创建资源池（节点）还是应该在每次需要节点时单独分配内存？

Answer 1

这完全取决于你的目标。默认情况下（即除非您真的需要这样做），只需为每个下一个节点进行正常分配。

与仅分配节点相比的内存池：

• 使分配更快。取决于底层的分配机制，有时会明显更快。

• 通常较少的内存碎片，尽管这对于某些分配器可能不是问题。

• 主要缺点：在保留但未使用的节点上浪费内存。如果您不加选择地使用数据结构（例如 1000 个实例）而不是仅使用几个实例，这一点非常重要。

由于这个缺点，内存池不适合一般情况。

在 C++ 中，所有标准容器都有一个allocator模板参数。

Answer 2

这是基本的时间与空间权衡。根据对您更重要的内容进行选择：

如果您提前分配池，那么您的运行时元素插入将 - 平均 - 针对速度进行优化，即恒定时间，即 O(1)。“平均而言”意味着大多数插入将是恒定时间，除了那些达到最大值并需要扩展池的插入，它们是线性时间，O(n)。如果您最终没有使用整个池，您也可能会浪费一些内存。

如果对每一个新节点做实时分配，总会有常量时间插入，但是这种情况下，常量时间比上面的常量时间长一点，因为你不仅要在一个内存位置，但您还必须首先分配内存位置。此外，这种方法通过预先保留内存位置不会浪费任何内存。

在大多数情况下，我认为实时分配在时间上是足够有效的，我不明白为什么要使用池化方法，除非您的应用程序需要极高的平均速度或者您进行大量插入。