如何在C中实现一个通用的，动态增长的数组？ [英] How may I implement a generic, dynamically growing array in C?
问题描述
我的要求：
- 数据结构必须能够容纳任意数量的元素（大约数十万） 。
- 数据结构必须有效地使用内存。在这种情况下，这意味着每当需要时可以增加十万个项目。
- 数据结构必须包含未知但统一类型的项目。
我希望能够构建一个的方法是定义一个表示数组的结构体。该结构体包含数组的长度和数组中的元素数。它还包含一个指向void指针数组的指针，这导致了实际的数据。
The way I expected to be able to build one was to define a struct which represented the array. The struct contained the length of the array and the number of elements in the array. It also contained a pointer to an array of void pointers, which led to the actual data.
使用指针，因为内存是数组增长的malloc（）'d和realloc（）'d。该数组是void指针，因为元素的类型是未知的。用户有责任创建和初始化元素，将其传递给数组实现，并跟踪使用的类型。
The pointer was used because the memory was malloc()'d and realloc()'d as the array grew. The array was of void pointers because the type of the elements was unknown. It was the responsibility of the user to create and initialize elements, to pass them to the array implementation, and to keep track what type was being used.
在内存中，结构体将存在于堆栈或堆中（用户选择），元素本身将分散在整个堆中，并且元素的指针数组将存在于堆中。
In memory, the struct would exist either on the stack or in the heap (user's choice), the elements themselves would be scattered throughout the heap, and the array of pointers to the elements would exist in the heap.
问题是，当我实现这个时，我需要能够为指针数组中的一个点指定一个void指针（例如，当附加一个元素时），而我无法做到这一点，因为void指针不能被分配（编译器说不完全类型void不可分配）。
The problem is that when I went to implement this, I needed to be able to assign a void pointer to a spot in the array of pointers (e.g. when appending an element), and I could not do this because void pointers cannot be assigned (compiler says "incomplete type 'void' is not assignable").
有不同的方法我应该使用？
Is there a different approach I should be using?
Nguai的代码帮助我得到正确的！他的答案在下面，这里是我根据他的代码编写的实现：
Nguai's code helped me get it right! His is below in his answer, and here is the implementation I wrote based on his code:
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的比例，所以你可以拉伸这个。
Here is a code that is trying to give you an idea what you have described. By no means, this is a solution. This is in a scale of 2, so you can stretch this.
#include <stdio.h>
#include <stdlib.h>
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;
}
这篇关于如何在C中实现一个通用的，动态增长的数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
