¿Cómo replicar el vector en c?

Question

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

Answer 1

típico código C es el siguiente:

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

oldMem = newMem; 

Tenga en cuenta que si realloc falla, entonces se devuelve cero pero la vieja memoria sigue siendo válido, 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 sintaxis (y el manejo de errores) se ven diferentes. Por ejemplo, vea LodePNG's analog de std :: vector para C.

Answer 2

Muchos proyectos C terminan implementando una API tipo 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 aplicación típica C podría ser algo como:

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

entonces tendrían varias llamadas a funciones 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 */ 
} 

Luego, por supuesto, necesita funciones para push_back, insert, resize , etc., que llamaría realloc si size supera 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, capacity se dobla para evitar la reasignación de todo el tiempo. Esta es generalmente la misma estrategia empleada internamente por std::vector, excepto que típicamente std::vector no llamará al realloc debido a la construcción/destrucción de objetos en C++. Más bien, std::vector podría asignar un nuevo búfer, y luego copiar construir/mover construir los objetos (utilizando la ubicación new) en el nuevo búfer.

Una implementación de vector 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. Ver http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c para una implementación de vector de ejemplo en C.

Answer 3

Comenzarían por ocultar la definición de una estructura 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 lo que lograrían encapsulación mediante el uso de void * en el lugar de * vec para el grupo de funciones, y en realidad ocultar la definición de la estructura del usuario mediante la definición de un plazo de el 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.

Answer 4

Se puede ver la aplicació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);