Come replicare il vettore in c?

Question

Nei giorni precedenti a C++ e vettoriali/elenchi, come hanno ampliato la dimensione degli array quando avevano bisogno di archiviare più dati?

Answer 1

codice C tipico è simile al seguente:

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

oldMem = newMem; 

Nota che se realloc riesce poi ritorna a zero, ma la vecchia memoria è ancora valida, questo uso tipico provoca perdita di memoria:

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

Purtroppo è molto comune;

Si noti inoltre che non vi è nulla di speciale nel vettore/elenco C++. Strutture simili possono essere implementate in C, solo la sintassi (e la gestione degli errori) hanno un aspetto diverso. Ad esempio vedi LodePNG's analogico di std :: vector per C.

Answer 2

Un sacco di progetti C finiscono per implementare un'API vettoriale. Gli array dinamici sono una necessità così comune, che è bello estrapolare il più possibile la gestione della memoria. Una tipica implementazione C potrebbe essere simile:

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

allora avrebbero diverse chiamate di funzione API che operano sul 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 */ 
} 

Poi, naturalmente, è necessario funzioni per push_back, insert, resize , ecc., che chiamerebbe realloc se size supera capacity.

vector_resize(vector* v, size_t new_size); 

vector_push_back(vector* v, int element); 

Di solito, quando è necessaria una riallocazione, capacity è raddoppiato per evitare la riallocazione tutto il tempo. Di solito si tratta della stessa strategia utilizzata internamente da std::vector, ad eccezione del fatto che lo realloc, in genere, non viene chiamato realloc a causa della distruzione/distruzione dell'oggetto C++. Piuttosto, std::vector potrebbe allocare un nuovo buffer, quindi copiare construct/move costruire gli oggetti (usando il posizionamento new) nel nuovo buffer.

Un'implementazione vettoriale reale in C potrebbe utilizzare i puntatori void* come elementi anziché int, quindi il codice è più generico. Comunque, questo genere di cose è implementato in molti progetti C. Vedere http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c per un'implementazione vettoriale di esempio in C.

Answer 3

Iniziano nascondendo la definizione di una struttura che terrebbe i membri necessari per l'implementazione. Quindi fornire un gruppo di funzioni che manipolerebbero i contenuti della struttura.

Qualcosa di simile:

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

Oltre a questo intendano realizzare incapsulamento utilizzando void * al posto di * vec per il gruppo di funzioni, ed effettivamente nascondere la definizione della struttura dall'utente definendo all'interno il modulo C che contiene il gruppo di funzioni piuttosto che l'intestazione. Inoltre nascondono le funzioni che consideri private, lasciandole fuori dall'intestazione e semplicemente prototipandole solo nel modulo C.

Answer 4

Potete vedere implementazione 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; 
} 

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