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

Question

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

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

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

#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 的增加，这种情况如何变化？

如果您只按恒定(或有界)量增长，那么您将不得不定期移动所有数据，因此增长的成本将取决于容器的大小，并随着容器的大小而增长。相比之下，当您以几何方式增长容器时，即将其大小乘以一个固定因子时，每次容器装满时，插入的预期成本实际上是独立于元素的数量，即常量。

它当然不是总是常量，但它是摊销常量，这意味着如果您不断插入元素，那么每个元素的平均成本是常量。您时不时地需要成长和移动，但是随着您插入越来越多的元素，这些事件会变得越来越少。

我曾经问过whether it makes sense for C++ allocators to be able to grow ，就像 realloc 那样。我得到的答案表明，当您渐近地思考时，realloc 的非移动增长行为实际上有点转移注意力。最终你将无法再增长，你将不得不移动，所以为了研究渐近成本，realloc 有时是空操作还是不是。 (此外，非移动增长似乎扰乱了现代的、基于竞技场的分配器，这些分配器期望它们的所有分配都具有相似的大小。)