Cómo replicar el vector en c?

En los días previos a c ++ y a las listas de vectores, ¿cómo expandieron el tamaño de las matrices cuando necesitaban almacenar más datos?

El código C típico se ve así:

void* newMem = realloc(oldMem, newSize); if(!newMem) { // handle error } oldMem = newMem; 

Tenga en cuenta que si realloc falla, entonces devuelve cero pero la memoria anterior sigue siendo válida, este uso típico provoca pérdida de memoria:

 oldMem = realloc(oldMem, newSize); if(!oldMem) { // handle error } 

Desafortunadamente es muy común;

También tenga en cuenta que no hay nada especial sobre C ++ vector / list. Estructuras similares se pueden implementar en C, solo la syntax (y el manejo de errores) se ven diferentes. Por ejemplo, vea el análogo de std :: de LodePNG para C.

Muchos proyectos de C terminan implementando una API similar a un vector. Las matrices dinámicas son una necesidad tan común, que es bueno abstraer la administración de memoria tanto como sea posible. Una implementación típica de C podría ser algo así como:

 typedef struct dynamic_array_struct { int* data; size_t capacity; /* total capacity */ size_t size; /* number of elements in vector */ } vector; 

Luego tendrían varias llamadas a función de API que operan en el vector :

 int vector_init(vector* v, size_t init_capacity) { v->data = malloc(init_capacity * sizeof(int)); if (!v->data) return -1; v->size = 0; v->capacity = init_capacity; return 0; /* success */ } 

Entonces, por supuesto, necesita funciones para push_back , insert , push_back , etc, que llamarían a realloc si el size excede la capacity .

 vector_resize(vector* v, size_t new_size); vector_push_back(vector* v, int element); 

Por lo general, cuando se necesita una reasignación, la capacity se duplica para evitar la reasignación todo el tiempo. Esta suele ser la misma estrategia empleada internamente por std::vector , excepto que típicamente std::vector no llamará a realloc debido a la construcción / destrucción de objetos C ++. Más bien, std::vector podría asignar un nuevo buffer, y luego copiar constructo / mover constructo los objetos (usando placement new ) en el nuevo buffer.

Una implementación vectorial real en C podría usar punteros void* como elementos en lugar de int , por lo que el código es más genérico. De todos modos, este tipo de cosas se implementa en muchos proyectos C. Consulte http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c para obtener una implementación de vector de ejemplo en C.

Comenzarían por ocultar la estructura definitoria que mantendría a los miembros necesarios para la implementación. Luego, proporciona un grupo de funciones que manipularían los contenidos de la estructura.

Algo como esto:

 typedef struct vec { unsigned char* _mem; unsigned long _elems; unsigned long _elemsize; unsigned long _capelems; unsigned long _reserve; }; vec* vec_new(unsigned long elemsize) { vec* pvec = (vec*)malloc(sizeof(vec)); pvec->_reserve = 10; pvec->_capelems = pvec->_reserve; pvec->_elemsize = elemsize; pvec->_elems = 0; pvec->_mem = (unsigned char*)malloc(pvec->_capelems * pvec->_elemsize); return pvec; } void vec_delete(vec* pvec) { free(pvec->_mem); free(pvec); } void vec_grow(vec* pvec) { unsigned char* mem = (unsigned char*)malloc((pvec->_capelems + pvec->_reserve) * pvec->_elemsize); memcpy(mem, pvec->_mem, pvec->_elems * pvec->_elemsize); free(pvec->_mem); pvec->_mem = mem; pvec->_capelems += pvec->_reserve; } void vec_push_back(vec* pvec, void* data, unsigned long elemsize) { assert(elemsize == pvec->_elemsize); if (pvec->_elems == pvec->_capelems) { vec_grow(pvec); } memcpy(pvec->_mem + (pvec->_elems * pvec->_elemsize), (unsigned char*)data, pvec->_elemsize); pvec->_elems++; } unsigned long vec_length(vec* pvec) { return pvec->_elems; } void* vec_get(vec* pvec, unsigned long index) { assert(index < pvec->_elems); return (void*)(pvec->_mem + (index * pvec->_elemsize)); } void vec_copy_item(vec* pvec, void* dest, unsigned long index) { memcpy(dest, vec_get(pvec, index), pvec->_elemsize); } void playwithvec() { vec* pvec = vec_new(sizeof(int)); for (int val = 0; val < 1000; val += 10) { vec_push_back(pvec, &val, sizeof(val)); } for (unsigned long index = (int)vec_length(pvec) - 1; (int)index >= 0; index--) { int val; vec_copy_item(pvec, &val, index); printf("vec(%d) = %d\n", index, val); } vec_delete(pvec); } 

Además de esto, lograrían la encapsulación utilizando void * en lugar de vec * para el grupo de funciones, y en realidad ocultaría la definición de estructura del usuario definiéndola dentro del módulo C que contiene el grupo de funciones en lugar del encabezado. También ocultaría las funciones que consideraría privadas, dejándolas fuera del encabezado y simplemente prototipandolas solo en el módulo C.

Puede ver la implementación vc_vector :

 struct vc_vector { size_t count; size_t element_size; size_t reserved_size; char* data; vc_vector_deleter* deleter; }; ... vc_vector* vc_vector_create_copy(const vc_vector* vector) { vc_vector* new_vector = vc_vector_create(vector->reserved_size / vector->count, vector->element_size, vector->deleter); if (unlikely(!new_vector)) { return new_vector; } if (memcpy(vector->data, new_vector->data, new_vector->element_size * vector->count) == NULL) { vc_vector_release(new_vector); new_vector = NULL; return new_vector; } new_vector->count = vector->count; return new_vector; } 

Para usarlo:

 vc_vector* v1 = vc_vector_create(0, sizeof(int), NULL); for (int i = 0; i < 10; ++i) { vc_vector_push_back(v1, &i); } // v1 = 0 1 2 3 4 5 6 7 8 9 vc_vector* v2 = vc_vector_create_copy(v1); // v2 = 0 1 2 3 4 5 6 7 8 9 (copy of v1) // to get pointer to int: const int* v2_data = vc_vector_data(v1);