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

Ответ 1

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

Если вам нужен динамический массив, вы не можете избежать указателей. Почему вы боитесь? Они не будут кусать (пока вы будете осторожны, то есть). В C нет встроенного динамического массива, вам просто нужно написать его самостоятельно. В С++ вы можете использовать встроенный класс std::vector. С# и практически любой другой язык высокого уровня также имеют некоторый аналогичный класс, который управляет динамическими массивами для вас.

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

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

Ответ 2

Есть несколько вариантов, о которых я могу думать.

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

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

Ответ 3

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

К сожалению, есть ограничения. Хотя вы все еще учитесь использовать функцию, вы не должны брать на себя роль учителя, например. Я часто читаю ответы от тех, кто, кажется, не знает, как использовать realloc (то есть, в настоящее время принятый ответ!), Рассказывая другим, как использовать его неправильно, иногда под предлогом того, что они опускают обработку ошибок, даже если это обычное явление. ловушка, о которой нужно упомянуть Здесь ответ, объясняющий, как правильно использовать realloc. Обратите внимание, что ответ сохраняет возвращаемое значение в другую переменную для проверки ошибок.

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

Операторы массива являются операторами указателя. array[x] - это действительно сокращение *(array + x), которое можно разбить на: * и (array + x). Скорее всего, * это то, что вас смущает. Мы можем еще больше исключить сложение из задачи, приняв x равным 0, поэтому array[0] становится *array потому что добавление 0 не изменит значения...

... и, таким образом, мы видим, что *array эквивалентен array[0]. Вы можете использовать один, где вы хотите использовать другой, и наоборот. Операторы массива являются операторами указателя.

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

Жаль, что принятый в настоящее время ответ также идет вразрез с fooobar.com/questions/154/..., и в то же время упускает возможность представить малоизвестную функцию, которая подходит именно для этого варианта использования: гибкий массив Участники! Это на самом деле довольно сломанный ответ... :(

Когда вы определяете свою 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); когда вы закончите с этим!

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

Основываясь на дизайне Matteo Furlans, он сказал, что "большинство реализаций динамических массивов работают, начиная с массива некоторого (небольшого) размера по умолчанию, а затем, когда у вас заканчивается свободное место при добавлении нового элемента, удваивают размер массива". Разница в " незавершенном производстве " ниже заключается в том, что он не удваивается по размеру, а направлен на использование только того, что требуется. Я также пропустил проверки безопасности для простоты... Кроме того, основываясь на идее 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) 
{
  array->array = (int *)malloc(sizeof(int)); 
  array->size = 0;
}

/* Dynamically add to end of an array */
void Array_Add(Array *array, int item) 
{
    array->size += 1;
    array->array = (int *)realloc(array->array, array->size * sizeof(int));
    array->array[array->size-1] = item;
}

/* Delete from a dynamic array */
void Array_Delete(Array *array, int index) 
{
    int i;
    Array temp;

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

    array->array = (int *)realloc(temp.array, temp.size * sizeof(int)); 
}

/* 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);
}

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