数据结构的资源池

Question

当实现像stack，queues，linked list等人这样的基本数据结构时。我是应该通过动态分配内存来创建(节点)资源池，还是应该在每次需要节点时单独分配内存？

Answer 1

这完全取决于你的目标。默认情况下(除非你真的需要这样做)，只是为每个下一个节点做一个正常的分配。

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

• 使分配速度更快。根据底层的分配机制，有时会显著减少内存碎片，尽管这可能不是一些allocators.
• Major缺点的问题:将内存浪费在保留而不是使用的节点上。如果您不加区别地使用数据结构(例如，数千个实例)，这一点非常重要，而不是只有几个实例。

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

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

Answer 2

这是一个基本的时间和空间的权衡。根据对你来说更重要的东西来选择：

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

如果对每个新节点进行实时分配，您将始终使用常量时间插入，但在本例中，常量时间比上面的常量时间稍长一些，因为您不仅需要将一个值放入内存位置，而且还必须首先分配内存位置。此外，这种方法不会因为预先预留内存位置而浪费任何内存。

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