当在 C 中创建自动扩展数组（如 C++ 的 std::vector）时，通常（或者至少是常见的建议）在每次填充时将数组的大小加倍，以限制调用的数量realloc为了尽可能避免复制整个数组。
例如。我们首先为 8 个元素分配空间，插入 8 个元素，然后为 16 个元素分配空间，再插入 8 个元素，再分配 32 个元素，等等。
But 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每次将元素添加到动态数组时？
您必须从代码中退一步，抽象地思考一下。开发动态容器的成本是多少？程序员和研究人员不会考虑“这花了 2 毫秒”，而是考虑了渐进复杂性：考虑到我已经拥有了，增长一种元素的成本是多少n元素；这是如何改变的n增加？
如果您仅以恒定（或有界）数量增长，那么您将必须定期移动所有数据，因此增长成本将取决于容器的大小，并随着容器的大小而增长。相比之下，当您以几何方式增长容器时，即multiply它的大小乘以一个固定的因子，每次它满了，那么expected插入成本实际上是独立的元素的数量，即constant.
当然不是always恒定，但它是摊余常数，这意味着如果您继续插入元素，那么每个元素的平均成本是恒定的。你时不时地必须成长和移动，但随着你插入越来越多的元素，这些事件变得越来越罕见。
我曾经问过C++ 分配器的增长是否有意义，以这样的方式realloc做。我得到的答案表明，非移动的生长行为realloc当你渐进地思考时，实际上有点转移注意力。最终你将无法再成长，你将不得不移动，因此为了研究渐近成本，是否realloc有时可以是空操作，也可以不是。 （此外，不动的增长似乎让现代的、基于竞技场的分配者感到不安，他们期望所有的分配都具有相似的规模。）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
