Type Safe Generic Data Structures in C (2025)
danielchasehooper.com
danielchasehooper.com
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.
> 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.
I don't know why you are now jumping to setjmp/longjmp, trying to make a point that somehow C is the worst programming languages ever, when all I am trying to argue is for sane programming practices, hinting that more complex features (line especially found in newer languages) are not solutions but part of the complexity problem.
> auto m2 = m; // implicit too
Taking a copy requires making an allocation.
If you find that RAII is a problem, I pity how poor a programmer you must be...
Fully agree, for locks or other simple begin/end pairs it doesn't create the same kind of architectural damage. But I don't use it even there, because RAII fundamentally doesn't play well with manual cleanup code. It's kind of an all-in game, if you use some RAII there are strong forces (whenever you need to get the "nesting" right) to convert all remaining manual begin/end type code to types that define that functionality out-of-line in the destructor/destructor, leading to fragmentation.
I could re-type all the essential stuff from std::string that I've ever used myself within 10 minutes, no problem, without looking up external sources, including copy & move semantics and whatnot. But I'm deliberately not doing it. Because I don't like this "invention".
Plain C strings all over the place.
Since I learnt C in 1990, knowing to count up to 10 is enough, for the amount of times I saw it actually being done.
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.
You left out the part of my comment where I said “pretty trivially” lol. C++ is mostly a superset of C, which is why I’m not arguing that it’s impossible to do these things in C++. I like C++ too, and think some of the things in there are great. But the simplicity of C is nice. I would often get overwhelmed thinking about all the different constructors in C++ and what I needed to do to ensure that I didn’t accidentally tank performance by copying objects around everywhere (and potentially calling some invisible constructor that did extra work in the copy function). In C, I know when I memcpy it’s just gonna move some bytes around.
Overall, I really don’t care all that much one way or the other. But I can see how people could prefer C to C++. I could also see how people prefer C++. I really really miss function overloading and <string.h> when I use C
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.
Nitpick: that isn’t possible anymore. gets was removed from C in C11 (https://en.cppreference.com/c/io/gets)
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.
My understanding is that C has a different understanding of the word warning than other languages. Such as in "stern warning" or "warning: the building will collapse if you take that brick out".
This is a philosophical problem. C has false positives to the question: "Is that a program", and some people find that to be idiotic (I don't, this is why I like C). But this becomes really logical, when you have in mind, that the point is that you do not want to have false negatives.
> Otherwise, if a program contains a violation of any diagnosable rule or an occurrence of a construct described in this document as “conditionally-supported” when the implementation does not support that construct, a conforming implementation shall issue at least one diagnostic message.
The C++ standard does seem to explicitly require the compiler to reject translation units with a failed static_assert. (The requirements for #error are a little confusing; not sure if a failed #error in a conditional block requires failure.) But I couldn't find a rule that mandates failure for invalid implicit int conversions. Implicit pointer to int conversions are invalid for the same reasons in both C and C++. Basically, AFAICT C++'s type safety in this regard is a matter of historical compiler behavior, and now the major C compilers are adopting that behavior, which they previously had allowed (with a mandatory diagnostic message) for backward compatibility reasons.
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?
I am not sure I understand the second question. I do not think compound literals have complex lifetime rules. The lifetime end with the corresponding block, as do other objects in C (one needs to know what a block is, some people confuse this with scope). There is some potential issue which may be surprising when passing them to macros that make use of the statement expression extension, as the lifetime is then limited to the macro body.
I have read up on it, and I do not remember why I arrived at the conclusion that compound literals have complex rules. Their rules are different from C++ and Rust temporaries, but the rules of compound literals are not complex, though their block lifetimes do have to be understood. I have seen at least two C developers being confused about their lifetimes (mostly about when used inside if-statement's condition or in a loop), but most C developers seem to grasp compound literals and their lifetime quickly, and the cppreference.com page is relatively short, which reflects the simplicity of compound literals. It helps that one can understand them as a local variable, local to the specific block that they are used in.
In contrast, C++ and Rust temporary lifetimes can vary, and those lifetime rules can confuse developers, like in https://fasterthanli.me/articles/a-rust-match-made-in-hell .
Mojo seems to avoid many of C++'s and Rust's issues on the topic about lifetimes.
Edit: The trade-off of C compound literals is as far as I can tell that their lifetime is longer than sometimes necessary.
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...
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.
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):...) .
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.
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)
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.
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,.
Microsoft, Google, Apple and co have done the right decision regarding to what extent C is still required on their platforms, when we have Typescript for C for about 40 years.
Now if WG14 was actually doing type safe enumerations, sorting out implicit conversations and arrays decaying into pointers only to save typing 4 additionally characters per location, catching up to PL/I strings and arrays, I might be a bit more positive.
One can wait for WG14 to ever deliver that, assuming it will ever happen, or take the easier way out, and use such features on C++ today.
In reality, we as industry should have long replaced both of them with something better, since Ada and Modula-2 came to be, but alas the industry always takes the easier path, like mountain rivers.
Likewise by 2002, AT&T also decided C had enough of lifetime and started the Cyclone project, which has a great effect in modern type systems.
They might have not won over C, others will, with projects whose influences trace back to where UNIX and C were born, quite ironically.
Which is much more interesting to post about than Modula-2 in 2026.
Examples: https://godbolt.org/z/hecqs78xs https://godbolt.org/z/YnrcjKrEn
Not perfect, but also not really inferior to C++ in my opinion.
Most elements on periodic table is toxic to human.
My comment was pointing out that despite lead being known for millennia as a problem in people, it was used for:
* water delivery pipes * plates and cutlery and cups * a paint ingredient in everyone's home * a sealant * a fuel additive that was spewed into the air by every motor vehical * a lubricant in a lot of machinery * a common additive to many additional products all over the place * a common additive in industrial processes leaving lead residue on products that wouldn't otherwise contain lead.
So the phrase: "underpins most of the technology in the world" somewhat realistically applies to lead - in the early 1900s it was everywhere all the time.
And as i pointed out at the start of this - it is kind of a bad choice to be using all the time in everything since it causes so many problems for people. Humanity has been dramatically reducing the use of lead in everything for a long time now (decades) and will continue to do so for a long time. The bad effects of all the lead use during the industrialization of our species will remain for quite a while.
So my whole point was: just because something was used in the creation of great outcomes, it doesn't make it any good in a fundamental way. I'm saying C is like lead in my analogy.