C Динамически растущий массив
-
30-09-2019 - |
Вопрос
У меня есть программа, которая читает «сырой» список внутриигровых объектов, и я намерен сделать массив, удерживающий номер индекса (INT) неопределенного количества объектов, для обработки различных вещей. Я хотел бы избежать слишком много памяти или процессора для хранения таких индексов ...
Быстро и грязное решение, которое я использую до сих пор, - это объявить, в основной функции обработки (локальный фокус) массив с размером максимальных игровых объектов, а другое целое число для отслеживания того, сколько было добавлено в список. Это не удовлетворительное, так как каждый список удерживает 3000+ массивов, что не так уж много, но чувствует себя как отходы, поскольку смогу использовать решение для 6-7 списков для различных функций.
Я не нашел никаких C (не C ++ или C #) конкретных решений для достижения этого. Я могу использовать указатели, но я немного боюсь использовать их (если только это не единственный возможный путь).
Массивы не оставляют локальной функции (они должны быть переданы на функцию, затем отброшены), в случае, если меняет вещи.
Если указатели являются единственным решением, как я могу отследить их, чтобы избежать утечек?
Решение
Я могу использовать указатели, но я немного боюсь использовать их.
Если вам нужен динамический массив, вы не можете избежать указателей. Почему ты боишься, хотя? Они не будут кусать (до тех пор, пока вы осторожны, то есть). В C нет встроенного динамического массива в 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
первый. И это может быть не удобно для вас, чтобы использовать. - Большой массив. Просто создайте массив с более чем достаточным пространством для всего
- Изменение размера массива. Воссоздайте массив, как только вы знаете размер и / или создаете новый массив каждый раз, когда вы запускаете пространство с небольшим количеством запасов и скопируйте все данные в новый массив.
- Связанный список массива. Просто используйте массив с фиксированным размером и, как только вы запускаете выход из пробела, создайте новый массив и ссылку на это (это будет разумно отслеживать массив и ссылку на следующий массив в структуре).
Трудно сказать, какой вариант будет лучшим в вашей ситуации. Просто создание большого массива предназначено для одного из самых простых решений и не должно давать вам больших проблем, если только это действительно большая.
Как и во всем, что вначале кажется пугающим, чем позже, лучший способ преодолеть начальный страх погрузитесь в дискомфорт неизвестногоДействительно В конце концов, это то, что мы узнаем больше всего, в конце концов.
К сожалению, есть ограничения. Пока вы все еще учитесь использовать функцию, вы не должны взять на себя роль учителя, например. Я часто читаю ответы от тех, кто, казалось бы, не знает, как использовать realloc
(то есть В настоящее время принятый ответ!) рассказывать другим, как использовать его неправильно, иногда под видом, который они Пропущенная обработка ошибок, Несмотря на то, что это распространенная ловушка, которая нуждается в упоминании. Вот ответ, объясняющий, как использовать realloc
правильно. Обратите внимание, что ответ хранит возвращаемое значение в разные переменная для выполнения проверки ошибок.
Каждый раз, когда вы вызываете функцию, и каждый раз, когда вы используете массив, вы используете указатель. Конверсии происходят неявно, что, если что-то должно быть даже пугающим, так как это то, что мы не видим, что часто вызывают большинство проблем. Например, утечки памяти ...
Операторы массива являются операторами указателя. array[x]
действительно ярлык для *(array + x)
, который можно разбиться в: *
а также (array + x)
. Отказ Скорее всего, что *
это то, что смущает вас. Мы можем дополнительно устранить дополнение к проблеме, предполагая x
быть 0
, таким образом, array[0]
становится *array
Потому что добавление 0
не изменит ценность ...
... и, таким образом, мы можем видеть это *array
эквивалентно array[0]
. Отказ Вы можете использовать один, где вы хотите использовать другой, и наоборот. Операторы массива являются операторами указателя.
malloc
, realloc
И друзья не изобретать концепция указателя, которую вы использовали все вместе; они просто использовать Это для реализации какой-либо другой функции, которая является другой формой продолжительности хранения, наиболее подходящие при желании радикальные, динамические изменения в размере.
Это позор, что в настоящее время принятый ответ также идет против зерна Некоторые другие очень обоснованные советы по стоковым потокам, И в то же время пропускает возможность ввести немного известную функцию, которая сияет для именно этой упрецеляции: гибкие члены массива! Это на самом деле довольно сломанный отвечать... :(
Когда вы определяете свой 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);
Когда вы закончите с этим!
Когда вы говорите
Сделайте массив, удерживающий номер индекса (INT) неопределенного количества объектов
Вы в основном говорите, что вы используете «указатели», но тот, который представляет собой локальный указатель, широкий на массиве вместо Picketer-Picketer. Поскольку вы уже концептуально используете «указатели» (т.е. идентификационные номера, которые ссылаются на элемент в массиве), почему бы вам не просто использовать обычные указатели (т.е. номера IT, которые ссылаются на элемент в самом большом массиве: всю память ).
Вместо ваших объектов хранят номера идентификаторов ресурсов, вы можете заставить их хранить указатель вместо этого. В основном то же самое, но гораздо более эффективно, так как мы избегаем поворота «индекса массива +» в «указатель».
Указатели не страшно, если вы думаете о них как о них как индекс массива для всей памяти (который на самом деле они на самом деле)
Строительство Маттео Фурланс дизайн, когда он сказал: «Наиболее динамические реализации массива работают с начала с массивом некоторых (маленьких) размера по умолчанию, затем всякий раз, когда у вас заканчивается пространство при добавлении нового элемента, удвоить размер массива". Разница в"работа в процессе«Ниже приведено в том, что он не удвоил в размере, он направлен на использование только то, что требуется. У меня также пропущены проверки безопасности для простоты ... Также здание на Бримбони Идея, я пытался добавить функцию удаления в код ...
Хранилище .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 */
Файл comaste.chost выглядит так ...
#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);
}
С нетерпением ждем конструктивная критика следовать...
Чтобы создать массив неограниченных элементов любого типа:
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);
}
И как его использовать:
// 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;
}
Этот вектор / массив может удерживать любой тип элемента, и он полностью динамичен по размеру.
Ну, я думаю, если вам нужно удалить элемент, вы сделаете копию массива, презиратив элемент, который будет исключен.
// 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);
//
Предположим, что getElement2BRemove()
, copy2TempVector( void* ...)
а также fillFromTempVector(...)
являются вспомогательными методами для обработки вектора TEMP.