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

126

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

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

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

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

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

Балкания
источник
1
Это (очень, очень маленькая) проблема в C, но как вы пропустили все решения C ++ и C # для этого?
Игнасио Васкес-Абрамс,
11
«Если указатели - единственное решение, как я могу отслеживать их, чтобы избежать утечек?» Забота, внимание и вальгринд. Именно поэтому люди так боятся, в первую очередь, C.
Крис Лутц,
27
Вы не можете эффективно использовать C без указателей. Не бойся.
qrdl
без больших библиотек только одна функция для всех, а также для структур, например: stackoverflow.com/questions/3456446/…
user411313
6
Использование C без указателей похоже на использование автомобиля без топлива.
martinkunev 02

Ответы:

211

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

Если вам нужен динамический массив, вы не можете избежать указателей. А чего ты боишься? Они не будут кусаться (если вы будете осторожны). В 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 = 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 = 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);
Касабланка
источник
1
Спасибо за образец кода. Я реализовал конкретную функцию, используя большой массив, но буду реализовывать другие аналогичные вещи, используя это, и после того, как я получу ее под контролем, верну остальные :)
Балкания,
2
Большое спасибо за код. removeArrayМетод , который позволяет избавиться от последнего элемента также будет аккуратным. Если вы позволите, я добавлю это в ваш образец кода.
brimborium
5
% d и size_t ... немного нет-нет. Если вы используете C99 или более позднюю версию, можете воспользоваться добавлением% z
Рэнди Ховард,
13
Никогда не пропускайте проверки безопасности с выделением и перераспределением памяти.
Alex Reynolds
3
Это компромисс производительности. Если вы каждый раз удваиваете, то накладные расходы иногда составляют 100%, а в среднем - 50%. 3/2 дает 50% худшего и 25% типичного. Он также близок к эффективному основанию последовательности Фибоначчи в пределе (фи), который часто хвалят и используют за его «экспоненциальные, но гораздо менее жесткие, чем характеристики с основанием 2», но которые легче вычислить. +8 означает, что достаточно маленькие массивы не делают слишком много копий. Он добавляет мультипликативный член, позволяющий массиву быстро расти, если его размер не имеет значения. В специализированном использовании это должно настраиваться.
Дэн Шеппард
11

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

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

аутистический
источник
" array[x]это действительно ярлык для *(array + x), [...]" Вы уверены в этом ???? См. Описание их различного поведения: eli.thegreenplace.net/2009/10/21/… .
C-Star-W-Star
1
Увы, @ C-Star-Puppy, единственная ссылка, которую ваш ресурс, похоже, вообще не упоминает, - это стандарт C. Это спецификация, которой должны придерживаться ваши компиляторы, чтобы юридически называть себя компиляторами C. Ваш ресурс, похоже, нисколько не противоречит моей информации. Тем не менее, стандарт на самом деле имеет несколько примеров , такие как этот драгоценный камень , где он показал , что array[index]на самом деле ptr[index]переодетый ... «определение оператора индекса []является то , что E1[E2]является идентичным (*((E1)+(E2)))» Вы не можете опровергнуть зОе
аутист
Попробуйте эту демонстрацию, @ C-Star-Puppy: int main(void) { unsigned char lower[] = "abcdefghijklmnopqrstuvwxyz"; for (size_t x = 0; x < sizeof lower - 1; x++) { putchar(x[lower]); } }... Вам, вероятно, понадобится #include <stdio.h>и <stddef.h>... Вы видите, как я написал x[lower]xцелочисленным типом), а не lower[x]? Компилятору C все равно, потому что *(lower + x)это то же значение *(x + lower), что и, и lower[x]первое, а x[lower]второе - как. Все эти выражения эквивалентны. Попробуйте их ... убедитесь сами, если вы не можете поверить мне на слово ...
аутист
... и затем, конечно, есть эта часть, на которой я сделал свой собственный акцент, но вам действительно следует прочитать всю цитату без акцента: "За исключением случаев, когда это операнд оператора sizeof, оператора _Alignof или унарный оператор &, или строковый литерал, используемый для инициализации массива, выражение, имеющее тип "массив типа", преобразуется в выражение с типом "указатель на тип", которое указывает на начальный элемент массива. объект и не является lvalue . Если объект массива имеет класс хранения регистров, поведение не определено. " То же самое и с функциями, кстати.
аутичный
Ох, и последнее замечание: @ C-Star-Puppy, Microsoft C ++ не является компилятором C и не был им уже почти 20 лет. Вы можете включить режим C89, suuuure , но мы вышли за пределы конца 1980-х годов в области вычислений. Для получения дополнительной информации по этой теме я предлагаю прочитать эту статью ... а затем переключиться на реальный компилятор C, такой как gccили clangдля всей вашей компиляции C, потому что вы обнаружите, что существует так много пакетов, которые используют функции C99 ...
аутичный
10

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

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

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

Wolph
источник
Как звучат семь массивов из 3264 целых чисел для современной 2D-игры? Если я просто параноик, решением будет большой массив.
Balkania
3
И №1, и №4 в любом случае требуют использования указателей и распределения динамической памяти. Я предлагаю использовать reallocс # 3 - выделить массив нормального размера, а затем увеличивать его, когда у вас закончится. reallocпри необходимости выполнит копирование ваших данных. Что касается вопроса OP об управлении памятью, вам просто нужно mallocодин раз в начале, freeодин раз в конце и reallocкаждый раз, когда вам не хватает места. Это не так уж и плохо.
Borealid
1
@Balkania: семь массивов по 3264 целых числа меньше 100 КБ. Это совсем не так уж много памяти.
Borealid
1
@Balkania: 7 * 3264 * 32 bitпохоже 91.39 kilobytes. Не так уж много по любым стандартам в наши дни;)
Вольф
1
Это конкретное упущение - позор, потому что не совсем очевидно, что должно произойти при reallocвозврате NULL: a->array = (int *)realloc(a->array, a->size * sizeof(int));... Возможно, лучше всего было бы записать как: int *temp = realloc(a->array, a->size * sizeof *a->array); a->array = temp;... Таким образом было бы очевидно, что все, что действительно произойдет, должно произойти раньшеNULL присваивается значение a->array(если оно вообще).
аутист
3

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

Надеемся на последующую конструктивную критику ...


источник
1
Если вам нужна конструктивная критика, лучше разместите ее на Code Review . Тем не менее, пара предложений: обязательно, чтобы код проверял успешность вызовов, malloc()прежде чем пытаться использовать выделение. Точно так же было бы ошибкой напрямую назначать результат realloc()указателю на перераспределяемую исходную память; в случае realloc()сбоя NULLвозвращается, а код остается с утечкой памяти. Гораздо эффективнее удвоить память при изменении размера, чем добавлять по одному пространству за раз: меньше обращений к realloc().
ex nihilo
1
Я знал, что меня разорвут на части, я просто пошутил, когда сказал «конструктивная критика» ... Спасибо за совет ...
2
Не пытаюсь кого-то разорвать, просто предлагаю конструктивную критику, которая могла быть высказана даже без вашего беззаботного сближения;)
ex nihilo
1
Дэвид, я подумал о вашем комментарии: «Гораздо эффективнее удвоить память при изменении размера, чем добавлять по одному пространству за раз: меньше вызовов realloc ()». Не могли бы вы пояснить это для меня, пожалуйста, почему лучше выделить вдвое больше памяти и, возможно, не использовать ее, тратя впустую память, чем назначать только количество, необходимое для задачи? Я понимаю, что вы говорите о вызовах realloc (), но почему вызывает realloc () каждый раз, когда возникает проблема? Разве это не то, для чего он нужен, чтобы перераспределить память?
1
Хотя строгое удвоение может быть неоптимальным, это определенно лучше, чем увеличивать память по одному байту (или по одному intи т. Д.) За раз. Удвоение - типичное решение, но я не думаю, что существует какое-либо оптимальное решение, подходящее для всех обстоятельств. Вот почему удвоение - хорошая идея (подойдет и другой фактор, например 1,5): если вы начнете с разумного распределения, вам может вообще не понадобиться перераспределение. Когда требуется больше памяти, разумное распределение удваивается и т. Д. Таким образом, вам, вероятно, понадобится всего один или два звонка на realloc().
ex nihilo
2

Когда ты говоришь

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

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

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

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

Ли Райан
источник
2

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

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

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

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

JOSMAR BARBOSA - M4NOV3Y
источник
Неясно, действительно ли это ответ на заданный вопрос или комментарий.
Это мнение о том, «как», и я прошу подтверждения (я ошибаюсь?), ЕСЛИ у кого-то есть идея получше. ;)
JOSMAR BARBOSA - M4NOV3Y
Думаю, я не понимаю твоего последнего предложения. Поскольку SO не является тематическим форумом, такие открытые вопросы в ответах выглядят странно.
1
Я закрепил ваше последнее предложение на том, что, я думаю, вы хотите сказать.