为什么需要为不断增长的指针数组重新分配内存？

Question

typedef struct { 
    void **head; 
    size_t used_size; 
    size_t free_size; 
    size_t current_size; 
    size_t size_increment; 
} GrowingArray; 

GrowingArray createEmptyGrowingArray(int initial_size, int size_increment) { 
    GrowingArray empty_growing_array; 
    empty_growing_array.head = malloc(initial_size * sizeof(void *)); 
    empty_growing_array.used_size = 0; 
    empty_growing_array.free_size = initial_size; 
    empty_growing_array.current_size = initial_size; 
    empty_growing_array.size_increment = size_increment; 

    return empty_growing_array; 
} 

GrowingArray appendToGrowingArray(GrowingArray growing_array, void *new_element) { 

    void *new_head_of_array; 

    if (growing_array.free_size == 0) { 
     new_head_of_array = realloc(growing_array.head, (growing_array.current_size + growing_array.size_increment) * sizeof(void*)); 
     if (new_head_of_array == NULL) { 
      printf("Reallocation failure.\n"); 
     } 

     growing_array.free_size = growing_array.size_increment; 
     growing_array.current_size += growing_array.size_increment; 
     growing_array.head = new_head_of_array; 
    } 

    growing_array.head[growing_array.used_size++] = new_element; 
    growing_array.free_size--; 

    return growing_array; 
} 

void finalizeGrowingArrayMemory(GrowingArray growing_array) { 
    growing_array.head = realloc(growing_array.head, growing_array.current_size * sizeof(void *)); 
} 

void freeGrowingArray(GrowingArray growing_array) { 
    free(growing_array.head); 
} 

int main(int argc, char* argv[]) { 
    GrowingArray test_array = createEmptyGrowingArray(5, 1); 

    int *test_integer = (int *)malloc(1 * sizeof(int)); 
    *test_integer = 4; 

    int *another_integer = (int *)malloc(1 * sizeof(int)); 
    *another_integer = 6; 

    int *yet_another_integer = (int *)malloc(sizeof(int)); 
    *yet_another_integer = 9; 

    test_array = appendToGrowingArray(test_array, test_integer); 
    test_array = appendToGrowingArray(test_array, another_integer); 
    test_array = appendToGrowingArray(test_array, yet_another_integer); 
    finalizeGrowingArrayMemory(test_array); 

    printf("%x,", *(int *)test_array.head[0]); 
    printf("%x,", *(int *)test_array.head[1]); 
    printf("%x\n", *(int *)test_array.head[2]); 

    freeGrowingArray(test_array); 

    printf("Going to free %llx\n", (long long int)test_integer); 
    free(test_integer); 

    printf("Going to free %llx\n", (long long int)another_integer); 
    free(another_integer); 

    printf("Going to free %llx\n", (long long int)yet_another_integer); 
    free(yet_another_integer); 

    return 0; 
} 

我写这些代码基于在正确答案提供对这个问题的示例代码：How may I implement a generic, dynamically growing array in C?

提供的答案包括简单地重新分配指针数组的函数。预期的用法是在将几个项目附加到数组之后调用它，如答案的代码所示。

我想知道为什么应该这样做。它提供了什么好处？ realloc（）是否尝试根据之前的使用情况预测一块内存将被使用，然后将其移动到它认为最好的地方？

谢谢！

作为附加是或不是问题：我应该使用calloc()而不是malloc()里面的createEmptyGrowingArray()？

Answer 1

我想知道为什么要这样做。它提供了什么好处？

我觉得你问为什么有一个功能，或者为什么有一个可配置的增量：

• 它的方便再分配细节分成自己的领域，以避免弄乱你的代码，还提供可重复使用的调整大小操作，可以从您可能实现的其他形式的“插入”调用中调用该操作。
• 通过增加配置，您可以通过多个元素放大数组，从而防止过度重新分配。
• 虽然你的例子没有这样做，但增加增量大小也是有用的。这将允许constant amortized time complexity阵列增长。

是否realloc（）的尝试做出如何的内存块基于其先前使用将被用来预测，然后将它放在它认为是最好的？

不，它不知道你的块被用于什么。它只是分配一块内存。如果它可以在不移动内存的情况下调整它的大小，它会。但是，如果没有足够的空间，或者它必须移动到不同的分配方案（内存管理器经常会根据它们的大小将块拆分到不同的区域），那么指针将移动，并且该内存的内容将被复制到新的位置。

作为一个附加的是或否问题：我应该使用calloc（）而不是malloc（）在createEmptyGrowingArray（）中吗？

这是合理的做法是使用calloc，但是当你创建一个空的数组记住，你当前的大小设置为零，所以malloc就够了，因为你不打算使用这些未初始化的值，直到你稍后进行初始化（追加后）。此外，在调用realloc来增加块之后，目前您并未将新内存中的指针归零，因此它不会为您的“创建”操作提供概念上的一致性。

所以你的情况，我认为使用malloc这不会给你的未使用的数据的状态不切实际的期望。如果你想使用calloc创建的时候，那么你应该也越来越大后使用memset零出新的记忆。