c - C 中的动态数组 - realloc

Question

我知道如何构建动态分配的数组，但不知道如何增长它们。

例如我有以下界面..

void insertVertex( vertex p1, vertex out[], int *size);

此方法获取一个顶点并将其存储到 out 数组中。存储顶点后，我增加了长度以供将来调用。

p1 - 是我要添加的顶点。

out[] - 是我需要存储它的数组(它总是满的)

length - 当前长度

顶点定义为..

typedef struct Vertex{
int x;
int y;
} Vertex;

这就是我在 Java 中使用的..

Vertex tempOut = new Vertex[size +1];
//Code to deep copy each object over
tempOut[size] = p1;
out = tempOut;

这就是我相信我可以在 c.. 中使用的东西

out = realloc(out, (*size + 1) * sizeof(Vertex));
out[(*size)] = p1;

但是，我不断收到一条错误消息，指出对象不是动态分配的。

我找到了解决此问题的解决方案。我没有使用 Vertex*，而是改用 Vertex** 并存储指针与顶点。然而，在切换所有内容后，我发现我忽略了一个事实，即单元测试将为我提供一个 Vertex out[]，所有内容都必须存储在其中。

我也尝试过以下方法，但没有成功。

Vertex* temp = (Vertex *)malloc((*size + 1) * sizeof(Vertex));
for(int i = 0; i < (*size); i++)
{
temp[i] = out[i];
}
out = temp;

但是，无论我在这两个之后进行测试时做什么，返回的数组都没有改变。

更新 - 要求的信息

out - 被定义为顶点数组(Vertex out[])

它最初是用我的多边形中的顶点数构建的。例如。

out = (Vertex *)malloc(vertexInPolygon * sizeof(Vertex))

其中 vertexInPolygon 是多边形中顶点数的整数。

length 是一个错字，应该是 size。

Size是一个整型指针

int *size = 0;

每当一个顶点在裁剪平面中时，我们将其添加到顶点数组中并将大小增加一。

更新

为了更好地解释我自己，我想出了一个简短的程序来展示我正在尝试做的事情。

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

typedef struct Vertex {
    int x, y;
} Vertex;

void addPointerToArray(Vertex v1, Vertex out[], int *size);

void addPointerToArray(Vertex v1, Vertex out[], int *size)
{
    int newSize = *size;
    newSize++;
    
    out = realloc(out, newSize * sizeof(Vertex));
    out[(*size)] = v1;
    
    //  Update Size
    *size = newSize;
}

int main (int argc, const char * argv[])
{
    //  This would normally be provided by the polygon
    int *size = malloc(sizeof(int)); *size = 3;
    
    //  Build and add initial vertex
    Vertex *out = (Vertex *)malloc((*size) * sizeof(Vertex));
    Vertex v1; v1.x = 1; v1.y =1;
    Vertex v2; v2.x = 2; v2.y =2;
    Vertex v3; v3.x = 3; v3.y =3;
    
    out[0] = v1;
    out[1] = v2;
    out[2] = v3;
    
    //  Add vertex
    //  This should add the vertex to the last position of out
    //  Should also increase the size by 1;
    Vertex vertexToAdd; vertexToAdd.x = 9; vertexToAdd.y = 9;
    addPointerToArray(vertexToAdd, out, size);
    
    for(int i =0; i < (*size); i++)
    {
        printf("Vertx: (%i, %i) Location: %i\n", out[i].x, out[i].y, i);
    }
   
}

Answer 1

一个长期存在的问题是您没有从 addPointerToArray() 函数返回更新后的数组指针:

void addPointerToArray(Vertex v1, Vertex out[], int *size)
{
    int newSize = *size;
    newSize++;

    out = realloc(out, newSize * sizeof(Vertex));
    out[(*size)] = v1;

    //  Update Size
    *size = newSize;
}

当您重新分配空间时，它可以移动到一个新位置，因此 realloc() 的返回值不必与输入指针相同。当您添加到数组时没有其他内存分配正在进行时这可能会起作用，因为 realloc() 将在有空间的情况下扩展现有分配，但一旦您开始它就会失败在读取顶点时分配其他数据。有几种方法可以解决此问题:

Vertex *addPointerToArray(Vertex v1, Vertex out[], int *size)
{
    int newSize = *size;
    newSize++;

    out = realloc(out, newSize * sizeof(Vertex));
    out[(*size)] = v1;

    //  Update Size
    *size = newSize;
    return out;
}

和调用:

out = addPointerToArray(vertexToAdd, out, size);

或者，您可以传入一个指向数组的指针:

void addPointerToArray(Vertex v1, Vertex **out, int *size)
{
    int newSize = *size;
    newSize++;

    *out = realloc(*out, newSize * sizeof(Vertex));
    (*out)[(*size)] = v1;

    //  Update Size
    *size = newSize;
}

和调用:

out = addPointerToArray(vertexToAdd, &out, size);

这些重写都没有解决微妙的内存泄漏问题。问题是，如果您用返回值覆盖传递给 realloc() 的值，但 realloc() 失败，您将丢失指向(仍然)分配的数组的指针- 内存泄漏。当您使用 realloc() 时，请使用像这样的成语:

Vertex *new_space = realloc(out, newSize * sizeof(Vertex));
if (new_space != 0)
    out = new_space;
else
    ...deal with error...but out has not been destroyed!...

请注意，使用 realloc() 一次添加一个新项目会导致(可能导致)二次行为。你最好分配一大块内存——例如，将分配的空间加倍:

int newSize = *size * 2;

如果担心过度分配，在读取循环结束时，可以使用realloc() 将分配的空间缩小到数组的确切大小。但是，还有更多的簿记工作要做；你需要值:分配给数组的顶点数，以及实际使用的顶点数。

最后，至少现在，请注意您真的应该严格保持一致并使用 addPointerToArray() 将前三个条目添加到数组中。我可能会使用类似于此(未经测试的)代码的东西:

struct VertexList
{
    size_t    num_alloc;
    size_t    num_inuse;
    Vertex   *list;
};

void initVertexList(VertexList *array)
{
    // C99: *array = (VertexList){ 0, 0, 0 };
    // Verbose C99: *array = (VertexList){ .num_inuse = 0, .num_alloc = 0, .list = 0 };
    array->num_inuse = 0;
    array->num_alloc = 0;
    array->list      = 0;
}

void addPointerToArray(Vertex v1, VertexList *array)
{
    if (array->num_inuse >= array->num_alloc)
    {
        assert(array->num_inuse == array->num_alloc);
        size_t new_size = (array->num_alloc + 2) * 2;
        Vertex *new_list = realloc(array->list, new_size * sizeof(Vertex));
        if (new_list == 0)
            ...deal with out of memory condition...
        array->num_alloc = new_size;
        array->list      = new_list;
    }
    array->list[array->num_inuse++] = v1;
}

这使用了 realloc() 的反直觉属性，如果传入的指针为空，它将执行 malloc()。您可以改为检查 array->list == 0，然后使用 malloc()，否则使用 realloc()。

您可能会注意到这种结构也简化了调用代码；您不再需要处理主程序中单独的 int *size;(及其内存分配)；大小被有效地捆绑到 VertexList 结构中作为 num_inuse。主程序现在可以开始了:

int main(void)
{
    VertexList array;
    initVertexList(&array);
    addPointerToArray((Vertex){ 1, 1 }, &array);  // C99 compound literal
    addPointerToArray((Vertex){ 2, 2 }, &array);
    addPointerToArray((Vertex){ 3, 3 }, &array);
    addPointerToArray((Vertex){ 9, 9 }, &array);

    for (int i = 0; i < array->num_inuse; i++)
        printf("Vertex %d: (%d, %d)\n", i, array->list[i].x, array->list[i].y, i);

    return 0;
}

(巧合的是这个序列只会调用一次内存分配，因为新的大小(old_size + 2) * 2第一次给数组分配了4个元素。很容易练习通过添加新点或将公式改进为 (old_size + 1) * 2 或 ...

来重新分配

如果您计划从内存分配失败中恢复(而不是在它发生时退出)，那么您应该修改 addPointerToArray() 以返回一个状态(成功，不成功)。

此外，函数名称可能应该是 addPointToArray() 或 addVertexToArray() 甚至 addVertexToList()。