Hoe breidden ze in de dagen vóór c++ en vector/lists de grootte van arrays uit toen ze meer gegevens moesten opslaan?
Antwoord 1, autoriteit 100%
Vector en lijst zijn conceptueel niet gebonden aan C++. Soortgelijke structuren kunnen in C worden geïmplementeerd, alleen de syntaxis (en foutafhandeling) zou er anders uitzien. LodePNGimplementeert bijvoorbeeld een dynamische arraymet functionaliteit die erg lijkt op die van std::vector. Een voorbeeldgebruik ziet er als volgt uit:
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);
Zoals te zien is, is het gebruik enigszins uitgebreid en moet de code worden gedupliceerd om verschillende typen te ondersteunen.
nothings/stbgeeft een eenvoudigere implementatie die werkt met elke soorten:
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);
Het biedt ook hash-kaarten en de truc die het gebruikt voor typeveilige containers in C kan ook worden toegepast op andere generieke containers.
Elk van deze methoden kan de onderliggende opslag uitbreiden door een aanroep van realloc(zie hieronder), of door nieuwe opslagruimte toe te wijzen met mallocen de oude vrij te maken met free— wat gelijk is aan hoe std::vectorzijn geheugen in C++ laat groeien.
Veel C-code, er is echter geen resorts om het geheugen rechtstreeks bij RealLOC te beheren:
void* newMem = realloc(oldMem, newSize);
if(!newMem) {
// handle error
}
oldMem = newMem;
Merk op dat reallocnull retourneert in geval van falen, maar het oude geheugen is nog steeds geldig. In een dergelijke situatie is dit gemeenschappelijk (en onjuist) gebruikslekken geheugen:
oldMem = realloc(oldMem, newSize);
if(!oldMem) {
// handle error
}
In vergelijking met std::vectoren de C-equivalenten van bovenaf, de eenvoudige reallocMETHODE GEBRUIKT OE (1) GEMAAKTE GARANTIE, OOWAAR reallockan soms efficiënter zijn als het gebeurt om het geheugen rond te verplaatsen.
Antwoord 2, Autoriteit 79%
Veel C-projecten eindigen uiteindelijk een vector-achtige API. Dynamische arrays zijn zo’n gewone behoefte, dat het leuk is om het geheugenbeheer zo veel mogelijk te abstraiteren. Een typische C-implementatie lijkt misschien iets als:
typedef struct dynamic_array_struct
{
int* data;
size_t capacity; /* total capacity */
size_t size; /* number of elements in vector */
} vector;
Dan zouden ze verschillende API-functie-oproepen hebben die werken op de 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 */
}
Dan heb je natuurlijk functies nodig voor push_back, insert, resize, enz., die reallocals sizecapacityoverschrijdt.
vector_resize(vector* v, size_t new_size);
vector_push_back(vector* v, int element);
Als een nieuwe toewijzing nodig is, wordt de capacitygewoonlijk verdubbeld om te voorkomen dat er steeds opnieuw moet worden toegewezen. Dit is meestal dezelfde strategie die intern wordt gebruikt door std::vector, behalve dat std::vectorreallocniet aanroept vanwege het C++-object constructie/vernietiging. In plaats daarvan zou std::vectoreen nieuwe buffer kunnen toewijzen, en vervolgens de objecten construct/move construct (met plaatsing new) naar de nieuwe buffer kopiëren.
Een daadwerkelijke vectorimplementatie in C kan void*-pointers als elementen gebruiken in plaats van int, dus de code is algemener. Hoe dan ook, dit soort dingen wordt in veel C-projecten geïmplementeerd. Zie http://codingrecipes.com/implementation-of-a-vector-data-structure -in-cvoor een voorbeeld van een vectorimplementatie in C.
Antwoord 3, autoriteit 28%
Ze zouden beginnen met het verbergen van de definitie van een structuur die leden zou bevatten die nodig zijn voor de implementatie. Dan een groep functies leveren die de inhoud van de structuur zou manipuleren.
Zoiets:
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);
}
Hierdoor zouden ze inkapseling bereiken door ongeldig * in de plaats van VEC * voor de Functiegroep te gebruiken en deze daadwerkelijk de structuurdefinitie uit de gebruiker te verbergen door deze te definiëren in de C-module die de groep van functies bevat in plaats van de kop . Ook zouden ze de functies verbergen die je zou overwegen om privé te zijn, door ze uit de koptekst te laten en gewoon ze alleen in de C-module te protograferen.
Antwoord 4, Autoriteit 12%
U kunt implementatie 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;
}
Om het te gebruiken:
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);
Antwoord 5, Autoriteit 5%
https://github.com/jakubgorny47/baku-code/tree /master/c_vector
Hier is mijn implementatie. Het is in feite een struct met een aanwijzer naar de gegevens, grootte (in elementen), totale toegewezen ruimte en een grootte van het type dat wordt opgeslagen in vector om het gebruik van lege aanwijzer mogelijk te maken.
Antwoord 6
U kunt de bibliotheek “Gena” gebruiken. Het lijkt sterk op stl::vectorin pure C89.
Vanaf de README bevat het:
- Toegang tot vectorelementen net als gewone C-arrays:
vec[k][j]; - Hebben multi-dimensionale arrays;
- Kopieer vectoren;
- Maak de benodigde vectortypen één keer in een aparte module, in plaats van dit elke keer te doen als je een vector nodig hebt;
- Je kunt kiezen hoe je waarden aan een vector wilt doorgeven en hoe je ze daaruit teruggeeft: op waarde of op aanwijzer.
Je kunt het hier bekijken: