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)数组 (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);
    }
   
}

- Freddy

---

out 是如何定义的？length 和 size 分别是什么意思？ - evgeny

你说realloc抱怨它没有动态分配。那么... 它是否被动态分配了？你必须先使用malloc才能后续使用realloc。 - Daniel Brockman

在传递给insertVertex()之前，您能否展示一下length或size的定义？ - Timothy Jones

evgeny out被定义为：Vertex *out = （Vertex ）malloc（sizeof（Vertex） numOfVerInPolygon）其中numOfVerInPolygon是多边形中顶点的数量。Daniel Brockman 是用malloc定义的。在传递之前，它定义如下。 Vertex *out = （Vertex ）malloc（sizeof（Vertex） numOfVerInPolygon）TimothyJones 抱歉，长度和大小是一样的。我更新了帖子，使所有内容都使用大小。大小最初为零：int *size = 0;当我们遍历每个顶点时，如果它在剪辑平面中，则将其添加到out []（Vertex）后，大小会增加一。 - Freddy

int *size = 0 会将 size 初始化为 NULL，并且不会给你一个指向值为 0 的 int 指针。除非你之后将其指向一个实际的 int，否则这可能是你的问题所在。 - Dmitri

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（）函数的反直觉性质，即在传入的指针为null时它会执行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()。

- Jonathan Leffler

---

Leffier 谢谢。你和Santoj真的帮了我很多。我已经更新了我的方法，想知道这样做是否可以。'void addPointerToPointerArray(Vertex v1, Vertex **out, int *size) { int newSize = *size; newSize++; Vertex *tempOut = (Vertex *)malloc(sizeof(Vertex) * newSize);if (tempOut != 0) { int i = 0; while (i < *size) { tempOut[i] = (*out)[i]; i++; } free(*out); *out = tempOut; } (*out)[(*size)] = v1; *size = newSize;}' - Freddy

是的 - 有一些限制。 while 循环应该改成 for 循环，或者用 memmove() 或 memcpy() 替换。使用 realloc() 意味着您不需要自己进行复制，而且它可能不需要复制所有数据。每次增加一个大小都会成为一个问题，尤其在这个“始终复制”模式下使用函数时。第一次添加一个大小，你会复制3个项目;下一个，你会复制4个;下一个，你会复制5个，以此类推。但是您现在的代码似乎可以胜任工作。（我重新格式化了它以便查看；我没有通过编译器运行它，更不用说 valgrind 了。） - Jonathan Leffler

很好的解释。谢谢。 - Xplouder

Answer 2

我有一些建议供您考虑：
1. 在使用 realloc 时，不要使用相同的输入和输出参数，因为如果内存分配失败并且之前指向的内存泄漏了，它可以返回 NULL。 realloc 可能会返回一个新的内存块（感谢 @Jonathan Leffler 指出，我之前漏掉了这一点）。您可以将您的代码更改为类似以下内容：

Vertex * new_out = realloc(out,  newSize * sizeof(Vertex));
if( NULL != new_out )
{    
    out = new_out;
    out[(*size)] = v1;
}
else
{
 //Error handling & freeing memory
}

2. 在 malloc 调用中添加 NULL 检查，并在内存失败时处理错误。
3. 缺少对 free 的调用。
4. 将 addPointerToArray() 的返回类型从 void 更改为 bool，以指示添加是否成功。如果 realloc 失败，则可以返回失败，即 false；否则，可以返回成功，即 true。
@MatthewD 已经指出了与过度复制等相关的其他观察结果。
@Jonathan Leffler 也提出了一些好的建议 (：
希望这有所帮助！

- another.anon.coward

---

+0.5：你提出了一些好观点，特别是关于误用out = realloc(out, newSize * sizeof(Vertex));。然而，你没有提到一个关键点，即realloc()可能返回与提供的指针不同的指针 - 数据可能会移动。这个事实需要采取不同的策略；请参见我的答案。 - Jonathan Leffler

@Jonathan Leffler：非常感谢！我错过了它...已编辑响应。 - another.anon.coward

Answer 3

尝试这些变更，应该能够工作。

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;
}

并像这样调用函数

addPointerToArray(vertexToAdd, &out, size);

• 有一种简单的方法可以解决这些问题（你可能已经知道了）。当你将参数传递给函数时，想一想到底会发生什么，并结合这样一个事实：无论你对栈上存在的变量做出什么更改，当它们离开函数时都会消失。这种思考方式应该可以解决大多数与传递参数相关的问题。

• 至于优化部分，选择正确的数据结构对任何项目的成功至关重要。就像有人在上面指出的那样，链表比数组更适合你。

- Santosh

Answer 4

你的示例程序在我这里运行良好。我正在Linux上使用gcc 4.1.1。

然而，如果你的实际程序与你的示例程序相似，那么它效率可能比较低下！

例如，你的程序经常复制内存：结构体复制 - 初始化out，将顶点传递给addPointerToArray()，通过realloc()进行内存复制。

通过指针而不是拷贝来传递结构体。

如果你需要大量增加列表类型的大小，最好使用链表、树或其他数据结构（取决于后续所需的访问类型）。

如果你必须要有一个向量类型，一种标准的动态实现方法是分配一块内存（例如，为16个顶点留出空间），并在每次用完空间时将其大小加倍。这将限制所需的重新分配次数。

- MatthewD