Wie repliziert man den Vektor in c?

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

Vektor und Liste sind konzeptionell nicht an C++ gebunden. Ähnliche Strukturen können in C implementiert werden, nur die Syntax (und Fehlerbehandlung) würde anders aussehen. Zum Beispiel LodePNG implementiert a Dynamisches Array mit einer Funktionalität, die der von std::vector sehr ähnlich ist. Eine beispielhafte Verwendung sieht so aus:

uivector v = {};
uivector_push_back(&v, 1);
uivector_push_back(&v, 42);
for(size_t i = 0; i < v.size; ++i)
    printf("%d\n", v.data[i]);
uivector_cleanup(&v);

Wie zu sehen ist, ist die Verwendung etwas ausführlich und der Code muss dupliziert werden, um verschiedene Typen zu unterstützen.

nichts/stb gibt eine einfachere Implementierung, die mit allen Typen funktioniert:

double *v = 0;
arrpush(v, 1.0);
arrpush(v, 42.0);
for(int i = 0; i < arrlen(v); ++i)
    printf("%g\n", v[i]);
arrfree(v);

Es bietet auch Hash-Maps, und der Trick, den es für typsichere Container in C verwendet, kann auch auf andere generische Container angewendet werden.

Jede dieser Methoden kann den zugrunde liegenden Speicher entweder durch einen Aufruf von erweitern realloc (siehe unten), oder indem Sie neuen Speicher mit zuweisen malloc und das Alte mit befreien free – was äquivalent ist zu wie std::vector vergrößert seinen Speicher in C++.

Viel C-Code greift jedoch auf die Verwaltung des Speichers direkt mit realloc zurück:

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

Beachten Sie, dass realloc gibt im Fehlerfall null zurück, aber der alte Speicher ist noch gültig. In einer solchen Situation führt diese häufige (und falsche) Verwendung zu Speicherlecks:

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

Verglichen mit std::vector und die C-Äquivalente von oben, die einfachen realloc Die Methode bietet jedoch keine amortisierte O(1)-Garantie realloc kann manchmal effizienter sein, wenn es passiert, dass der Speicher nicht verschoben wird.

Viele C-Projekte enden damit, eine vektorähnliche API zu implementieren. Dynamische Arrays sind ein so häufiges Bedürfnis, dass es schön ist, die Speicherverwaltung so weit wie möglich zu abstrahieren. Eine typische C-Implementierung könnte etwa so aussehen:

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

Dann hätten sie verschiedene API-Funktionsaufrufe, die auf dem arbeiten 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 */
}

Dann braucht man natürlich Funktionen für push_back, insert, resizeetc, was anrufen würde realloc wenn size übersteigt capacity.

vector_resize(vector* v, size_t new_size);

vector_push_back(vector* v, int element);

Wenn eine Umverteilung erforderlich ist, capacity wird verdoppelt, um eine ständige Neuzuweisung zu vermeiden. Dies ist normalerweise die gleiche Strategie, die intern von verwendet wird std::vectoraußer in der Regel std::vector werde nicht anrufen realloc wegen der Konstruktion/Zerstörung von C++-Objekten. Eher, std::vector könnte einen neuen Puffer zuweisen und dann die Objekte kopieren, konstruieren/verschieben (unter Verwendung von Placement new) in den neuen Puffer.

Eine tatsächliche Vektorimplementierung in C könnte verwendet werden void* Zeiger als Elemente statt int, daher ist der Code allgemeiner. Jedenfalls wird so etwas in vielen C-Projekten implementiert. Sehen http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c für eine beispielhafte Vektorimplementierung in C.

Sie würden damit beginnen, die Definition einer Struktur zu verbergen, die die für die Implementierung erforderlichen Mitglieder enthalten würde. Dann Bereitstellung einer Gruppe von Funktionen, die den Inhalt der Struktur manipulieren würden.

Etwas wie das:

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

Darüber hinaus würden sie eine Kapselung erreichen, indem sie void* anstelle von vec* für die Funktionsgruppe verwenden und die Strukturdefinition tatsächlich vor dem Benutzer verbergen, indem sie sie innerhalb des C-Moduls definieren, das die Funktionsgruppe und nicht den Header enthält. Außerdem würden sie die Funktionen verbergen, die Sie als privat betrachten würden, indem sie sie aus dem Header weglassen und sie einfach nur im C-Modul prototypisieren.

Sie können die Umsetzung sehen vc_Vektor:

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

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

https://github.com/jakubgorny47/baku-code/tree/master/c_vector

Hier ist meine Implementierung. Es ist im Grunde eine Struktur, die einen Zeiger auf die Daten, die Größe (in Elementen), den insgesamt zugewiesenen Speicherplatz und eine Größe des Typs enthält, der im Vektor gespeichert wird, um die Verwendung des void-Zeigers zu ermöglichen.

Sie können “Gen” Bibliothek. Es ähnelt stark stl::vector im Reinen C89.

Aus der README enthält es:

• Greifen Sie auf Vektorelemente wie auf einfache C-Arrays zu: vec[k][j];
• Mehrdimensionale Arrays haben;
• Vektoren kopieren;
• Instanziieren Sie die erforderlichen Vektortypen einmal in einem separaten Modul, anstatt dies jedes Mal zu tun, wenn Sie einen Vektor benötigen.
• Sie können wählen, wie Sie Werte an einen Vektor übergeben und wie Sie sie daraus zurückgeben: per Wert oder per Zeiger.

Sie können es hier überprüfen:

https://github.com/cher-nov/Gena