是否有必要将动态数组的容量加倍？

Question

在 C 中创建自动扩展数组（如 C++ 的 std::vector）时，通常（或者至少是常见的建议）在每次填充时将数组的大小加倍，以限制调用量，以realloc避免尽可能复制整个数组。

例如。我们首先为 8 个元素分配空间，插入 8 个元素，然后为 16 个元素分配空间，再插入 8 个元素，再分配 32 个元素，等等。

但realloc如果可以扩展现有的内存分配，则不必实际复制数据。例如，以下代码在我的系统上仅执行 1 次复制（初始 NULL 分配，因此它不是真正的副本），即使它调用了realloc10000 次：

#include <stdlib.h>
#include <stdio.h>

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每次将元素添加到动态数组时都调用不是更好吗？

Answer 1

您必须从代码中退一步，抽象地思考一下。开发动态容器的成本是多少？程序员和研究人员不会从“这花了 2 毫秒”的角度思考，而是从渐进复杂度的角度思考：考虑到我已经有了元素，增长一个元素的成本是多少n？随着增加它会如何变化n？

如果您仅以恒定（或有界）数量增长，那么您将必须定期移动所有数据，因此增长成本将取决于容器的大小，并随着容器的大小而增长。相比之下，当您以几何方式增长容器时，即将其大小乘以固定因子，每次容器满时，则插入的预期成本实际上与元素数量无关，即常数。

它当然并不总是恒定的，但它是摊销常数，这意味着如果您继续插入元素，那么每个元素的平均成本是恒定的。你时不时地必须成长和移动，但随着你插入越来越多的元素，这些事件变得越来越罕见。

我曾经问过C++ 分配器能够以这种方式增长是否有意义realloc。我得到的答案表明，当你渐近地思考时， 的非移动增长行为realloc实际上有点转移注意力。最终你将无法再成长，你将不得不移动，因此为了研究渐近成本，realloc有时是否可以进行空操作实际上是无关紧要的。（此外，不动的增长似乎让现代的、基于竞技场的分配者感到不安，他们期望所有的分配都具有相似的规模。）