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.