Как я могу реализовать общий, динамически растущий массив в C?

Мои требования:

  • Структура данных должна содержать произвольное количество элементов (порядка сотен тысяч).
  • Структура данных должна эффективно использовать память. В этом случае это означает добавление дополнительных сотен тысяч предметов, когда они необходимы.
  • Структура данных должна содержать элементы неизвестного, но однородного типа.

То, как я ожидал, что смогу построить, – это определить структуру, представляющую массив. Структура содержала длину массива и количество элементов в массиве. Он также содержал указатель на массив указателей void, которые приводили к фактическим данным.

Схема, показывающая концептуальную компоновку структуры данных

Указатель использовался, потому что память была malloc () ‘d и realloc ()’ d по мере роста массива. Массив был не указаным, потому что тип элементов был неизвестен. Пользователь должен создавать и инициализировать элементы, передавать их в реализацию массива и отслеживать, какой тип использовался.

В памяти структура будет существовать либо в стеке, либо в куче (выбор пользователя), сами элементы будут разбросаны по всей куче, а массив указателей на элементы будет существовать в куче.

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

Есть ли другой подход, который я должен использовать?


Код Нгуа помог мне понять это правильно! Его ниже в его ответе, и вот реализация, которую я написал на основе его кода:

typedef struct { void **head; size_t used_size; size_t free_size; size_t current_size; size_t size_increment; } GrowingArray; GrowingArray createEmptyGrowingArray(int initial_size, int size_increment) { GrowingArray empty_growing_array; empty_growing_array.head = malloc(initial_size * sizeof(void *)); empty_growing_array.used_size = 0; empty_growing_array.free_size = initial_size; empty_growing_array.current_size = initial_size; empty_growing_array.size_increment = size_increment; return empty_growing_array; } GrowingArray appendToGrowingArray(GrowingArray growing_array, void *new_element) { void *new_head_of_array; if (growing_array.free_size == 0) { new_head_of_array = realloc(growing_array.head, (growing_array.current_size + growing_array.size_increment) * sizeof(void*)); if (new_head_of_array == NULL) { printf("Reallocation failure.\n"); } growing_array.free_size = growing_array.size_increment; growing_array.current_size += growing_array.size_increment; growing_array.head = new_head_of_array; } growing_array.head[growing_array.used_size++] = new_element; growing_array.free_size--; return growing_array; } void finalizeGrowingArrayMemory(GrowingArray growing_array) { growing_array.head = realloc(growing_array.head, growing_array.current_size * sizeof(void *)); } void freeGrowingArray(GrowingArray growing_array) { free(growing_array.head); } int main(int argc, char* argv[]) { GrowingArray test_array = createEmptyGrowingArray(5, 1); int *test_integer = (int *)malloc(1 * sizeof(int)); *test_integer = 4; int *another_integer = (int *)malloc(1 * sizeof(int)); *another_integer = 6; int *yet_another_integer = (int *)malloc(sizeof(int)); *yet_another_integer = 9; test_array = appendToGrowingArray(test_array, test_integer); test_array = appendToGrowingArray(test_array, another_integer); test_array = appendToGrowingArray(test_array, yet_another_integer); finalizeGrowingArrayMemory(test_array); printf("%x,", *(int *)test_array.head[0]); printf("%x,", *(int *)test_array.head[1]); printf("%x\n", *(int *)test_array.head[2]); freeGrowingArray(test_array); printf("Going to free %llx\n", (long long int)test_integer); free(test_integer); printf("Going to free %llx\n", (long long int)another_integer); free(another_integer); printf("Going to free %llx\n", (long long int)yet_another_integer); free(yet_another_integer); return 0; } 

Вот код, который пытается дать вам представление о том, что вы описали. Это не решение. Это в масштабе 2, поэтому вы можете растянуть это.

  #include  #include  const size_t stIncrement = 2; typedef struct { size_t space_left; size_t size; void **vptrX; }T; T t; void vStoreData( void *data ) { void *vptrTemp; size_t stMaxLength; if( t.space_left == 0 ) { stMaxLength = t.size + stIncrement; vptrTemp = realloc(t.vptrX, stMaxLength * sizeof(void *) ); if( vptrTemp == NULL ){ printf( "Failed realloc"); exit(1); } t.space_left = stIncrement; t.vptrX = vptrTemp; } t.vptrX[t.size++] = data; t.space_left--; } //This will make the memory efficient. void vFinalizeMemory() { t.vptrX = realloc(t.vptrX, t.size * sizeof(void *)); } int main(void) { int i; char c; float d; char *cp = "How are you"; i = 10; c ='O'; d = 40.12345; t.vptrX = malloc(stIncrement*sizeof(void *)); t.size = 0; t.space_left = 2; vStoreData( &i ); vStoreData( &c ); vStoreData( cp ); vStoreData( &d ); vStoreData( &c ); vStoreData( cp ); vStoreData( &d ); vFinalizeMemory(); printf( "%d\n", *((int *)t.vptrX[0]) ); printf( "%c\n", *((char *)t.vptrX[1] )); printf( "%s\n", (char *)t.vptrX[2] ); printf( "%f\n", *((float*)t.vptrX[3] )); printf( "%c\n", *((char *)t.vptrX[4] )); printf( "%s\n", (char *)t.vptrX[5] ); printf( "%f\n", *((float*)t.vptrX[6] )); return 0; } 

Вам нужен указатель на массив указателей void, а не указатель void;

 void ** array_of_pointers_to_actual_elements ; 

Удачи!