是否需要将动态arrays的容量加倍？
当在C中自动扩展数组（如C ++的std :: vector）时，通常（或至少是常见的建议）在每次填充时将数组的大小加倍，以限制对realloc的调用量，以便避免尽可能复制整个arrays。
例如。 我们首先为8个元素分配空间，插入8个元素，然后我们为16个元素分配空间，插入8个元素，我们分配32 ..等等。
但是如果realloc可以扩展现有的内存分配，则不必实际复制数据。 例如，以下代码仅在我的系统上执行1次复制（初始NULL分配，因此它实际上不是副本），即使它调用realloc 10000次：
#include #include int main() { int i; int copies = 0; void *data = NULL; void *ndata; for (i = 0; i < 10000; i++) { ndata = realloc(data, i * sizeof(int)); if (data != ndata) copies++; data = ndata; } printf("%d\n", copies); }
我意识到这个例子非常临床 – 一个真实世界的应用程序可能会有更多的内存碎片，并会做更多的副本，但即使我在realloc循环之前做了一堆随机分配，它只会略微恶化2-4副本代替。
那么，“倍增方法”真的有必要吗？ 每次将元素添加到动态数组时调用realloc会不会更好？
你必须从代码中退一分钟，抽象地抽象。 种植动态容器的成本是多少？ 程序员和研究人员并没有考虑“这需要2ms”，而是考虑渐近复杂性 ：考虑到我已经有n元素，由一个元素成长的成本是多少; 当n增加时，这会如何变化？
如果你只是以恒定（或有限）的数量增长，那么你将不得不定期移动所有数据，因此增长的成本将取决于容器的大小，并随之增长。 相比之下，当您在几何上增长容器时，即将其大小乘以固定因子，每次填充时，插入的预期成本实际上与元素数量无关 ，即不变 。
它当然不总是恒定的，但它的摊销是不变的 ，这意味着如果你继续插入元素，那么每个元素的平均成本是不变的。 时不时地你必须成长和移动，但是当你插入越来越多的元素时，这些事件变得越来越罕见。
我曾经问过，就像realloc那样，C ++分配器能够增长是否realloc 。 我得到的答案表明，当你渐近思考时， realloc的非移动增长行为实际上有点像红鲱鱼。 最终你将无法再成长，你将不得不移动，所以为了研究渐近成本， realloc有时候是无操作也无关紧要。 （此外，不动的增长似乎打乱了现代，基于竞技场的分配器，它们期望所有分配都具有相似的大小。）
与几乎所有其他类型的操作相比， malloc ， calloc ，尤其是realloc都非常昂贵。 我个人对10,000,000个reallocs进行了基准测试，这需要花费大量时间。
即使我同时进行了其他操作（在两个基准测试中），我发现通过使用max_size *= 2而不是max_size += 1 ，我可以从运行时间中逐渐减少HOURS。
问：’将动态arrays的容量增加一倍“
答：没有。一个人只能在必要的程度上成长。 但是，您可能会多次真正复制数据。 这是内存和处理器时间之间的经典折衷。 一个好的增长算法会考虑到对程序数据需求的了解，也不会过度考虑这些需求。 指数增长2倍是一个愉快的妥协。
但现在你的声明“以下代码只做1份”。
使用高级内存分配器进行复制的数量可能不是OP认为的。 获取相同的地址并不意味着底层内存映射没有执行重要的工作。 各种各样的活动都在幕后进行。
对于在代码生命周期中大量增长和缩小的内存分配，我喜欢增长和缩小几何上彼此分开的阈值。
const size_t Grow[] = {1, 4, 16, 64, 256, 1024, 4096, ... }; const size_t Shrink[] = {0, 2, 8, 32, 128, 512, 2048, ... };
通过在变大时使用增长阈值并在收缩时缩小增量阈值，可以避免在边界附近晃动。 有时使用因子1.5。