Type Safe Generic Data Structures in C (2025)
danielchasehooper.com124 points by AlexeyBrin 2 days ago
124 points by AlexeyBrin 2 days ago
I don't understand people reinventing macro-based hacks in C to achieve what was achieved in other languages many years ago. Why not using C++, for example? It's available almost everywhere, introducing its usage in an existing C codebase is pretty simple. Sure, C++ has its own downsides, but is it better to create mess with macros in C rather then using exiting language facilities and standard library containers provided by C++?
Having used C++ a lot in the past, I think the mess in C++ is way worse. I also contribute to projects that introduce C++ into a C code base, and I really wish they hadn't done this.
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.
> the mess in C++ is way worse
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?
> What is mess in 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.
> How do you make a shallow copy of an object in C++
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.
Yeah, and that's the reason why people prefer to write in C.
"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 can’t necessarily do that in C either, it depends on if your object is in a container that relies on pointer stability. Intrusive linked lists are common in C and they get broken by this, for example.
Calling memcpy on any random old struct in C is how you get bugs. If the struct contains other pointers: who is in charge of freeing them? What if the struct has internal pointers (a pointer pointing to a subobject of the struct)? You are playing with fire and you know it.
> And you can always use only features from C++ you find useful.
Ah, the old "programmers just need to be more disciplined when using C++".
Yeah, C programmers have never seen that argument before...
As if C programmers don’t have to be disciplined. Look if you are a C programmer you need to pick good parts of the language to write in as well. A beginner picked gets()? Oh the foes of the young and inexperienced. You picked VLA? Linus would breathe fire unto you.
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.
My macro-vector types are type safe. In fact this is the point.
I do not think C++ is more expressive or type safe.
In C, assigning the return value from malloc() to a specific type merely produces a warning:
$ 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]
No, this counts as C++ is stupid to me. The memory returned by malloc is UNTYPED. The sole reason why void as a type exists is to convey the notion of no type, so that it needs to be assigned to a type by a programmer. If you mean "byte region, please cast before use" that's 'char *'. Since C++ now forces me to write a cast, it effectively forces me to hide and silence errors.
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.
For one reason, it is because C++ runtime (and its standard library) is a whole own can of worms which most people would rather not touch if they can afford to. Which they mostly can.
> 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.
Here we go again. Yes there are bad parts in the C++ standard library and there are good parts. But if you are just trying to do type safe generic data structures you are unlikely to touch the bad parts. Many codebases forbids parts of the standard library, e.g. LLVM forbids including <iostream>. You can forbid using parts of the standard library too.
> Yes there are bad parts in the C++ standard library and there are good parts.
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.
Strings, something that C still doesn't do properly, not even having something like SDS into the standard library.
<map> does the work just fine, not everyone has winning microbenchmarks as part of their daily work.
Many of the big C++ projects I've worked with have custom string types since the standard one was defficient for some reason or another.
Exactly, and a simple usable string type is just a struct MyString { char *buf; size_t len; }; away. Actual magic is in how you use it, where you allocate it, how you integrate allocation and formatting and logging and I/O... i.e. all the things that aren't solved by crufty complex std::string either.
> <map> does the work just fine
It has a rather weird interface, at least until C++ 17 when some of the deficiencies were patched somewhat.
It's a slow generic data structure with an unintuitive API. You can use it for leetcode or for CRUD. For anything more demanding it's horrifically bloated and bad. std::string too. Whenever you see STL datatypes like even string and map, you have to deal with RAII, implicit allocations, weird operator syntax, unexpected mutation (invalidation) and so on.
(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).
> For anything more demanding it's horrifically bloated and bad
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.
> C++ containers are designed for average demands. If you need something more specific, you can always use an alternative implementation.
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?