Wie replizieren Vektor in c?

Question

In den Tagen vor C++ und Vektor/Listen, wie haben sie die Größe von Arrays erweitert, wenn sie mehr Daten speichern mussten?

Answer 1

Typische C-Code sieht wie folgt aus:

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

oldMem = newMem; 

Beachten Sie, dass, wenn realloc versagt, dann gibt es Null, aber der alte Speicher ist immer noch gültig, diese typische Verwendung Speicherleck verursacht:

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

Leider Es ist sehr gängig;

Beachten Sie auch, dass C++ Vektor/Liste nichts Besonderes ist. Ähnliche Strukturen können in C implementiert werden, nur die Syntax (und die Fehlerbehandlung) sehen anders aus. Zum Beispiel siehe LodePNG's analog von std :: vector für C.

Answer 2

Viele C-Projekte enden mit der Implementierung einer Vektor-ähnlichen API. Dynamische Arrays sind ein so häufiges Bedürfnis, dass es gut ist, die Speicherverwaltung so weit wie möglich wegzuspulen. Eine typische C-Implementierung könnte etwas wie folgt aussehen:

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

Dann würden sie verschiedene API-Funktionsaufrufe haben, die auf dem vector arbeiten:

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 */ 
} 

Dann natürlich Sie benötigen Funktionen für push_back, insert, resize usw., die realloc aufrufen würde, wenn sizecapacity überschreitet.

vector_resize(vector* v, size_t new_size); 

vector_push_back(vector* v, int element); 

Normalerweise, wenn eine Neuzuweisung erforderlich ist, wird capacity verdoppelt die ganze Zeit zu vermeiden Neuzuweisung. Dies ist normalerweise die gleiche Strategie, die intern von std::vector verwendet wird, mit der Ausnahme, dass std::vector aufgrund der C++ - Objektkonstruktion/-Zerstörung nicht realloc aufgerufen wird. Stattdessen kann std::vector einen neuen Puffer zuweisen und dann construct/move die Objekte (mit der Platzierung new) in den neuen Puffer kopieren.

Eine tatsächliche Vektorimplementierung in C könnte void* Zeiger als Elemente anstelle von int verwenden, so dass der Code generischer ist. Wie auch immer, solche Dinge werden in vielen C-Projekten implementiert. Eine http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c Beispielvektorimplementierung in C.

Answer 3

Sie würden beginnen, indem sie das Definieren einer Struktur verbergen, die Mitglieder halten würde, die für die Implementierung notwendig sind. Dann wird eine Gruppe von Funktionen bereitgestellt, die den Inhalt der Struktur manipulieren würden.

Etwas wie folgt aus:

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

Im Anschluss an diese sie Verkapselung unter Verwendung von void * an der Stelle von vec * für die Funktionsgruppe erreichen würde, und verstecken tatsächlich die Strukturdefinition von dem Benutzer, indem sie es in der Definition das C-Modul enthält die Funktionsgruppe und nicht den Header. Außerdem würden sie die Funktionen verbergen, die Sie für privat halten würden, indem Sie sie aus dem Header herauslassen und sie nur im C-Modul prototypisieren.

Answer 4

können Sie sehen Implementierung 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; 
} 

es zu benutzen:

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