C语言 C 动态增长数组

C dynamically growing array

提问by Balkania

I have a program that reads a "raw" list of in-game entities, and I intend to make an array holding an index number (int) of an indeterminate number of entities, for processing various things. I would like to avoid using too much memory or CPU for keeping such indexes...

我有一个程序可以读取游戏中实体的“原始”列表，我打算制作一个包含不确定数量实体的索引号 (int) 的数组，用于处理各种事情。我想避免使用太多内存或 CPU 来保留此类索引...

A quick and dirty solution I use so far is to declare, in the main processing function (local focus) the array with a size of the maximum game entities, and another integer to keep track of how many have been added to the list. This isn't satisfactory, as every list holds 3000+ arrays, which isn't that much, but feels like a waste, since I'll possible use the solution for 6-7 lists for varying functions.

到目前为止，我使用的一个快速而肮脏的解决方案是在主处理函数（局部焦点）中声明具有最大游戏实体大小的数组，以及另一个整数以跟踪已添加到列表中的数量。这并不令人满意，因为每个列表都包含 3000 多个数组，这并不多，但感觉像是一种浪费，因为我可能会使用 6-7 个列表的解决方案来实现不同的功能。

I haven't found any C (not C++ or C#) specific solutions to achieve this. I can use pointers, but I am a bit afraid of using them (unless it's the only possible way).

我还没有找到任何 C（不是 C++ 或 C#）特定的解决方案来实现这一点。我可以使用指针，但我有点害怕使用它们（除非这是唯一可能的方法）。

The arrays do not leave the local function scope (they are to be passed to a function, then discarded), in case that changes things.

数组不会离开局部函数作用域（它们将被传递给一个函数，然后被丢弃），以防发生变化。

If pointers are the only solution, how can I keep track of them to avoid leaks?

如果指针是唯一的解决方案，我如何跟踪它们以避免泄漏？

回答by casablanca

I can use pointers, but I am a bit afraid of using them.

我可以使用指针，但我有点害怕使用它们。

If you need a dynamic array, you can't escape pointers. Why are you afraid though? They won't bite (as long as you're careful, that is). There's no built-in dynamic array in C, you'll just have to write one yourself. In C++, you can use the built-in std::vectorclass. C# and just about every other high-level language also have some similar class that manages dynamic arrays for you.

如果您需要动态数组，则不能转义指针。可你为什么害怕？他们不会咬人（只要你小心，就是这样）。C 中没有内置动态数组，您只需要自己编写一个即可。在 C++ 中，您可以使用内置std::vector类。C# 和几乎所有其他高级语言也有一些类似的类可以为您管理动态数组。

If you do plan to write your own, here's something to get you started: most dynamic array implementations work by starting off with an array of some (small) default size, then whenever you run out of space when adding a new element, double the size of the array. As you can see in the example below, it's not very difficult at all: (I've omitted safety checks for brevity)

如果您确实打算自己编写，这里有一些东西可以帮助您入门：大多数动态数组实现都是从一些（小）默认大小的数组开始工作的，然后每当添加新元素时空间不足时，加倍数组的大小。正如您在下面的示例中所看到的，它一点也不难：（为了简洁，我省略了安全检查）

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void initArray(Array *a, size_t initialSize) {
  a->array = (int *)malloc(initialSize * sizeof(int));
  a->used = 0;
  a->size = initialSize;
}

void insertArray(Array *a, int element) {
  // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed.
  // Therefore a->used can go up to a->size 
  if (a->used == a->size) {
    a->size *= 2;
    a->array = (int *)realloc(a->array, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

void freeArray(Array *a) {
  free(a->array);
  a->array = NULL;
  a->used = a->size = 0;
}

Using it is just as simple:

使用它同样简单：

Array a;
int i;

initArray(&a, 5);  // initially 5 elements
for (i = 0; i < 100; i++)
  insertArray(&a, i);  // automatically resizes as necessary
printf("%d\n", a.array[9]);  // print 10th element
printf("%d\n", a.used);  // print number of elements
freeArray(&a);

回答by Wolph

There are a couple of options I can think of.

我能想到几个选项。

1. Linked List. You can use a linked list to make a dynamically growing array like thing. But you won't be able to do array[100]without having to walk through 1-99first. And it might not be that handy for you to use either.
2. Large array. Simply create an array with more than enough space for everything
3. Resizing array. Recreate the array once you know the size and/or create a new array every time you run out of space with some margin and copy all the data to the new array.
4. Linked List Array combination. Simply use an array with a fixed size and once you run out of space, create a new array and link to that (it would be wise to keep track of the array and the link to the next array in a struct).

1. 链接列表。您可以使用链表来制作动态增长的数组之类的东西。但是，如果您不先array[100]走过，您将无法做到1-99。而且您使用它可能也不是那么方便。
2. 大阵。只需创建一个具有足够空间容纳所有内容的数组
3. 调整数组大小。一旦知道大小和/或每次用完空间时创建一个新数组并保留一些边距，然后重新创建数组并将所有数据复制到新数组中。
4. 链表数组组合。只需使用一个固定大小的数组，一旦空间用完，创建一个新数组并链接到该数组（最好跟踪该数组以及指向结构中下一个数组的链接）。

It is hard to say what option would be best in your situation. Simply creating a large array is ofcourse one of the easiest solutions and shouldn't give you much problems unless it's really large.

很难说哪种选择最适合您的情况。简单地创建一个大数组当然是最简单的解决方案之一，除非它真的很大，否则不会给您带来太多问题。

回答by autistic

As with everything that seems scarier at first than it was later, the best way to get over the initial fear is to immerse yourself into the discomfort of the unknown! It is at times like that which we learn the most, after all.

就像一开始看起来比后来更可怕的事情一样，克服最初恐惧的最好方法是让自己沉浸在未知的不适中！毕竟，有时我们学到的东西最多。

Unfortunately, there are limitations. While you're still learning to use a function, you shouldn't assume the role of a teacher, for example. I often read answers from those who seemingly don't know how to use realloc(i.e. the currently accepted answer!) telling others how to use it incorrectly, occasionally under the guise that they've omitted error handling, even though this is a common pitfall which needs mention. Here's an answer explaining how to use realloccorrectly. Take note that the answer is storing the return value into a differentvariable in order to perform error checking.

不幸的是，有一些限制。例如，当您仍在学习使用函数时，您不应承担教师的角色。我经常阅读那些看似不知道如何使用的人的答案realloc（即当前接受的答案！）告诉其他人如何错误地使用它，偶尔以他们省略错误处理为幌子，即使这是一个常见的陷阱这需要提及。这是解释如何realloc正确使用的答案。请注意，答案是将返回值存储到不同的变量中以执行错误检查。

Every time you call a function, and every time you use an array, you are using a pointer. The conversions are occurring implicitly, which if anything should be even scarier, as it's the things we don't see which often cause the most problems. For example, memory leaks...

每次调用函数时，每次使用数组时，都是在使用指针。转换是隐式发生的，如果有的话应该更可怕，因为它是我们看不到的东西，通常会导致最多的问题。比如内存泄漏...

Array operators are pointer operators. array[x]is really a shortcut for *(array + x), which can be broken down into: *and (array + x). It's most likely that the *is what confuses you. We can further eliminate the addition from the problem by assuming xto be 0, thus, array[0]becomes *arraybecause adding 0won't change the value...

数组运算符是指针运算符。array[x]确实是 的快捷方式*(array + x)，可以分解为：*和(array + x)。这很可能*是让您感到困惑的原因。我们可以通过假设x为 来进一步消除问题中的加法0，因此，array[0]变成*array是因为加法0不会改变值......

... and thus we can see that *arrayis equivalent to array[0]. You can use one where you want to use the other, and vice versa. Array operators are pointer operators.

......因此我们可以看到它*array等价于array[0]。您可以在想要使用另一个的地方使用一个，反之亦然。数组运算符是指针运算符。

malloc, reallocand friends don't inventthe concept of a pointer which you've been using all along; they merely usethis to implement some other feature, which is a different form of storage duration, most suitable when you desire drastic, dynamic changes in size.

malloc,realloc朋友们不会发明你一直在使用的指针的概念；他们只是使用它来实现一些其他功能，这是一种不同形式的存储持续时间，最适合当您希望大小发生剧烈的动态变化时。

It is a shame that the currently accepted answer alsogoes against the grain of some other very well-founded advice on StackOverflow, and at the same time, misses an opportunity to introduce a little-known feature which shines for exactly this usecase: flexible array members! That's actually a pretty brokenanswer... :(

遗憾的是，当前接受的答案也与StackOverflow 上其他一些非常有根据的建议背道而驰，同时，错过了介绍一个鲜为人知的功能的机会，该功能正是这个用例的亮点：灵活数组会员！这实际上是一个非常糟糕的答案...... :(

When you define your struct, declare your array at the endof the structure, without any upper bound. For example:

当你定义你的struct，在结构的末尾声明你的数组，没有任何上限。例如：

struct int_list {
    size_t size;
    int value[];
};

This will allow you to unite your array of intinto the same allocation as your count, and having them bound like this can be very handy!

这将允许您将您的数组int合并到与您相同的分配中count，并且像这样绑定它们会非常方便！

sizeof (struct int_list)will act as though valuehas a size of 0, so it'll tell you the size of the structure with an empty list. You still need to add to the size passed to reallocto specify the size of your list.

sizeof (struct int_list)就像value大小为 0 一样，所以它会用空列表告诉您结构的大小。您仍然需要添加到传递给realloc的大小以指定列表的大小。

Another handy tip is to remember that realloc(NULL, x)is equivalent to malloc(x), and we can use this to simplify our code. For example:

另一个方便的提示是记住它realloc(NULL, x)等价于malloc(x)，我们可以使用它来简化我们的代码。例如：

int push_back(struct int_list **fubar, int value) {
    size_t x = *fubar ? fubar[0]->size : 0
         , y = x + 1;

    if ((x & y) == 0) {
        void *temp = realloc(*fubar, sizeof **fubar
                                   + (x + y) * sizeof fubar[0]->value[0]);
        if (!temp) { return 1; }
        *fubar = temp; // or, if you like, `fubar[0] = temp;`
    }

    fubar[0]->value[x] = value;
    fubar[0]->size = y;
    return 0;
}

struct int_list *array = NULL;

The reason I chose to use struct int_list **as the first argument may not seem immediately obvious, but if you think about the second argument, any changes made to valuefrom within push_backwould not be visible to the function we're calling from, right? The same goes for the first argument, and we need to be able to modify our array, not just herebut possibly also in any other function/s we pass it to...

我选择struct int_list **用作第一个参数的原因可能看起来并不明显，但是如果您考虑第二个参数，value从内部所做的任何更改对push_back我们调用的函数都是不可见的，对吧？第一个参数也是如此，我们需要能够修改我们的array，不仅在这里，而且可能在我们将它传递给的任何其他函数中...

arraystarts off pointing at nothing; it is an empty list. Initialisingit is the same as adding to it. For example:

array一开始什么也没有；它是一个空列表。初始化它与添加它相同。例如：

struct int_list *array = NULL;
if (!push_back(&array, 42)) {
    // success!
}

P.S. Remember to free(array);when you're done with it!

PS 完成后请记住free(array);！

回答by autistic

Building on Matteo Furlansdesign, when he said "most dynamic array implementations work by starting off with an array of some (small) default size, then whenever you run out of space when adding a new element, double the size of the array". The difference in the "work in progress" below is that it doesn't double in size, it aims at using only what is required. I have also omitted safety checks for simplicity...Also building on brimboriumsidea, I have tried to add a delete function to the code...

基于Matteo Furlans 的设计，当他说“大多数动态数组实现都是从一些（小）默认大小的数组开始工作的，然后每当添加新元素时空间不足时，就将数组的大小加倍”。下面“进行中的工作”的不同之处在于它的大小不会翻倍，它旨在仅使用所需的内容。为简单起见，我还省略了安全检查……也是基于brimboriums 的想法，我尝试在代码中添加删除功能……

The storage.h file looks like this...

storage.h 文件看起来像这样......

#ifndef STORAGE_H
#define STORAGE_H

#ifdef __cplusplus
extern "C" {
#endif

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

    void Array_Init(Array *array);
    void Array_Add(Array *array, int item);
    void Array_Delete(Array *array, int index);
    void Array_Free(Array *array);

#ifdef __cplusplus
}
#endif

#endif /* STORAGE_H */

The storage.c file looks like this...

storage.c 文件看起来像这样......

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

/* Initialise an empty array */
void Array_Init(Array *array) 
{
    int *int_pointer;

    int_pointer = (int *)malloc(sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to allocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
        array->size = 0;
    }
}

/* Dynamically add to end of an array */
void Array_Add(Array *array, int item) 
{
    int *int_pointer;

    array->size += 1;

    int_pointer = (int *)realloc(array->array, array->size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer;
        array->array[array->size-1] = item;
    }
}

/* Delete from a dynamic array */
void Array_Delete(Array *array, int index) 
{
    int i;
    Array temp;
    int *int_pointer;

    Array_Init(&temp);

    for(i=index; i<array->size; i++)
    {
        array->array[i] = array->array[i + 1];
    }

    array->size -= 1;

    for (i = 0; i < array->size; i++)
    {
        Array_Add(&temp, array->array[i]);
    }

    int_pointer = (int *)realloc(temp.array, temp.size * sizeof(int));

    if (int_pointer == NULL)
    {       
        printf("Unable to reallocate memory, exiting.\n");
        free(int_pointer);
        exit(0);
    }
    else
    {
        array->array = int_pointer; 
    } 
}

/* Free an array */
void Array_Free(Array *array) 
{
  free(array->array);
  array->array = NULL;
  array->size = 0;  
}

The main.c looks like this...

main.c 看起来像这样......

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

int main(int argc, char** argv) 
{
    Array pointers;
    int i;

    Array_Init(&pointers);

    for (i = 0; i < 60; i++)
    {
        Array_Add(&pointers, i);        
    }

    Array_Delete(&pointers, 3);

    Array_Delete(&pointers, 6);

    Array_Delete(&pointers, 30);

    for (i = 0; i < pointers.size; i++)
    {        
        printf("Value: %d Size:%d \n", pointers.array[i], pointers.size);
    }

    Array_Free(&pointers);

    return (EXIT_SUCCESS);
}

Look forward to the constructive criticismto follow...

期待后续的建设性批评...

回答by Lie Ryan

When you're saying

当你说

make an array holding an index number (int) of an indeterminate number of entities

制作一个包含不确定数量实体的索引号 (int) 的数组

you're basically saying you're using "pointers", but one which is a array-wide local pointer instead of memory-wide pointer. Since you're conceptually already using "pointers" (i.e. id numbers that refers to an element in an array), why don't you just use regular pointers (i.e. id numbers that refers to an element in the biggest array: the whole memory).

您基本上是在说您正在使用“指针”，但它是一个数组范围的本地指针，而不是内存范围的指针。由于您在概念上已经在使用“指针”（即指代数组中元素的 id 号），为什么不只使用常规指针（即指代最大数组中元素的 id 号：整个内存）。

Instead of your objects storing a resource id numbers, you can make them store a pointer instead. Basically the same thing, but much more efficient since we avoid turning "array + index" into a "pointer".

您可以让对象存储一个指针，而不是存储资源 ID 号的对象。基本上是一样的，但效率更高，因为我们避免将“数组+索引”变成“指针”。

Pointers are not scary if you think of them as array index for the whole memory (which is what they actually are)

如果您将指针视为整个内存的数组索引（实际上是它们），则指针并不可怕

回答by Sebastian Karlsson

To create an array of unlimited items of any sort of type:

要创建任何类型的无限项的数组：

typedef struct STRUCT_SS_VECTOR {
    size_t size;
    void** items;
} ss_vector;


ss_vector* ss_init_vector(size_t item_size) {
    ss_vector* vector;
    vector = malloc(sizeof(ss_vector));
    vector->size = 0;
    vector->items = calloc(0, item_size);

    return vector;
}

void ss_vector_append(ss_vector* vec, void* item) {
    vec->size++;
    vec->items = realloc(vec->items, vec->size * sizeof(item));
    vec->items[vec->size - 1] = item;
};

void ss_vector_free(ss_vector* vec) {
    for (int i = 0; i < vec->size; i++)
        free(vec->items[i]);

    free(vec->items);
    free(vec);
}

and how to use it:

以及如何使用它：

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT {
    int id;
} apple;

apple* init_apple(int id) {
    apple* a;
    a = malloc(sizeof(apple));
    a-> id = id;
    return a;
};


int main(int argc, char* argv[]) {
    ss_vector* vector = ss_init_vector(sizeof(apple));

    // inserting some items
    for (int i = 0; i < 10; i++)
        ss_vector_append(vector, init_apple(i));


    // dont forget to free it
    ss_vector_free(vector);

    return 0;
}

This vector/array can hold any type of item and it is completely dynamic in size.

这个向量/数组可以容纳任何类型的项目，并且它的大小是完全动态的。

回答by JOSMAR BARBOSA - M4NOV3Y

Well, I guess if you need to remove an element you will make a copy of the array despising the element to be excluded.

好吧，我想如果您需要删除一个元素，您将制作一个数组副本，鄙视要排除的元素。

// inserting some items
void* element_2_remove = getElement2BRemove();

for (int i = 0; i < vector->size; i++){
       if(vector[i]!=element_2_remove) copy2TempVector(vector[i]);
       }

free(vector->items);
free(vector);
fillFromTempVector(vector);
//

Assume that getElement2BRemove(), copy2TempVector( void* ...)and fillFromTempVector(...)are auxiliary methods to handle the temp vector.

假设getElement2BRemove()、copy2TempVector( void* ...)和fillFromTempVector(...)是处理临时向量的辅助方法。