C++ 容器 : Optimal Memory Management

Question

我想实现一个容器。数据将存储在动态分配的数组中。我需要有关内存重新分配的建议。

基本上，我想要一个公式来确定当数组已满时我应该使它变大多少。我认为常量值不是最优的，因为数组越大，复制它所需的时间就越长。

例如，如果一个数组可以存储 1000000 个 double 并且它变满了，重新分配 1000005 个 double 将是愚蠢的。去 1001000 会是一个更好的主意。相反，如果我有一个包含 5 个 double 的数组并且它变满了，将它扩大到 1005 个单位同样是愚蠢的。也许每次都将它放大 10%(或者像放大 20+10% 这样在小阵列上感觉也不错)会是一个更好的主意。对此有何建议？

Answer 1

我将从重用 std::vector 开始。不要重新实现已经运行良好的东西。

如果您对数据的大小有所了解，请使用 reserve() 函数来确保您不会比需要的更频繁地进行分配。如果您不清楚自己有多少数据，请随时预留 20% 或 40% 的额外空间。

如果您对数据的大小一无所知，那么 std::vector 会在您一无所知的情况下针对良好的性能进行优化。如果您对数据的大小一无所知，那么您拥有 10001 个条目并让 vector 浪费大量空间的可能性与拥有 9999 个条目并且让 vector 避免 4 或 5 个不太积极的算法选择的浪费拷贝的可能性相同。 Std::vector 实现经过数百个工时的微调，以确保在用户没有关于大小调整的信息时的最佳行为。

我唯一开始偏离这一点的时间是当您开始使用千兆字节数据集时。然后最好确保您没有分配太大而无法放入内存的东西。