C动态增长数组

Question

我有一个读取游戏中实体的“原始”列表的程序，我打算创建一个数组，其中包含不确定数量的实体的索引号(int)，用于处理各种事情。我希望避免使用太多的内存或CPU来保存这样的索引……

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

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

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

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

Answer 1

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

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

如果您确实计划编写自己的数组，可以从以下内容开始:大多数动态数组实现都是从一些(小)默认大小的数组开始的，然后每当您在添加新元素时耗尽空间时，将数组的大小增加一倍。正如您在下面的示例中所看到的，这并不是非常困难：(为了简洁，我省略了安全检查)

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

void initArray(Array *a, size_t initialSize) {
  a->array = 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 = 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;
}

使用它也很简单：

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

Answer 2

一个简单的解决方案涉及mmap。如果您可以容忍POSIX解决方案，这将是非常好的。只需映射整个页面并防止溢出，因为对于这样的值，realloc无论如何都会失败。现代OSes在您使用它之前不会提交所有内容，如果需要，您可以截断文件。

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

不幸的是，这是有局限性的。例如，当你还在学习使用函数时，你不应该承担教师的角色。我经常从那些似乎不知道如何使用realloc的人那里读到答案(也就是目前公认的答案！)告诉别人如何不正确地使用它，偶尔会以他们忽略了错误处理为借口，即使这是一个需要提及的常见陷阱。Here's an answer explaining how to use realloc correctly。请注意，答案是将返回值存储到 different 变量中，以便执行错误检查。

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

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

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

malloc，realloc和朋友并没有发明你一直在使用的指针的概念；他们只是用它来实现一些其他功能，这是一种不同形式的存储持续时间，最适合当你想要急剧的，动态的大小变化时。

遗憾的是，目前被接受的答案也与some other very well-founded advice on StackOverflow的思路背道而驰，同时，错过了引入一个鲜为人知的特性的机会，这个特性正是为这个用例而闪耀的:灵活的数组成员！这实际上是一个相当支离破碎的答案。:(

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

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

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

sizeof (struct int_list)将表现为value的大小为0，因此它将通过一个空列表告诉您结构的大小。您仍然需要添加传递给realloc的大小，以指定列表的大小。

另一个方便的技巧是记住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;

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

array一开始没有指向任何东西；它是一个空列表。初始化它和添加它是一样的。例如：

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

附言:当你用完free(array);的时候，记得要它！

Answer 3

我能想到几个选择。

1. 链表。你可以使用链表来创建一个动态增长的类似数组的东西。但是，如果不先遍历1-99，您将无法执行array[100]。对于你来说，使用.
2. 大型数组可能也不太方便。只需创建一个具有足够everything
3. Resizing数组空间的数组。知道大小后重新创建数组和/或每次空间不足时创建一个新数组，并将所有数据复制到新数组中。
4. 链接列表数组组合。只需使用具有固定大小的数组，一旦空间耗尽，就创建一个新数组并链接到该数组(明智的做法是跟踪该数组以及结构中指向下一个数组的链接)。

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