Type Safe Generic Data Structures in C (2025) (danielchasehooper.com)
Panzerschrek 8 hours ago
Joker_vD 8 hours ago
> 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.
kccqzy 8 hours ago
Joker_vD 8 hours ago
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.
pjmlp 8 hours ago
<map> does the work just fine, not everyone has winning microbenchmarks as part of their daily work.
Joker_vD 7 hours ago
It has a rather weird interface, at least until C++ 17 when some of the deficiencies were patched somewhat.
jstimpfle 7 hours ago
(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).
Panzerschrek 6 hours ago
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.
jstimpfle 6 hours ago
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
> in C++ it's strictly recommended to mark as const everything in regular user code which shouldn't be mutated.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?
Panzerschrek 5 hours ago
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).
jstimpfle 5 hours ago
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.
pif 6 hours ago
If you find that RAII is a problem, I pity how poor a programmer you must be...
jstimpfle 6 hours ago
kccqzy 5 hours ago
jstimpfle 21 minutes ago
accelbred 7 hours ago
jstimpfle 7 hours ago
kccqzy 6 hours ago
accelbred 7 hours ago
jeffbee 7 hours ago
accelbred 7 hours ago
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.
jeffbee 6 hours ago
1: https://github.com/llvm/llvm-project/commit/905a88b923433eb8...
rwbt 8 hours ago
pjmlp 8 hours ago
accelbred 7 hours ago
uecker 8 hours ago
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.
Panzerschrek 7 hours ago
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?
_gabe_ 6 hours ago
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.
Panzerschrek 5 hours ago
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.
mpweiher 2 hours ago
1718627440 2 hours ago
"That's not how things are done in C++" I like C, because I can just decide for myself how things are done here.
variadix 5 hours ago
kccqzy 2 hours ago
lelanthran 6 hours ago
Ah, the old "programmers just need to be more disciplined when using C++".
Yeah, C programmers have never seen that argument before...
kccqzy 2 hours ago
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.
uecker 6 hours ago
I do not think C++ is more expressive or type safe.
ranger_danger 4 hours ago
$ 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]
Whereas in C++ it's a hard error: $ 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]
Does this not count as "more type safe" to you?1718627440 2 hours ago
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.
josephg an hour ago
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.
0xbadcafebee 7 hours ago
psyclobe 6 hours ago
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.
tliltocatl 5 hours ago
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).
coolThingsFirst 4 hours ago
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.
lor_louis 10 hours ago
https://louissven.xyz/article/how_I_do_container_types_in_C....
Feel free to flag/delete if this isn't the place.
rramadass 6 hours ago
It is really nice that you studied both Martin Uecker and Daniel Hooper's techniques and tweaked them to suit your ideas/taste.
tniemi 10 hours ago
Still feels a bit like a party trick, but if it works...
Xirdus 9 hours ago
JdeBP 8 hours ago
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):...) .
dang 2 hours ago
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)
add2 an hour ago
mkehrt 6 hours ago
randomNumber7 8 hours ago
pjmlp 8 hours ago
uecker 8 hours ago
randomNumber7 7 hours ago
The article uses a struct with a VLA as the last element.
uecker 7 hours ago
lukasgelbmann 7 hours ago
Flexible array members don’t allocate a dynamic amount of memory on the stack.
uecker 7 hours ago
david2ndaccount 4 hours ago
#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 no
`typedef`s with side effects...randomNumber7 7 hours ago
uecker 5 hours ago
ActorNightly 3 hours ago
Because 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.
veexx103 10 hours ago
just as was done with C++?
pjmlp 9 hours ago
nikbackm 9 hours ago
peesem 9 hours ago
christophilus 8 hours ago
pjmlp 8 hours ago
krior 7 hours ago
peesem 4 hours ago
pornel 7 hours ago
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.
actionfromafar 6 hours ago
SAI_Peregrinus 3 hours ago
rramadass 6 hours ago
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.
FullGarden_S 7 hours ago
accelbred 7 hours ago
lelanthran 4 hours ago
ActorNightly 3 hours ago
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.
rramadass 10 hours ago
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.
podocarp 10 hours ago
david2ndaccount 8 hours ago
warmwaffles 7 hours ago
uecker 7 hours ago
rramadass 7 hours ago
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.
david2ndaccount 6 hours ago
ranger_danger 4 hours ago
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).
carlos256 9 hours ago
pjmlp 9 hours ago
uecker 8 hours ago
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.
pjmlp 7 hours ago
We will keep on agreeing to disagree.
uecker 7 hours ago
I could tolerate it if it were at least some interesting criticism,.
nice_byte 9 hours ago
loeg 7 hours ago
uecker 7 hours ago
Examples: https://godbolt.org/z/hecqs78xs https://godbolt.org/z/YnrcjKrEn
Not perfect, but also not really inferior to C++ in my opinion.
0xbadcafebee 7 hours ago
esafak 6 hours ago
0xbadcafebee 3 hours ago
sophacles 6 hours ago
jeltz 5 hours ago