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

Answer 2

我能想到几个选项.

1. 链接列表.您可以使用链接列表来制作动态增长的数组.但你不会是能够做到array[100],而不必通过走1-99第一.你可能也不方便使用它们.
2. 大阵列.只需创建一个具有足够空间的数组即可
3. 调整数组大小.知道大小后重新创建数组和/或每次空间用尽时创建一个新数组,并将所有数据复制到新数组.
4. 链接列表数组组合.只需使用具有固定大小的数组,一旦空间不足,创建一个新数组并链接到该数组(跟踪数组和结构中下一个数组的链接是明智的).

在你的情况下很难说哪种选择最好.简单地创建一个大型阵列是最简单的解决方案之一,除非它真的很大,否则不应该给你带来太多问题.

Answer 3

就像最初看起来比以后更加可怕的一切一样,克服最初恐惧的最好方法就是让自己沉浸在未知的不适之中!毕竟,有时我们学到的最多.

不幸的是,存在局限性.当你还在学习使用某个功能时,你不应该担任教师的角色.我经常阅读那些看似不知道如何使用的答案realloc(即目前接受的答案!)告诉别人如何错误地使用它,偶尔以他们省略错误处理为幌子,即使这是一个常见的陷阱需要提一下.这是一个解释如何realloc正确使用的答案.请注意,答案是将返回值存储到另一个变量中以执行错误检查.

每次调用函数时,每次使用数组时,都使用指针.转换是隐含的,如果有什么事情应该更加可怕,那就是我们看不到的事情往往会导致最多的问题.例如,内存泄漏......

数组运算符是指针运算符.array[x]真的是一个捷径*(array + x),可以分解为:*和(array + x).这很可能*会让你感到困惑.我们可以进一步消除假设从问题除了x要0,因此,array[0]变成*array因为添加0不会改变的价值...

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

malloc,realloc和朋友不要编造你已经使用了所有沿指针的概念; 他们只是用它来实现一些其他功能,这是一种不同形式的存储持续时间,最适合您需要大小的动态变化.

令人遗憾的是,目前接受的答案也与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 **第一个参数的原因似乎并不是很明显,但是如果你考虑第二个参数,那么value从内部进行的任何更改push_back都不会对我们调用的函数可见,对吧？对于第一个参数也是如此,我们需要能够修改我们的array,不仅仅是在这里,但也可能在我们传递给它的任何其他函数中 ...

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

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

PS 请记住,free(array);当你完成它!

Answer 4

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

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 */

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

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

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