How to replicate vector in c?

Question

In the days before c++ and vector/lists, how did they expand the size of arrays when they needed to store more data?

Answer 1

Vector and list aren't conceptually tied to C++. Similar structures can be implemented in C, just the syntax (and error handling) would look different. For example LodePNG implements a dynamic array with functionality very similar to that of std::vector. A sample usage looks like:

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

As can be seen the usage is somewhat verbose and the code needs to be duplicated to support different types.

nothings/stb gives a simpler implementation that works with any types:

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

It also provides hash maps, and the trick it uses for type-safe containers in C can be applied to other generic containers too.

Any of these methods can expand the underlying storage either by a call to realloc (see below), or by allocating new storage with malloc and freeing the old one with free -- which is equivalent to how std::vector grows its memory in C++.

---

A lot of C code, however, resorts to managing the memory directly with realloc:

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

Note that realloc returns null in case of failure, yet the old memory is still valid. In such a situation this common (and incorrect) usage leaks memory:

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

Compared to std::vector and the C equivalents from above, the simple realloc method does not provide O(1) amortized guarantee, even though realloc may sometimes be more efficient if it happens to avoid moving the memory around.

Answer 2

A lot of C projects end up implementing a vector-like API. Dynamic arrays are such a common need, that it's nice to abstract away the memory management as much as possible. A typical C implementation might look something like:

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

Then they would have various API function calls which operate on the 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 */ } 

Then of course, you need functions for push_back, insert, resize, etc, which would call realloc if size exceeds capacity.

vector_resize(vector* v, size_t new_size);  vector_push_back(vector* v, int element); 

Usually, when a reallocation is needed, capacity is doubled to avoid reallocating all the time. This is usually the same strategy employed internally by std::vector, except typically std::vector won't call realloc because of C++ object construction/destruction. Rather, std::vector might allocate a new buffer, and then copy construct/move construct the objects (using placement new) into the new buffer.

An actual vector implementation in C might use void* pointers as elements rather than int, so the code is more generic. Anyway, this sort of thing is implemented in a lot of C projects. See http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c for an example vector implementation in C.