DEV Community

Rowen
Rowen

Posted on

Implementing C++ STL containers in pure C — what I learned

#algorithms #c #cpp #showdev

I've been experimenting with implementing C++ STL-style containers (vector, list, deque, set, map, stack, queue, priority_queue, unordered_set, unordered_map) as a single-header C library using C99 macros and variadic dispatch.

The goal was to see how close you can get to the C++ STL interface in pure C — same function names like push_back, insert, erase, find, begin/end — without requiring a C++ compiler.

A few interesting design challenges came up:

1. Bracket access (v[i])

For VECTOR and DEQUE, the handle is just a <type>* pointing into the data region, so v[i] works naturally as pointer arithmetic. Metadata (size, capacity) is stored before the pointer address. This also means you can pass a vector directly to qsort or bsearch with no wrapper.

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 10; i++)
    push_back(v, i);

qsort(v, size(v), sizeof(int), my_cmp);  // just works
printf("%d", v[3]);                       // bracket access
destroy(v);
Enter fullscreen mode Exit fullscreen mode

2. Variadic overloading in C

Using macro argument counting, different parameter counts dispatch to different behaviors:

insert(v, v + 3, 777);       // insert single value at position
insert(v, v + 5, 3, 999);    // insert N copies at position
Enter fullscreen mode Exit fullscreen mode

This mimics C++ overloading without _Generic per se — it's purely preprocessor-driven dispatch based on argument count.

3. Uniform API across container types

The same insert, erase, find names work across all container types. A single macro routes to the correct implementation based on the container's internal tag. Node-based containers (list, set, map) use next(it) / prev(it) for iteration instead of it++.

// Dijkstra with VECTOR + PRIORITY_QUEUE
typedef struct { int cost, to; } Edge;

int compare_edge(const void *a, const void *b) {
    return ((Edge*)a)->cost > ((Edge*)b)->cost ? -1
         : ((Edge*)a)->cost < ((Edge*)b)->cost;
}

int *dijkstra(Edge **graph, int src) {
    VECTOR(int) dist = new_vector(int);
    QUEUE(Edge) pq = new_priority_queue(Edge, compare_edge);
    assign(dist, size(graph), 99999);
    dist[src] = 0;
    push(pq, (Edge){0, src});

    while (!empty(pq)) {
        Edge e = top(pq); pop(pq);
        for (int i = 0; i < size(graph[e.to]); i++) {
            int next_to = graph[e.to][i].to;
            int new_cost = dist[e.to] + graph[e.to][i].cost;
            if (dist[next_to] > new_cost) {
                dist[next_to] = new_cost;
                push(pq, (Edge){new_cost, next_to});
            }
        }
    }
    destroy(pq);
    return dist;
}
Enter fullscreen mode Exit fullscreen mode

Compiler compatibility was another rabbit hole — getting this to work across MSVC, GCC, Clang, MinGW64, icx-cc, and TCC required quite a bit of conditional preprocessing, especially around __VA_ARGS__ handling differences.

Source is here if anyone wants to look at the macro internals: https://github.com/springkim/OpenCSTL

Curious what people think about this approach. Has anyone else tried building STL-like abstractions in C? What tradeoffs did you hit? I'm especially interested in opinions on the metadata-before-pointer trick for bracket access — it works well but feels a bit cursed.

Top comments (0)