C语言未知大小数组的高效实现及结构体管理技术问询

当我们需要使用大小未知的C数组时，通常的做法是先分配较小的内存，再按需倍增扩容并重新分配内存，完成操作后重新分配以释放未使用的内存，对吗？

以下是你给出的示例代码：

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

int main()
{
    // unknown = an unknown amount of work we need to do
    int unknown = 1234;

    // size = the current allocated memory
    int size = 10;

    // counter = the final size of the array
    int counter = 0;

    // first we allocate a small amount for our array
    int *array = (int *) malloc(size * sizeof(int));

    // and then start working
    for(int i = 0; i < unknown; i++)
    {
        // work
        array[i] = i; counter++;

        // check the size of the array to see if we need to realloc
        if (counter == size)
        {
            size *= 2;
            array = (int *) realloc(array, sizeof(size));
        }
    }

    // when all of the work is done we then shorten it to the exact size
    array = (int *) realloc(array, sizeof(counter));

    printf("%d", counter);
}

问题1：上述处理未知大小数组的方式是否为性能最优的方案？ #

首先得指出示例代码里的致命错误：两次realloc的第二个参数都写错了——sizeof(size)和sizeof(counter)得到的是int类型的字节数（通常是4），而不是数组需要的总内存。正确写法应该是size * sizeof(int)和counter * sizeof(int)，不然会直接导致内存分配不足，触发数组越界访问，程序大概率崩溃。

回到性能问题：倍增扩容的思路是时间效率上接近最优的方案。通过摊还分析可以算出，这种方式下所有插入操作的总时间复杂度是O(n)，因为每次扩容后，接下来的n/2次插入都不需要再分配内存，不会频繁触发realloc的开销。

当然也有优化空间：如果能提前大致预估数据量，先分配接近预估的容量可以减少扩容次数，但如果预估不准，倍增扩容依然是最稳妥的选择。另外，最后缩容到精确大小的操作要看场景——如果后续还要往数组里加元素，缩容反而会导致下次插入又要扩容，反而拖慢性能；如果确定数组不再修改，缩容能节省内存，这是空间和时间的权衡。

问题2：由于需要跟踪数组的大小，多数开发者是否会使用结构体来进行管理？示例结构体如下： #

typedef struct list
{
    int size;
    int *array;
} list;

是的，绝大多数开发者都会用结构体来管理动态数组的状态。原因很简单：

• 把数组指针、已分配容量、已使用元素数这些变量打包在一起，避免到处传递零散的变量，减少出错的概率。
• 方便封装成一套操作函数，比如初始化、插入元素、扩容、销毁数组，代码更模块化，复用起来更方便。
• 还能灵活扩展字段，比如如果要做通用型的动态数组，可以加个element_size字段存储单个元素的字节数，适配不同类型的数据。

另外，你给出的示例结构体可以优化一下，把size拆成capacity（当前已分配的总容量）和count（已使用的元素个数），这样逻辑更清晰，不会混淆“能装多少”和“已经装了多少”：

typedef struct list
{
    int capacity; // 当前分配的总容量
    int count;    // 已使用的元素个数
    int *array;   // 数组指针
} list;

内容的提问来源于stack exchange，提问作者user2980746