3 ms·
That’s one of the few places that genuinely itch in my C experience, but I haven’t seen it solved anywhere, even partially. The hard part is, there are a myria
by mananaysiempre 4y ago
That’s one of the few places that genuinely itch in my C experience, but I haven’t seen it solved anywhere, even partially.
The hard part is, there are a myriad tiny variations of each data structure, especially the simplest ones (even prehistoric Knuth vol 1 lists a dozen of versions of a linked list); the C practice is generally to write the most appropriate one in each case (because there is no reason to value a premade one if you don’t have any, and because manual implementation makes to want and appreciate those small affordances that pointer-to-head / dummy-head / cyclic pointer-to-head / cyclic dummy-head / etc. give you). This does not always work well, both because it forces you to optimize with little data, and because natural laziness can lead you to avoid a marginally more complex data structure for longer than you really should (and possibly have the laziness-induced inefficiency be lost and forgotten).
But it does give working with data structures in C a certain feel and style that I haven’t seen reproduced with reusable implementations. When a language uses those, it’s either by choosing a small set of structures and running with them (Lua, Awk, Python, perhaps Tcl as a more interesting example) or by parametrizing everything to the hilt (C++ and D). Even in C, the language more steers you towards rolling your own than forces it (cue qsort & bsearch, BSD and Linux macros, etc.). Yet the small set is frequently too small, and the One Implementation to rule them all is bloated far beyond the mental capacity of a single person and still too inflexible.
Honestly, if there is something I’d like from a C successor, it’s reproducing the hand-rolled-data-structure style without the actual hand rolling (in most cases), and that’s as much a library feature as a language one. I can name a lot of other things I’d like to see in my low-level language, but if I had to choose one improvement, that would be it. So far, I haven’t seen a convincing attempt.
- anonymoushn 4y agoThe Zig standard library includes some commonly used data structures, and the perfect time to add your favorites or to improve the APIs of the existing ones is before 1.0 :)
- kubb 4y agoBlog post idea: how to build a zig library with an extern C API that provides access to a Zig data structure, build it, link it in a C program and use it from C.
- tialaramex 4y agoOne of the things Gankra (I think it was her?) did a long time ago for Rust before 1.0 was pull out all the more esoteric data structures which had lived in its standard library and banish them to separate crates. Does somebody need an LRU cache? Yes. But unlike say, a HashSet most people will never need one even if you explain what it's for. The standard library has a high maintenance cost. It's only worth it to pay that cost for data structures people need all the damn time, and for vocabulary types. Fewer people will ever need ControlFlow than HashSet, but having it in the standard library means everybody is agreed that's ControlFlow, there's no risk two popular things invent their own. If two popular Rust crates invent their own LRU cache nobody's day is ruined. Because C is really old, it's understandable that K&R went really light on the standard library. I can't forgive their terrible string, or the garbage built-in array type, but I can totally imagine in the 1970s it's a lot to ask that the standard library should have say, hash tables. Today it isn't and your language should have them.