我想实现一个容器。数据将存储在动态分配的数组中。我需要有关内存重新分配的建议。
基本上，我想要一个公式，说明当数组已满时我应该使数组变大多少。我认为一个常数值是次优的，因为数组越大，复制它所需的时间就越长。
例如，如果一个数组可以存储 1000000 个双精度并且它已满，那么重新分配 1000005 个双精度将是愚蠢的。去 1001000 会是一个更好的主意。相反，如果我有一个包含 5 个双精度的数组并且它已满，将其扩大到 1005 个单位同样愚蠢。也许每次都将它放大 10%（或者像 20+10% 这样在小型阵列上也感觉不错）会是一个更好的主意。对此有何建议？
我将从重用 std::vector 开始。不要重新实现已经运行良好的东西。
如果您对数据的大小有所了解，请使用 reserve() 函数来确保您分配的频率不会超出您的需要。如果您不知道自己拥有多少数据，请随意保留 20% 或 40% 的额外空间。
如果您对数据的大小一无所知，那么 std::vector 会在不知道任何内容的情况下进行优化以获得良好的性能。如果您对数据的大小一无所知，那么您同样可能拥有 10001 个条目并且让向量浪费地分配大量空间，就像您拥有 9999 个条目并且让向量避免 4 或 5 个不那么激进的算法选择的浪费副本一样。Std::vector 实现经过数百个工时的微调，以确保在用户没有关于大小的信息时的最佳行为。
我开始偏离这一点的唯一一次是当您开始使用千兆字节数据集时。然后很高兴确保您不会分配太大而无法放入内存的东西。