在不知道大小的情况下与 C 数组交互

Question

因此，当我们想要在不知道大小的情况下使用数组时，常见的过程是从小处开始，然后不断将大小加倍并重新分配它，对吗？

然后我假设一旦我们完成了，我们将想要再次重新分配以释放已分配但我们没有使用的多余内存？

#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：这是解决此问题的最有效方法吗？

问题 2：既然我们需要跟踪数组的大小，大多数人都会为此创建一个结构体吗？

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

Answer 1

问题1

您的方法对

O(log(unknown))

进行了

realloc

次调用，并进行了约

O(unknown)

的额外复制（10 + 20 + ... + 未知 / 2 是一个几何级数，大约等于未知）。这还不错，但你可以利用分配是惰性的，至少在 Linux 系统上是这样。您可以首先分配一些上限（例如可用 RAM 的两倍），然后填充数组。完成后，您可以重新分配。这不需要额外的复制，只需调用一次

realloc

。分配太多内存只会保留虚拟地址空间，在写入之前不会使用 RAM。

问题2

在我看到的大多数代码中，人们只是显式地将大小传递给函数，但我不认为使用结构有什么问题。我建议使用

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

否则，假设

int

是 32 位，您的数组将被限制为 8 GiB。