16 minutes
A Typesafe Dynamic std::vector equivalent in C
I’m writing a game in c, and inevitably in c, you have to deal with the fact that c doesn’t have std::vector or anything like it. If you want to store like items in a dynamically resizing container, you do have a few options. Let’s go on a tour.
NOTE: If you’re coming here from non c/c++ land, we’ll also be talking about the c-preprocessor a bit. c macros through the preprocessor perform naive text substitutions, with some limits on recursive substitutions we have to work around.
Prior Art
Stretchy Buffer
Sean Barret’s stretchy_buffer.h is a good contender.
NOTE: Sean Barret has since deprecated stretch_buffer.h and replaced it with stb_ds.h which contains a dynamic array implementation that is more full-featured, but operates under similar principles.
stretchy_buffer implements the array as a fat pointer. Fat Pointers are pointers that store a little extra data about the thing their pointing to. To illustrate the basic principle of a fat pointer, imagine we need to allocate a pointer to an object of size 16 O and store a piece of meta-data about it m of size 4. Everything is in bytes. To do this as a fat pointer, we would allocate a memory block sizeof(O) + sizeof(m) (16 + 4) for a total size of 20. We’re going to put memory alignment issues aside for the moment. Once we have our pointer p of size 20, we’ll create pointer p’ by moving p by 4 bytes.
Allocated Block
0 4 8 12 16 20
↓ ↓ ↓ ↓ ↓ ↓
--------------------
↑ ↑
p → p'
We now have two regions, one before the pointer of size 4, where we can store m and one where we can store the object O. Notably, this pattern preserves direct pointer access to O. The meta data can still be accessed with some pointer arithmetic. This pattern is commonly used for strings, where O is the string’s content and m is the string’s length.
0 4 8 12 16 20
↓ ↓ ↓ ↓ ↓ ↓
--------------------
[m ][ O ]
↑
p'
stretchy_buffer stores two values as meta-data, the array’s current occupancy (count) and total occupancy it can support with the amount of memory it has(cap). This is sufficient to implement automatic resizing. The other thing that makes stretchy_buffer work is that its operations are implemented as a series of macros. As you can see in this excerpt:
#define stb_sb_free(a) ((a) ? free(stb__sbraw(a)),0 : 0)
#define stb_sb_push(a,v) (stb__sbmaybegrow(a,1), (a)[stb__sbn(a)++] = (v))
#define stb_sb_count(a) ((a) ? stb__sbn(a) : 0)
#define stb_sb_add(a,n) (stb__sbmaybegrow(a,n), stb__sbn(a)+=(n), &(a)[stb__sbn(a)-(n)])
#define stb_sb_last(a) ((a)[stb__sbn(a)-1])
And the usage code is also ergonomic:
#include "stretchy_buffer.h"
int *array = 0;
int a = 5
sb_push(array, a);
sb_push(array, 6);
sb_push(array, 7);
int b = array[0];
Because you declare the pointer as pointing to the type it stores, the system is largely typesafe during normal use. The implementation is also truly tiny. If you just need ‘an’ array, this will do the job, especially if you’re not squemish about the intrusion of macros into your c code.
Macro Templates
So if you don’t want to do that, or you need your array needs to do ‘something’ that would be annoying to implement as macros, or if you’re just not willing to accept that level of macro intrusion, you could emulate c++ templates by using the c preprocessor to get something a little more familiar to std::vector.
// Template Via Macro
#define TYPE int
#define NAME i
#include "template-array.h"
// Example Usage:
i_Array array = i_ArrayCreate(128);
i_ArrayPush(&array, 5);
int item = array.items[0];
The usage code is calling into an interface generated by the preprocessor but the usage itself doesn’t invoke the preprocessor at all. I also don’t like that this will necessitate putting the array type definition way at the top of the file instead of at it’s usage site. Since we wish to store many types using arrays, this will cause many files to have a long collection of array definitions at the top, and even the most diligent programmer will forget to remove the unneeded ones. This method will also generate a lot more code, and in a sense you will get the worst of both worlds because “template-array.h” is going to be full of less-scrutable preprocessor stuff. As just an example, forming the function i_ArrayCreate() will require code that looks like this:
typedef struct JOIN(NAME,_Array)
{
int count;
int cap;
TYPE *items;
} JOIN(NAME,_Array);
JOIN(NAME,_Array) JOIN(NAME, _ArrayCreate)(int initCap)
{
JOIN(NAME, _Array) result =
{
.count = 0,
.cap = initCap,
.items = ALLOC(sizeof(TYPE)*initCap),
};
ZERO(items, sizeof(TYPE)*initCap);
return result;
}
We’ve already sacrificed some readability in the array implementation. Of course, the preprocessor won’t consistently join tokens together when they are passed into a ‘function-like macro invocation’ unless you use a work-around so instead of typing NAME ## _Array, you have to type JOIN(NAME, _ARRAY), and JOIN will have the following definition:
#define JOIN3(a,b) a ## b
#define JOIN2(a,b) JOIN3(a,b)
#define JOIN(a,b) JOIN2(a,b)
But to be honest, this is some of the more tame preprocessor manipulation I’ve seen, so make of this what you will. Interestingly, you can also invert this pattern. We define template parameters and then included a header that used them. But you could also include a header that defines a macro that generates the code from its arguments. i.e.
// Template Via Macro
#include "template-array.h"
INSTANTIATE_ARRAY(i,int,0)
// Example Usage:
i_Array array = i_ArrayCreate(128);
i_ArrayPush(&array, 5);
int item = array.items[0];
If you’re curious, the inside of “template-array.h” will look like this:
#define INSTANTIATE_ARRAY(NAME, TYPE, INIT) \
typedef struct JOIN(NAME, _Array) \
{ \
int count; \
int cap; \
TYPE *items; \
} JOIN(NAME, _Array); \
JOIN(NAME, _Array) JOIN(NAME, _ArrayCreate)(int initCap) \
{ \
JOIN(NAME, _Array) result = \
{ \
.count = 0, \
.cap = initCap, \
.items = malloc(sizeof(TYPE)*initCap), \
}; \
\
for (int i = 0; i < result.cap; i++) \
{ result.items[i] = INIT; } \
\
return result; \
}
Fun.
Void Pointer Generics
And then there’s the old choice. My impression is that many older c collections implement their data structures using void* to accept any type. The implementation is trivial if annoying. The usage code is straight-forward.
// inclusion
#include "c-array.h"
// usage
Array array = ArrayCreate(sizeof(int), 128);
int a = 5;
ArrayPush(&array, &a);
// there are ways to make this access less terrible
int b = ((int*)array.items)[0];
// or
int b = 0;
ArrayGet(&b, &array, 0);
NOTE: If you’re coming from C++, you may be surprised by the lack of casts to (void*). In c, unlike c++, all pointer types implicitly cast to void*.
Although the implementation will involve no proprocessor nonsense, we’ve not only fully given up type-checking, but introduced a easily stepped on error case that will be miserable to track down. You see because the array interface uses void pointers, the signiture of ArrayPush() will be something like
int ArrayPush(Array *array, void *item);
Then, it will use the sizeof data we gave to ArrayCreate() to know how many bytes to copy from pointer item to next slot of array->items. And that means…
Array array = ArrayCreate(sizeof(int), 128);
long long int a = 5;
// type mismatch long long int vs int
// No warning or error, but will create malformed data.
ArrayPush(&array, &a);
typedef struct GiantStructThing
{
//...
} GiantStructThing;
GiantStructThing giantStruct = {0};
// It won't warn you about this either.
ArrayPush(&array, &giantStruct);
We no longer detect any type mismatches when adding to the array. Which is, as I would call it, an oof.
A Proposed Solution: Partial Generics
I have implemented and am using a compromise solution that I believe provides the best of these properties, which I’m calling Partial Generics.
My solution comes from the following insights:
- We need type-checking only for operations that actually read or write elements in the array, from the outside.
- Therefore, operations that don’t copy items into or out of the array don’t need type-checking.
- Moving items internally to the array can be done safely using sizeof and/or alignof information.
- For many operations, we can return an index rather than the value, and then have the usage code perform a typesafe access.
- We could implement a dynamic array that can be accessed through a typed pointer to preserve type-checking, but has other operations invoked through generic void pointers using stored size and layout info.
The Partially Generic Array takes the form of a fat pointer where the meta-data item is an ArrayHeader struct that stores information like occupancy, capacity, and grow factor. In my code base it also stores some information related to allocator, and to other features intrusively implemented as part of the array.
{ArrayInfo} | Item 0 | Item 1 | Item 2 | ...
⬑ Pointer to array points here.
Let’s take a look at usage code.
// inclusion
#include "array.h"
// usage
// creation/init
int *array = ArrayCreate(sizeof(*array), 128);
// add item
int slot = ArrayReserve((void**) &array, 1);
array[slot] = 5;
// add multiple items
slot = ArrayReserve((void**) &array, 2);
array[slot] = 7;
array[slot+1] = 6;
// read
int a = array[0];
int b = array[1];
// generic function
ArraySort(array);
// similarly: ArrayClear(array);
// remove
ArrayRemove(array, 0);
// info
int count = ArrayCount(array);
The create function takes as input the memory attributes of the member type, and an initial capacity. It uses those memory attributes to place the meta data in the fat pointer, and then returns the pointer to the block of memory containing the array’s members.
void *ArrayCreate(size_t itemSize, size_t itemAlign, size_t initCap)
{
size_t headerSize = ((sizeof(ArrayHeader)/itemSize+1)*itemSize;
size_t headerDiff = headerSize - sizeof(ArrayHeader);
ArrayHeader *header = (ArrayHeader*) malloc(itemSize*initCap+headerSize);
header = (ArrayHeader*)(((char*)header) + headerDiff);
*header = (ArrayHeader)
{
.count = 0,
.cap = initCap,
.itemSize = itemSize,
.itemAlign = itemAlign,
.growFactor = 4,
};
return header+1;
}
The reserve function is called to find out what slot a new item should go into. It checks the capacity of the array and grows it if necessary, grows the array to be able to contain the new items. It can be called once to reserve space for reserveCount contiguous elements on the end of the array.
size_t ArrayReserve(void **array, size_t reserveCount)
{
ArrayHeader *header = ArrayGetHeader(*array);
assert(reserveCount > 0);
// do we need to resize?
size_t oldCount = header->count;
size_t avail = header->cap - header->cap;
if (avail < reserveCount)
{
if (header->growFactor == 0)
{
// error
}
size_t newArrayCap = header->cap;
if (newArraycap == 0)
{ newArrayCap = header->growFactor; }
// increase cap using growFactor until big enough
while (newArrayCap < header->count + reserveCount)
{
newArrayCap *= header->growFactor;
}
// reallocate and move header pointer
size_t headerSize = ((sizeof(ArrayHeader)/header->itemSize)+1)*header->itemSize;
size_t headerDiff = headerSize - sizeof(ArrayHeader);
size_t newArraySize = headerSize + header->itemSize*newArrayCap;
void *base = (void*) (((char*)array)-headerSize);
void *np = realloc( header->allocator, base, newArraySize);
header = (void*) (((char*)np) + headerDiff);
header->cap = newArrayCap;
}
// return the slot that new elements can be copied to
size_t index = header->count;
header->cont += reserveCount;
// re-write array pointer in case of realloc
*array = HeaderGetArray(header);
return index;
}
You may notice that the reserve function takes as input a void** to the address of the array. In fat pointer implementations with actual functions, as opposed to macros that expand in place, one must sometimes pass the array, and sometimes pass the address where the pointer to the array is stored. And because of c’s automatic casting to void*, and I deemed this too prone to error. If ArrayReserve() accepted a void* instead of a void**, it would be come trivial to make this disasterous error:
int *array = ArrayCreate(/*...*/);
// correct, ArrayReserve needs to assign to the array reference it gets when the array resizes, so we have address of the array pointer.
int slot = ArrayReserve(&array,1);
// wrong, no error, fails at runtime, vulnerable to various forms of memory corruption
// also the normal way to pass the array to functions.
int slot = ArrayReserve(array,1);
To remove the possibility of this error, I made ArrayReserve() take a void**, which counter intuitively, is a type that other pointers do not implicitly cast to in c. This mild inconvience slightly damages ergonomics by forcing the users to cast the array pointer explicitly, but in my experience completely stopped this error from occuring. This is why the usage code from above calls the function with the void** cast. i.e.
int slot = ArrayReserve((void**) &array,1);
But this compromise can probably be improved. More on that at the end. Another initial pain-point is the lack of a proper pushback function. This model cannot include a pushback function because the functions operating on the array accept it as a void* and copy the array items around without knowledge of their type information. ArrayPushback would have to take the form
void ArrayPushback(void** array, void *item);
Which would have the same issues as the void pointer generic implementation.
. . .
But what if we stole one more piece of Sean Barret’s stretchy_buffer?
#define ARRAY_ADD(ar,it) \
do\
{\
size_t index = ArrayReserve((void*)&(ar), 1);\
ar[index] = it;\
} while(0)
Hey look! There’s no reason we can’t use a macro just to perform typed pushback like array insertion.
int *array = ArrayCreate(sizeof(*array), 128);
ARRAY_ADD(array, 5);
ARRAY_ADD(array, 6);
ARRAY_ADD(array, 7);
And now we have every property we were looking for. The implementation I’m using is a bit heavier, because I add features and operations to it whenever I find one my game could use, but these are the fundamentals.
Limitations
One ‘foot-gun’ that I was unable to eliminate occurs when you pass around the array. If the array is passed to a function that may add members or otherwise cause it to resize, it must be passed by address, so that the calling context receives the re-allocation. Consider the following correct case:
void UseArray(int **array)
{
// notice the lack of an '&'
int slot = ArrayReserve((void**) array, 1);
*array[slot] = 4;
}
// ...
// init cap of 4
int *array = ArrayCreate(sizeof(*array), 4);
// use up all the capacity
ARRAY_ADD(array,0);
ARRAY_ADD(array,1);
ARRAY_ADD(array,2);
ARRAY_ADD(array,3);
// function adds to array, forces resize, but reallocated pointer is fine because we passed &array.
UseArray(&array);
ARRAY_ADD(array,5);
By lack of contrast, the incorrect case looks very similar, will not be caught by the compiler, and will not be noticed by the user unfamiliar with this pattern.
void UseArray(int *array)
{
int slot = ArrayReserve((void**) &array, 1);
array[slot] = 4;
}
// ...
// init cap of 4
int *array = ArrayCreate(sizeof(*array), 4);
// use up all the capacity
ARRAY_ADD(array,0);
ARRAY_ADD(array,1);
ARRAY_ADD(array,2);
ARRAY_ADD(array,3);
// function adds to array, forces resize, but reallocated pointer goes out of scope when function returns.
UseArray(array);
// array pointer is stale, uh oh...
ARRAY_ADD(array,5);
This error has not occured in my codebase, but again, likely would in a codebase where there are several or many users unfamiliar with the implementation. See more at the end.
Conclusion
To be honest, it’s not everything I would hope for, but it’s good enough to use c in a modern and type-safe way, and fits my purposes. If you’re programming c in 2026 and need an resizing array, this is what I have found to be the best set of compromises.
Addendum
I have considered implementing a version where the data pointer is stored in a structure, and therefore a pointer to the structure could be safely passed around. I understand this pattern to be common in languages like Zig and perhaps some others. The issue in this case is that we forced to choose between an array struct carrying a generic void*, or a neverending series of near identical array structures with typed pointers. Have fun passing them to a common function family!
But… Let’s try anyway. A macro of the form
typedef struct ArrayGeneric { void *arr; } ArrayGeneric;
#define DECLARE_ARRAY(type) union { ArrayGeneric gen; type *items; };
declares a type that can be used in both ways
DECLARE_ARRAY(int) array = { .gen = ArrayCreate(/* ... */) };
// both are type safe
// ArrayReserve() takes typechecked ArrayGeneric*
ArrayReserve(&array.gen,1);
// array.items is of type int*
int item = array.items[0];
Because the two pointers are both the same size and at the same base address of all of their containing types on certain platforms, array.gen.arr and array.items can be used interchangably, on those platforms! (Platforms where all pointers are of equal size and alignment.) Despite being interchangable, they are each usable without typecasting in their various contexts.
But this has sacrificed a great deal in terms of ergonomics, in two ways. First in initialization, nesting the constructor in an initializer is disappointing considering how often arrays themselves are in initializer lists. Second, and much more importantly, the type of this array will not implicitly cast to other identical declarations. i.e.
// Declaration is actually fine here as type of parameter
void UseArray(DECLARE_ARRAY(int) *param_array)
{
/* do something */
}
DECLARE_ARRAY(int) array_1 = { .gen = ArrayCreate(/* ... */) };
// Here's what you can do:
DECLARE_ARRAY(int) array_2 = {.items = array_1.items};
// or
array_2.items = array_1.items;
// The compiler will yell at you about this because c is not duck-typed.
DECLARE_ARRAY(int) array_2 = array_1;
// The compiler will yell at you about this too
UseArray(&array_1);
If you assign by the .items members, it looks to me like incorrect usage, even though it’s not. You can’t cast it without using typeof(), because in DECLARE_ARRAY(int) array_1; the DECLARE_ARRAY(int) is declaring an unnamed bespoke type as part of the definition of variable array_1.
DECLARE_ARRAY(int) array_2 = (/* there's only one/zero thing(s) you can put here*/) array_1;
// this does work in c23 or before that with compiler extensions, but it jetisons type-checking
DECLARE_ARRAY(int) array_2 = (typeof(array_2)) array_1;
// this line declares two separate, bespoke array types that do not cast to one another.
// doesn't work, and would also jetison type-checking if it did
DECLARE_ARRAY(int) array_2 = (DECLARE_ARRAY(int)) array_1;
NOTE: In case
typeof()seems too convenient a solution,typeof()only became a standard language feature (not an compiler extension anymore) in c23, which was adopted in 2024.
Typesafe-ish casting requires you to pass the address of the typed pointer member of the union, and then perform an unsafe cast. One pattern I use in C in situations like this is to try and hide the type unsafe operation behind checked one, or enforce some sort of runtime type check. Unfortunately, I think an RTTI implementation would be cumbersome in this application.
// We lose the explicit array type but the double pointer make malformed passing less likely.
void UseArray(int **param_array)
{
// Lose type-checking entirely on this cast.
DECLARE_ARRAY(int) *array = (typeof(array)) param_array;
/* do something */
}
// ...
DECLARE_ARRAY(int) array_1 = { .gen = ArrayCreate(/* ... */) };
UseArray(&array_1.items);
Although you could then typedef every array type you use, at the moment I have deemed this an unneccesary compromise given the lack of errors I have produced of this form, but I would certainly consider it in a team setting where most people didn’t also write the array library. The above case, resolved with typedefs, would look like this.
typedef DECLARE_ARRAY(int) i_Array;
void UseArray(i_Array *param_array)
{
/* do something */
}
// no complaints from compiler
i_Array array_1 = { .gen = ArrayCreate(/* ... */) };
i_Array array_2 = array_1;
UseArray(&array_1);
// if you're initializing an array that belongs to a struct it will can be initialized
// with the slightly less bad syntax
Thing thing = (Thing)
{
.ids.gen = ArrayCreate(sizeof(*thing.ids.items), 128),
};
This will re-add some of the top of file declarations from the Macro Templates section, away from the point of initialization for the array. If you’re interested in adopting an array of this form, but want some added safety checks, this may be a compromise worth considering.
Next Time
Join me for something easier next time, where we’ll discuss no-pain enums for c.
c c99 c11 c17 c23 development software implementation collections data-structures
3302 Words
2026-09-29 02:00