Cdynamic增长数组

我有一个程序,读取一个“原始”游戏中的实体列表,我打算做一个数组持有不确定数量的实体的索引号(int),以处理各种事情。 我想避免使用太多的内存或CPU来保持这样的指标…

到目前为止,我使用的一个快速和肮脏的解决scheme是在主处理函数(本地焦点)中声明最大游戏实体大小的数组,以及另一个整数来跟踪已添加到列表中的数量。 这并不令人满意,因为每个列表都包含3000个以上的数组,但并不是那么多,但是感觉像是一种浪费,因为我可以使用6-7列表来实现不同的function。

我还没有find任何C(而不是C ++或C#)特定的解决scheme来实现这一点。 我可以使用指针,但我有点害怕使用它们(除非是唯一可能的方式)。

数组不会离开本地函数作用域(它们将被传递给一个函数,然后丢弃),以防万一。

如果指针是唯一的解决scheme,我如何跟踪它们以避免泄漏?

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

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

如果你打算自己写,你可以从这里开始:大多数dynamic数组的实现都是以一个(小)默认大小的数组开始工作,然后当你添加一个新的元素时,数组的大小。 正如你在下面的例子中看到的那样,这并不是很困难:(为了简洁起见我省略了安全检查)

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

使用它也同样简单:

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

有几个选项我可以想到。

  1. 链接列表。 你可以使用链表来创build一个dynamic增长的数组。 但是如果不经过1-99你将无法做array[100] 。 也可能不太适合你使用。
  2. 大阵。 只需创build一个具有足够空间的数组
  3. 调整数组的大小。 一旦知道尺寸就重新创build数组,并且/或者每次用完空白后创build一个新数组,并将所有数据复制到新数组中。
  4. 链接列表数组组合。 只需使用一个固定大小的数组,一旦空间不足,创build一个新的数组并连接到这个数组(跟踪数组和链接到结构中下一个数组将是明智的)。

很难说在你的情况下最好的select是什么。 简单地创build一个大arrays是当然最简单的解决scheme之一,除非它真的很大,否则不应该给你带来太多的问题。

当你说

创build一个拥有不确定数量实体的索引号(int)的数组

你基本上说你正在使用“指针”,而是一个数组范围内的本地指针,而不是内存范围的指针。 既然你在概念上已经使用了“指针”(即引用数组中的一个元素的id号),为什么不使用常规的指针(即指向最大数组中元素的id号:整个内存)。

而不是你的对象存储一个资源ID号码,你可以让他们存储一个指针,而不是。 基本上是同样的事情,但是由于我们避免将“数组+索引”变成“指针”,效率更高。

如果你把它们看作整个内存的数组索引(这就是它们的实际情况)

就像所有一开始似乎比以前更加恐怖的事情一样,克服初始恐惧的最好方法就是让自己沉浸在未知的不适中 ! 毕竟,它有时就像我们最了解的东西。

不幸的是,有一些限制。 当你还在学习使用一个函数的时候,例如,你不应该假设一个老师的angular色。 我经常从那些看似不知道如何使用realloc (即目前被接受的答案 )的人那里听到答案,告诉别人错误地使用它,偶尔也会忽略error handling ,尽pipe这是一个常见的错误需要提及的陷阱。 这是一个解释如何正确使用realloc的答案 。 请注意,答案是将返回值存储到一个不同的variables,以执行错误检查。

每次你调用一个函数,每次你使用一个数组,你都在使用一个指针。 这种转变正在隐含地发生,如果有什么更应该是更加可怕的,因为这是我们看不到的东西,这往往造成最多的问题。 例如,内存泄漏…

数组运算符是指针运算符。 array[x]实际上是*(array + x)的快捷方式,可以分解为: *(array + x) 。 这很可能是*让你感到困惑。 我们可以通过假设x0来进一步消除这个问题,因此, array[0]变成*array因为加0不会改变值…

…因此我们可以看到*array相当于array[0] 。 你可以使用一个你想使用另一个,反之亦然。 数组运算符是指针运算符。

mallocrealloc和朋友不会发明你一直使用的指针的概念; 他们只是它来实现一些其他的function,这是一种不同的存储时间forms,最适合当你想要大幅度,dynamic变化的大小

可惜的是,目前公认的答案与StackOverflow上一些其他非常有根据的build议不符 ,同时也错过了一个机会来介绍一个鲜为人知的特性,这个特性正好闪耀着这个用例:灵活的数组会员! 这实际上是一个相当破碎的答案… 🙁

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

 struct int_list { size_t count; 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]->count = y; return 0; } struct int_list *array = NULL; 

我select使用struct int_list **作为第一个参数的原因可能看起来并不明显,但是如果您考虑第二个参数,那么在push_backvalue任何更改都不会对我们调用的函数可见,对? 第一个参数也是一样的,我们需要能够修改我们的array ,而不仅仅是在这里,也可能在我们传递给它的任何其他函数中

array开始指向什么都没有; 这是一个空的列表。 初始化与添加它相同。 例如:

 if (!push_back(&array, 42)) { // success! }