С динамически растущим массивом - PullRequest
116 голосов
/ 21 августа 2010

У меня есть программа, которая читает «сырой» список игровых сущностей, и я намереваюсь создать массив, содержащий индексное число (int) неопределенного числа сущностей, для обработки различных вещей. Я бы хотел не использовать слишком много памяти или процессора для хранения таких индексов ...

Быстрое и грязное решение, которое я использую до сих пор, состоит в том, чтобы объявить в основной функции обработки (локальный фокус) массив с размером максимального количества игровых объектов и другое целое число для отслеживания того, сколько было добавлено к список. Это неудовлетворительно, так как каждый список содержит более 3000 массивов, что не так уж и много, но выглядит как пустая трата, поскольку я могу использовать решение для 6-7 списков для различных функций.

Я не нашел никаких конкретных решений для C (не C ++ или C #) для достижения этой цели. Я могу использовать указатели, но я немного боюсь их использовать (если это не единственный возможный способ).

Массивы не покидают область действия локальной функции (они должны быть переданы в функцию, а затем отброшены), если это что-то меняет.

Если указатели являются единственным решением, как я могу отслеживать их, чтобы избежать утечек?

Ответы [ 7 ]

187 голосов
/ 21 августа 2010

Я могу использовать указатели, но я немного боюсь их использовать.

Если вам нужен динамический массив, вы не можете экранировать указатели. Почему ты боишься, хотя? Они не будут кусаться (пока вы осторожны). В 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);
10 голосов
/ 21 августа 2010

Я могу придумать несколько вариантов.

  1. Связанный список.Вы можете использовать связанный список, чтобы создать динамически растущий массив.Но вы не сможете сделать array[100], не пройдя сначала 1-99.И это может быть не очень удобно для вас.
  2. Большой массив.Просто создайте массив с более чем достаточно места для всего
  3. Изменение размера массива.Создайте заново массив, как только вы узнаете размер, и / или создайте новый массив каждый раз, когда у вас заканчивается свободное пространство с некоторым запасом, и скопируйте все данные в новый массив.
  4. Комбинация из массива связанного списка.Просто используйте массив с фиксированным размером и, как только вы исчерпаете пространство, создайте новый массив и создайте ссылку на него (было бы целесообразно отслеживать массив и ссылку на следующий массив в структуре).

Трудно сказать, какой вариант будет лучшим в вашей ситуации.Простое создание большого массива - одно из самых простых решений, и оно не должно вызывать особых проблем, если только оно не очень большое.

8 голосов
/ 21 сентября 2017

Как и во всем, что поначалу кажется страшнее, чем было позже, лучший способ преодолеть первоначальный страх - это погрузиться в дискомфорт неизвестного !В конце концов, именно такие моменты мы изучаем больше всего.

К сожалению, существуют ограничения.Хотя вы все еще учитесь использовать функцию, вы не должны брать на себя роль учителя, например.Я часто читаю ответы от тех, кто, по-видимому, не знает, как использовать 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);, когда закончите с этим!

2 голосов
/ 09 декабря 2018

Опираясь на дизайн Маттео Фурлана , когда он сказал: " большинство реализаций динамического массива работают, начиная с массива некоторого (небольшого) размера по умолчанию, а затем всякий раз, когда при добавлении пространства у вас заканчивается новый элемент, удвоенный размер массива". Разница в « незавершенном производстве » ниже заключается в том, что он не удваивается по размеру, а направлен на использование только того, что требуется. Я также пропустил проверки безопасности для простоты ... Кроме того, основываясь на идее 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);
}

С нетерпением ждем конструктивной критики , которая последует ...

2 голосов
/ 21 августа 2010

Когда вы говорите

сделать массив, содержащий порядковый номер (int) неопределенного числа сущностей

Вы в основном говорите, что используете "указатели", но тот, который является локальным указателем на весь массив вместо указателя на всю память. Поскольку вы концептуально уже используете «указатели» (т. Е. Числа идентификаторов, которые относятся к элементу в массиве), почему бы вам не использовать обычные указатели (то есть числа идентификаторов, которые относятся к элементу в самом большом массиве: всей памяти ).

Вместо того, чтобы ваши объекты хранили номера идентификаторов ресурсов, вы можете вместо них хранить указатель. По сути, это то же самое, но гораздо эффективнее, поскольку мы избегаем превращения «массива + индекса» в «указатель».

Указатели не страшны, если вы думаете о них как о индексе массива для всей памяти (что они и есть на самом деле)

0 голосов
/ 27 ноября 2018

Ну, я думаю, если вам нужно удалить элемент, вы сделаете копию массива, презирающего элемент, который будет исключен.

// 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(...) являются вспомогательными методами для обработки временного вектора.

0 голосов
/ 18 ноября 2018

Чтобы создать массив неограниченных элементов любого типа:

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

Этот вектор / массив может содержать элементы любого типаи он полностью динамический по размеру.

...