Type Safe Generic Data Structures in C (2025)
danielchasehooper.com
danielchasehooper.com
> Sure, C++ has its own downsides
"Sure, getting your eyes gouged out has its downsides, but is it better to read that awful mess of macros in C instead?" The answer most people would give to this question may surprise you.
Okay, other than <vector>, what are the good parts? Because as the sibling comments rightfully point out, migrating your codebase from C to C++ just to be able to use <vector> is not worth it.
The <map> is a sad joke played upon the C++ programmers by the standard committee.
<map> does the work just fine, not everyone has winning microbenchmarks as part of their daily work.
It has a rather weird interface, at least until C++ 17 when some of the deficiencies were patched somewhat.
(Spporting or even encouraging destructive mutation, and by this I mean not incrementing counters or anything harmless but allowing iterator invalidations and crashes, are also why std::vector is bad in my opinion, these are idiomatic APIs for 90s and 2000s programming, which we should know better to avoid in 2026).
C++ containers are designed for average demands. If you need something more specific, you can always use an alternative implementation. And it's better than messing with macros in pure C.
> you have to deal with RAII
What's problematic with it?
> implicit allocations
Allocations aren't implicit. It's usually clear from the documentation where allocation takes place (like in concatenating strings or copying strings).
> unexpected mutation (invalidation)
It's not the case with standard library containers. Mutating methods aren't const-qualified, so that it's clear where mutation can take place. And in C++ it's strictly recommended to mark as const everything in regular user code which shouldn't be mutated.
As someone who has been programming exclusively in C/C++ for a long time -- the biggest selling point for these languages in 2026 is exactly being suited to doing something specific, not generic.
> Allocations aren't implicit
std::map<int,int> m;
m[1] = 42; // implicit alloc
auto m2 = m; // implicit too
Theory and practice. Making everything const correct is too painful in practice, often impossible. It's a trap for bean counters that can't focus on getting some actual useful work done. I'm being harsh to my own past self here. Counter question: why include allocation mechanics with some existing data that never gets changed? Why should we have to add much more boilerplate to get the simpler thing?
operator[] of associative containers is mutating and may allocate. It's mentioned in the documentation. And there is no operator[] overloading for const instances, so that you can't trigger an allocation by just reading elements from it.
> auto m2 = m; // implicit too
Taking a copy requires making an allocation. Do you expect some other behavior in such case?
> Making everything const correct is too painful in practice, often impossible
Maybe you are dealing with some legacy codebase (from 90s)? I have worked with multiple codebases in past 10 years or so and keeping things which shouldn't be mutated const wasn't a problem at all. All the code was written using such approach.
> why include allocation mechanics with some existing data that never gets changed
I don't think I fully understand this question. What never gets changed? In your example you are mutating a container and taking a copy of it (which can be changed later).
No, just saying this stuff is implicit and thus hard to read. More so the allocation on indexing assignment. and keeping things which shouldn't be mutated const wasn't a problem at all.
> and keeping things which shouldn't be mutated const wasn't a problem at all.
As soon as datastructures become more complicated and more interconnected, it's not clear anymore what const should even mean (issues are similar as with deep vs shallow copies, how do you even draw the lines, where are the objects?).
And the major philosophical flaw in the const vs. non-const distinction is that to make a strict separation you have to move everything mutable into constructor calls (for the most part, not getting more into the weeds of C++). Which is very awkward, it's a real tradeoff you need to be aware of. I realized only after playing these games for a long time what a waste of time it is and how much complexity it creates.
If you find that RAII is a problem, I pity how poor a programmer you must be...
Also std::start_lifetime_at is a hack and ive seen nobody using it in all the placed where it aught to be used.
If optimizing based on object lifetimes could be turned off, itd be turned off everywhere for hardening like strict aliasing is.
1: https://github.com/llvm/llvm-project/commit/905a88b923433eb8...
Although there are C features I like that I would need to remove before introducing C++ to a codebase, so this may not always be so simple.
What is mess in C++? Yes, it has some shady parts and is more complex than C, but this complexity provides expressiveness and type safety. And you can always use only features from C++ you find useful.
> also contribute to projects that introduce C++ into a C code base, and I really wish they hadn't done this.
What is problematic in these projects other than unfamiliarity of C++ for developers previously used only C?
Just a couple examples:
How do you make a shallow copy of an object in C++, how do you do the same thing in C? Knowing I can just memcpy _any_ struct in C and have a valid shallow copy is pretty huge.
How do you create a stable ABI in C++? How do you make one in C? In C, knowing that all my exported functions will mostly just work and be stable as long as I don’t change the interface is also huge and allows you to create cross language bindings pretty trivially.
Shallow copies aren't generally possible for classes storing something indirectly, since it violates ownership semantics. That's not how things are done in C++.. Operator = is usually used for making copies, which is optimized to memcpy for POD structures, but for something more complex may perform extra work for doing an actual deep copy.
> How do you create a stable ABI in C++
It's a complex topic. Basic ABI for calling functions is identical to C. But one need to keep in mind, that type layouts and internal implementations of library types (like containers) may differ from implementation to implementation and from version to version.
> knowing that all my exported functions will mostly just work and be stable as long as I don’t change the interface
Nothing prevents you doing this in C++. You can have C-style external interface and use all goods of C++ internally.
"That's not how things are done in C++" I like C, because I can just decide for myself how things are done here.
Ah, the old "programmers just need to be more disciplined when using C++".
Yeah, C programmers have never seen that argument before...
A difference between C++ programmers and C programmers is that C++ programmers have the awareness to know their language has bad parts to avoid, but C programmers are oblivious to the bad parts until someone uses it, but otherwise sing paeans for the language.
I do not think C++ is more expressive or type safe.
$ echo -ne "#include <stdlib.h>\nint foo() { return malloc(42); }" | gcc -xc -fsyntax-only -c -
<stdin>: In function ‘foo’:
<stdin>:2:20: warning: returning ‘void *’ from a function with return type ‘int’ makes integer from pointer without a cast [-Wint-conversion]
$ echo -ne "#include <stdlib.h>\nint foo() { return malloc(42); }" | gcc -xc++ -fsyntax-only -c -
<stdin>: In function ‘int foo()’:
<stdin>:2:26: error: invalid conversion from ‘void*’ to ‘int’ [-fpermissive]
I do want an error when I violate types, I do not want it for void, because that's the whole meaning of void. C++ manages to make it the worst of both worlds.
I’m mostly happy with implicit casts from void* to int* or something. But in this code example, we see an implicit cast from void* to int, casting the pointer itself into a number that might not even fit the pointer. This is rarely what you want. I’d much rather explicit casts in this case.
Also, a question for a C expert like you, uecker: In your opinion, does the compound literals feature have complex lifetimes rules or complex semantic rules otherwise?
Usually the way we do it here is we honor some interface then rewrite the subsystem in c++.
And then there's the real hurdle and that is getting the c++ idiom correct as it is very easy to just open the floodgates and let everyone write code that looks vastly different.
Also, template metaprogramming is way more arcane than C macros. And I need compile-time metaprogramming in leu of dynamic allocation. So C macros it is for now (Zig is promising but still not there yet).
Problem is C++ has many features which I likely won't be able to understand in this lifetime. But using C-style C++ is nuts.
Just the extra of STL is basically the C that C should have been. It's a shame not to have a string type or use brittle macros.
These macro tricks (from the article) are not about recreating C++ in C. C is less opinionated (comp. to C++): it gives you fewer built-in abstractions; does not prescribe which DS dev. should use. It is bring-your-own-data-structures language. Bring whatever you choose. In C, newer language standard is not always better. Older lang standards support more platforms. There is a certain beauty in writing in an old language while still applying modern coding practices.
I like C. I don't hate other languages. I wouldn't use C for apps that should have been written in C# with WinForms...
https://louissven.xyz/article/how_I_do_container_types_in_C....
Feel free to flag/delete if this isn't the place.
It is really nice that you studied both Martin Uecker and Daniel Hooper's techniques and tweaked them to suit your ideas/taste.
Still feels a bit like a party trick, but if it works...
I actually thought from the title before I read the article that it was going to use _Generic, as in something like _Generic((item),__typeof__((list)->payload):...) .
I write type-safe generic data structures in C - https://news.ycombinator.com/item?id=44425461 - June 2025 (182 comments)
Type-safe generic data structures in C - https://news.ycombinator.com/item?id=26735655 - April 2021 (52 comments)
just as was done with C++?
As soon as you change anything in a breaking way, start requiring your own compiler/transpiler, or introduce new idioms, you end up losing the things that keep C alive.
Users of C either like it exactly the way it is, or have to use a specific C version due to a vendor dependency or compliance.
An upgraded C not approved by the standards body gives you yet another niche language that is not C, but is still burdened with its old flaws.
I really don't understand why people bring up other languages when one is discussing implementation of some "advanced/tricky/hackish/new" features in C. It is not as if the implementer does not know about the ease of availability in other languages but there is always some set of criteria which prevents switching to a new language.
On a related note, there is a dearth of written/learning material (books etc.) cataloging and explaining advanced architecture/design/implementation patterns in C though we know they exist in the tons of industrial-strength codebases out there.
There is also the fact that when you see an implementation in C of some feature from another language you better understand language design pragmatics eg. implementing inheritance and virtual functions in C gives you insight into how they work in C++/Java/C#/etc.
For example, when I worked on writing embedded software for autopilots, we had 2 files, common.so and common.h that contained essentially a super robust typing framework. The way it worked is that you defined types through the provided functions at the beginning of your code, and all of the definitions were stored and checked at runtime at the beginning before the main execution loop took effect. So basically taking what a more robust language compiler would do and just moving that processing to the start of execution.
I use something similar for my local llm setup at home, where i can have my agent basically write tools for itself and when the tool fails, the error code makes it pretty easy for the agent to fix.
The article uses a struct with a VLA as the last element.
Flexible array members don’t allocate a dynamic amount of memory on the stack.
#include <stdio.h>
#include <stddef.h>
void v(int y[printf("hello world!\n")]){
}
int main(){
v(NULL);
typedef int wut[printf("oh no\n")];
}
$ cc vla.c && ./a.out
hello world!
oh noBecause in the flip side, you get C++ templates, which are turing complete, so you can write entire program syntax that the compliler executies during the complie process.
He also has other interesting C techniques, namely;
Adding reflection to C - https://news.ycombinator.com/item?id=49964525
_Generic for Type Reification in C - https://www.davidpriver.com/creification.html
See also his C2y interpreter with REPL named "DrC" for the upcoming C29 standard (https://en.wikipedia.org/wiki/C29_(C_standard_revision)) - https://github.com/drpriver/drc
PS: I really like his style of writing and presentation; concise and precise without unnecessary fluff and page beautifying.
I also posted your "Adding Reflection to C" at https://news.ycombinator.com/item?id=49964525 and hope HN picks up on it and has a decent discussion.
You definitely should add a detailed post on your "DrC" compiler/interpreter; usecase, scope, techniques used etc. Since this is looking forward to C2y/C29 with some more extensions, i think people will enjoy playing with it in the REPL format.
What I'd really like is a standards-conformant (C++98/03) compiler that actually enforces the standard properly (or maybe it becomes a new standard), and ONLY allows that version to be used, AND only the classes.
No templates, no exceptions, no standard library (just use a plain libc).
But if you compare some C++ template container to a C macro solution, I also do not find the macro solution to be more complex.
We will keep on agreeing to disagree.
I could tolerate it if it were at least some interesting criticism,.
Examples: https://godbolt.org/z/hecqs78xs https://godbolt.org/z/YnrcjKrEn
Not perfect, but also not really inferior to C++ in my opinion.