| ▲ | Type Safe Generic Data Structures in C(danielchasehooper.com) |
| 113 points by AlexeyBrin 2 days ago | 79 comments |
| |
|
| ▲ | Panzerschrek 3 hours ago | parent | next [-] |
| 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++? |
| |
| ▲ | psyclobe an hour ago | parent | next [-] | | Its rather hard to introduce c++ into legacy c projects. You basically have to decide on a subset of features to use, and then you'll have to explain to the teams why the same looking code now takes 10x more compute to build. 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. | |
| ▲ | uecker 3 hours ago | parent | prev | next [-] | | 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. | | |
| ▲ | Panzerschrek an hour ago | parent [-] | | > 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? | | |
| ▲ | _gabe_ an hour ago | parent | next [-] | | > 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. | | |
| ▲ | Panzerschrek 23 minutes ago | parent [-] | | > 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. |
| |
| ▲ | lelanthran an hour ago | parent | prev | next [-] | | > 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... | |
| ▲ | uecker 31 minutes ago | parent | prev [-] | | My macro-vector types are type safe. In fact this is the point. I do not think C++ is more expressive or type safe. |
|
| |
| ▲ | Joker_vD 3 hours ago | parent | prev | next [-] | | 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. | | |
| ▲ | kccqzy 3 hours ago | parent [-] | | 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. | | |
| ▲ | Joker_vD 3 hours ago | parent | next [-] | | > 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. | | |
| ▲ | pjmlp 3 hours ago | parent | next [-] | | 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. | | |
| ▲ | accelbred 2 hours ago | parent | next [-] | | 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. | | |
| ▲ | jstimpfle 2 hours ago | parent [-] | | 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. |
| |
| ▲ | Joker_vD 2 hours ago | parent | prev [-] | | > <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. | | |
| ▲ | jstimpfle 2 hours ago | parent [-] | | 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). | | |
| ▲ | Panzerschrek an hour ago | parent | next [-] | | > 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. | | |
| ▲ | jstimpfle an hour ago | parent [-] | | > 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
> 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 16 minutes ago | parent [-] | | > m[1] = 42; // implicit alloc 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). |
|
| |
| ▲ | pif an hour ago | parent | prev [-] | | > you have to deal with RAII If you find that RAII is a problem, I pity how poor a programmer you must be... | | |
| ▲ | jstimpfle an hour ago | parent [-] | | You must be very experienced to be so judgemental! But maybe ask the many billions of voxels that get tested per second on my multithreaded and SIMD'ed cutting simulation. | | |
| ▲ | kccqzy 16 minutes ago | parent [-] | | C++ is the best language to write multi-architecture SIMD without relying on compiler magics like autovectorization. It gives you enough tools to define zero-cost abstractions to make SIMD nice. |
|
|
|
|
| |
| ▲ | kccqzy an hour ago | parent | prev [-] | | So what? You like <vector>, and make it the only allowed include. Write all other type safe generic data structures by hand using C++ syntax. Problem solved. In fact many old codebases migrated from C already has their own implementations of strings and vectors and hash tables, so these projects can totally forbid the C++ standard library versions in favor of their own versions, and only pull in <type_traits> for easier type safe generic data structure programming. |
| |
| ▲ | accelbred 2 hours ago | parent | prev [-] | | You cant touch C++ without bringing the object lifetime stuff in. And unlike strict aliasing, theres no flag to turn it off. | | |
| ▲ | jeffbee 2 hours ago | parent [-] | | Object lifetime is the entire point of C++ and it solves ~100% of the emergent flaws in C programs. | | |
| ▲ | accelbred 2 hours ago | parent [-] | | I was just dealing with this: https://bugs.gentoo.org/show_bug.cgi?id=974323. 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 an hour ago | parent [-] | | In my personal opinion, the fix[1] for that issue clearly implicates C-style habits polluting a C++ code base. No right-thinking knower of C++ initializes objects with memset! Also I believe that -Wall would have flagged that, and I know for certain that cppcoreguidelines-init-variables + cppcoreguidelines-pro-type-member-init would have flagged it. 1: https://github.com/llvm/llvm-project/commit/905a88b923433eb8... |
|
|
|
|
| |
| ▲ | rwbt 3 hours ago | parent | prev | next [-] | | I'd rather not migrate my C codebase to C++ just to use an array container. Very hard to consistently limit the codebase to a strict subset of C++. | | |
| ▲ | pjmlp 3 hours ago | parent [-] | | It is called a linter, more devs should learn to use a tool that was originally created for C in 1979. | | |
| ▲ | accelbred 2 hours ago | parent [-] | | The only decent linters I know of for C++ are clang-tidy and coverity and they are not good enough. |
|
| |
| ▲ | tliltocatl 21 minutes ago | parent | prev | next [-] | | Not sure why author does it, but I use C over C++ for one reason: I'd rather not have random hidden malloc() scattered in my code. And no, it's not about latency or performance. Once my code takes an yet unexplored part and runs out of 200kB RAM, the will be no way for me to learn about it - running out of memory will bring down both the logger and the radio link, which is the only way to get the logs from a sensor installed twenty meters above ground in a hazardous environment facility. C may be unsafe, but most errors short of "writing to a random memory area" are either well-contained or at least reproducible. Dynamic memory allocation means that anything may crash everything. Manageable if you have a MMU and can contain crashes within isolated heap, but if not - I'd rather not bother. And yea, you can write zero-allocation C++ code, but why bother if most of STL is now unusable? And you get some new and exciting UB modes (seriously, no union aliasing, what the heck?) 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). | |
| ▲ | 0xbadcafebee 2 hours ago | parent | prev [-] | | If you want better tires on your car, why not just get a different car? |
|
|
| ▲ | lor_louis 5 hours ago | parent | prev | next [-] |
| I wrote a summarizing article on type safe container types a while back, but
with some C23 specific changes and a few tweaks to work better for complex types. https://louissven.xyz/article/how_I_do_container_types_in_C.... Feel free to flag/delete if this isn't the place. |
| |
| ▲ | rramadass an hour ago | parent [-] | | Thanks for sharing. It is really nice that you studied both Martin Uecker and Daniel Hooper's techniques and tweaked them to suit your ideas/taste. |
|
|
| ▲ | mkehrt 36 minutes ago | parent | prev | next [-] |
| I absolutely cannot remember the details, but we did typesafe, macro based generic data structures in C in an undergrad class I took ~20 years ago (CMU Operating Systems). The idea has definitely been around, though I don't know if the implantation was the same. |
|
| ▲ | tniemi 5 hours ago | parent | prev | next [-] |
| That `(1 ? (item) : (list)->payload)` was a neat trick. It gets optimized away, but the type comparison happens before that. Still feels a bit like a party trick, but if it works... |
| |
| ▲ | JdeBP 3 hours ago | parent | next [-] | | It's somewhat of a forced trick nowadays, I think. 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):...) . | |
| ▲ | Xirdus 4 hours ago | parent | prev [-] | | Expressions that compile but never evaluate are bread and butter in C++ template metaprogramming. |
|
|
| ▲ | veexx103 5 hours ago | parent | prev | next [-] |
| Is it feasible to create a new language by adding features to C just as was done with C++? |
| |
| ▲ | pornel 2 hours ago | parent | next [-] | | It's not worth it. The value of C is in compatibility, availability of compilers, and familiarity. 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. | | |
| ▲ | rramadass an hour ago | parent | next [-] | | Well said. 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. | |
| ▲ | actionfromafar an hour ago | parent | prev [-] | | It would be nice to have something like C which was very much like C and Pascal (not the syntax) but which was basically C except no naked pointers by default etc, fewer footguns, but which would generate C. |
| |
| ▲ | pjmlp 4 hours ago | parent | prev | next [-] | | And Objective-C, yet somehow people reinvent them badly in C. | |
| ▲ | accelbred 2 hours ago | parent | prev | next [-] | | I am working on a language that was C with extensions, transpiled to plain C, but the C syntax is kinda not great to work with (stuff like needing type tables and unbounded lookahead). At the point you clean up the syntax, you're not really C with extensions anymore. | |
| ▲ | FullGarden_S 2 hours ago | parent | prev | next [-] | | C3 might be it because C3 has full C ABI compatibility so unlike most modern C-like alternatives, it checks out. | |
| ▲ | nikbackm 4 hours ago | parent | prev [-] | | There are already plenty of such languages, Zig among others. | | |
|
|
| ▲ | randomNumber7 3 hours ago | parent | prev | next [-] |
| As far as I know many C programmers think the addition of variable length arrays in C99 was a mistake. What would be the downside of this approach? |
| |
| ▲ | pjmlp 3 hours ago | parent | next [-] | | So much so, that it was made optional annex in C11, while Google paid to remove all their use from the Linux kernel. | |
| ▲ | uecker 2 hours ago | parent | prev [-] | | I do not get the connection with a VLA in this context, but if you need a VLA, by all means use it. It is basically always better than the alternative. | | |
| ▲ | randomNumber7 2 hours ago | parent [-] | | > I do not get the connection with a VLA in this context The article uses a struct with a VLA as the last element. | | |
| ▲ | uecker 2 hours ago | parent [-] | | I see. This array of unknown length at the end of a struct is called a flexible array member and not a variable length array (although it also refers to an array of variable length it is a different language feature). | | |
| ▲ | lukasgelbmann 2 hours ago | parent | next [-] | | Yes, and variable length arrays were made an optional part of the standard in C11. Whereas flexible array members remain a standard required feature. Flexible array members don’t allocate a dynamic amount of memory on the stack. | | |
| ▲ | uecker 2 hours ago | parent | next [-] | | VLAs are supported by basically all modern C compilers though, and I do not think adding them was a mistake (I certainly use them a lot!). They got a bad reputation due to stack clash attacks, but in the past some compilers did not implement stack probing (clang was very late). But this was fixed a decade ago. | |
| ▲ | 2 hours ago | parent | prev [-] | | [deleted] |
| |
| ▲ | randomNumber7 an hour ago | parent | prev [-] | | What happens when I put a variable of a struct type that contains a flexible array member on the stack? | | |
| ▲ | uecker 24 minutes ago | parent [-] | | The array has size 0. In GNU C, you can initialize it and then it has a fixed size corresponding to the initializer. |
|
|
|
|
|
|
| ▲ | rramadass 5 hours ago | parent | prev | next [-] |
| Also see Templates in C by David Priver - https://www.davidpriver.com/ctemplates.html 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. |
| |
| ▲ | david2ndaccount 3 hours ago | parent | next [-] | | Hey that’s me! Cool to see people like my stuff. | | |
| ▲ | rramadass 2 hours ago | parent | next [-] | | You should write more ;-) 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 31 minutes ago | parent [-] | | I agree. Alas I have a day job and my other hobby is going for long hikes. But when the days get shorter and the weather is worse I’ll write some more! |
| |
| ▲ | warmwaffles 2 hours ago | parent | prev [-] | | I do wish to see comptime stuff in C some day. Or at a minimum your `defblock` implemented. I am so tired of having to escape new lines. | | |
| |
| ▲ | podocarp 5 hours ago | parent | prev [-] | | Lol at some point just implement a small compiler in C… reflection is kinda a hilarious thing to have like I understand the use case for generics, since it's not that that that hard to do with macros and quite commonly wished for |
|
|
| ▲ | carlos256 4 hours ago | parent | prev | next [-] |
| Jesus, I hate those macro hacks so much. Most of the time you only need a single container, so writing an ad-hoc implementation is cleaner than that. |
| |
| ▲ | pjmlp 4 hours ago | parent [-] | | The extent some will go to avoid touching C++. | | |
| ▲ | uecker 3 hours ago | parent [-] | | Indeed. After having suffered from C++ a lot, I am also really avoid touching it if I can. 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 2 hours ago | parent [-] | | I would not expect any other kind of answer. We will keep on agreeing to disagree. | | |
| ▲ | uecker 2 hours ago | parent [-] | | The difference between me and you is that I do not usually post under C++ articles something negative about C++. Instead I respect that people interested in C++ may have their own reasons. For some reason you find it appropriate to post something negative under each C article. I could tolerate it if it were at least some interesting criticism,. |
|
|
|
|
|
| ▲ | nice_byte 4 hours ago | parent | prev [-] |
| I've tried doing this for a few years and it just sucks ass. Just use c++ and templates if you need proper generic data structures. C is a defective language. |
| |
