C malloc 用例 - 重新分配与预计算

Question

我想从另一个数据结构在堆上创建一个结构数组。假设总共有 N 个元素要遍历，并且 (N-x) 个指针 (computed_elements) 将被添加到数组中。

我对此的幼稚策略是在堆栈上创建一个大小为 N 的数组 (temp_array) 并遍历数据结构，跟踪需要向数组中添加多少元素，并在遇到它们时将它们添加到 temp_array .完成后，我 malloc(computed_elements) 并使用 temp_array 填充此数组。

这是次优的，因为第二个循环是不必要的。但是，我正在权衡每次迭代不断重新分配内存的权衡。一些粗略的代码来澄清:

void *temp_array[N];
int count = 0;
for (int i = 0; i < N; i++) {
  if (check(arr[i])) {
    temp_array[count] = arr[i];
    count++;
  }
}

void *results = malloc(count * sizeof(MyStruct));
for (int i = 0; i < count; i++) {
  results[i] = temp_array[i];
}

return results;

想法将不胜感激。

Answer 1

一个常见的策略是尝试估计您将需要的元素数量(不是接近的估计，更多的是“按...的顺序”类型的估计)。 Malloc 那个内存量，当你“接近”那个限制时(“接近”也有待解释)，重新分配一些。就个人而言，我通常会在快要填满数组时将数组加倍。

-编辑-

这里是“十分钟版”。 (我确保它可以构建并且不会出现段错误)

显然我省略了检查 malloc/realloc 是否成功、清零内存等...

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>     /* for the "malloc only version" (see below) */

/* Assume 500 elements estimated*/
#define ESTIMATED_NUMBER_OF_RECORDS   500

/* "MAX" number of elements that the original question seems to be bound by */
#define N   10000

/* Included only to allow for test compilation */
typedef struct
{
    int foo;
    int bar;
} MyStruct;

/* Included only to allow for test compilation */
MyStruct arr[N] = { 0 };

/* Included only to allow for test compilation */
bool check(MyStruct valueToCheck)
{
    bool baz = true;
    /* ... */
    return baz;
}

int main (int argc, char** argv)
{
    int idx = 0;
    int actualRecordCount = 0;
    int allocatedSize = 0;
    MyStruct *tempPointer = NULL;

    MyStruct *results = malloc(ESTIMATED_NUMBER_OF_RECORDS * sizeof(MyStruct));
    allocatedSize = ESTIMATED_NUMBER_OF_RECORDS;

    for (idx = 0; idx < N; idx++)
    {
        /* Ensure that we're not about to walk off the current array */
        if (actualRecordCount == (allocatedSize))
        {
            allocatedSize *= 2;

            /* "malloc only version"
             * If you want to avoid realloc and just malloc everything...
             */
            /*
            tempPointer = malloc(allocatedSize);
            memcpy(tempPointer, results, allocatedSize);
            free(results);
            results = tempPointer;
            */

            /* Using realloc... */
            tempPointer = realloc(results, allocatedSize);
            results = tempPointer;
        }

        /* Check validity or original array element */
        if (check(arr[idx]))
        {
            results[actualRecordCount] = arr[idx];
            actualRecordCount++;
        }
    }

    if (results != NULL)
    {
        free(results);
    }

    return 0;
}