C doesn't come with dynamic data structures like vectors or hashmaps, so developers have to either develop their own on top of arrays and structs, or use an external library.

One of the most popular data structure libraries is stb_ds.h. It's a very easy to use single-header library that feels almost like Javascript arrays, but I was getting frustrated with its design.

First, iteration relies on index calculations, which is a slower technique than pointer comparison (that's what std::vector uses).

Second, the structure hides its array header behind the data pointer. This is done to allow for the square brackets syntax [ ], but it turns debugging into a horrible experience since we can't easily access the header, and this technique relies on undefined behavior which is unreliable, especially when using less popular compilers on different systems.

Third, stb_ds.h doesn't do bounds checking, so it silently corrupts memory out-of-bounds access. This is the worst possible way to manage errors, but C is limited on that department.

Fourth, stb_ds.h isn't fully type-safe. It relies on sizeof (a) for type-checking, but it's possible to pass different pointer types (char, double), different primitives of the same size (int, float), or different structs of the same size (struct { node next; }, struct { float x; float y; }) to violate the type contract. The user must enforce type-safety themselves.

Fifth, I personally do not like its licensing because MIT forbids re-licensing, and public domain is ambiguous internationally.

So I decided to make my own single-header vector library to fix all of those issues.

My vector library (vector.h) uses the same iteration technique as std::vector (3 pointers, one for the beginning of the array/elements, one for past the last element, and one past the last valid memory index). This results in faster iteration (which is the most common array usage), clearer debugging with all values being in the struct, and no undefined behavior surprises.

vector.h also panics on errors instead of silently corrupting memory. This may seem like a bad design decision, but lots of popular languages crash on out-of-bounds access (Rust, Go, GDScript, etc.). It's almost always a severe bug, and it's best to let the developer know by failing fast. But for those who cannot afford a crash, I implemented the flag VECTOR_NO_PANIC_ON_OOB that turns out-of-bounds access into no-ops.

The type-safety requirement was the trickiest to solve, but I landed on macro-generated functions. This is similar to what the Linux kernel sometimes uses like `list.h`, but Linux compiles with gnu89 which includes typeof(), while my vector is strict c89 ISO compliant, which doesn't have typeof().

Finally, for licensing, I chose the BSD Zero-Clause license which allows for re-licensing, is internationally unambiguous, and doesn't require attribution.

To make my library production ready, I included a robust test routine.

I'd love feedback from C developers who've struggled with similar issues. Code and benchmarks at https://github.com/RolandMarchand/vector.h

The Lowest Level PL

Comments