C dynamically growing array
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...
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.
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).
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?
3 ответа
Я могу использовать указатели, но я немного боюсь их использовать.
Если вам нужен динамический массив, вы не можете обойтись без указателей. Но почему вы боитесь? Они не кусаются (пока вы осторожны, то есть). В 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);
Я могу придумать несколько вариантов.
- Связанный список. Вы можете использовать связанный список, чтобы создать динамически растущий массив, как вещь. Но вы не сможете выполнить
array [100], не пройдя сначала через1-99. И вам тоже может быть не так удобно. - Большой массив. Просто создайте массив с более чем достаточным пространством для всего
- Изменение размера массива. Повторно создайте массив, как только вы узнаете размер, и / или создавайте новый массив каждый раз, когда у вас заканчивается пространство с некоторым запасом, и копируйте все данные в новый массив.
- Комбинация массивов связанных списков. Просто используйте массив фиксированного размера, и как только у вас закончится место, создайте новый массив и сделайте ссылку на него (было бы разумно отслеживать массив и ссылку на следующий массив в структуре).
Трудно сказать, какой вариант лучше всего подходит в вашей ситуации. Простое создание большого массива - это, конечно, одно из самых простых решений и не должно доставить вам особых проблем, если только он не будет действительно большим.
Когда вы говорите
создать массив, содержащий номер индекса (int) неопределенного количества сущностей
, вы в основном говорите, что используете «указатели», но тот, который является локальным указателем всего массива вместо указателя всей памяти. Поскольку вы концептуально уже используете «указатели» (т.е. номера идентификаторов, которые относятся к элементу в массиве), почему бы вам просто не использовать обычные указатели (например, номера идентификаторов, которые относятся к элементу в самом большом массиве: вся память ).
Вместо того, чтобы ваши объекты сохраняли номера идентификаторов ресурсов, вы можете заставить их хранить указатель. В основном то же самое, но гораздо более эффективно, поскольку мы избегаем превращения «массив + индекс» в «указатель».
Указатели не страшны, если вы думаете о них как о индексе массива для всей памяти (что они и есть на самом деле)