C Динамически растущий массив

https://stackoverflow.com/questions/3536153

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.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow