CC

es are maximally aligned - which they will be if they're dynamically allocated - it doesn't matter whether the pointer we store to the list head is ListNode *, type *, void *, or any other regular pointer type.) The union approach has the same drawback as the struct approach: untagged unions are not compatible with each other, so we have to typedef the container in advance in order to pass in and out of functions (as noted in the article). This is broadly similar to the drawback from which the "generic headers" approach (which I usually call the "pseudo-template" approach) suffers, namely the need for boilerplate from the user. However, the generic-headers/pseudo-template approach is guaranteed to generate the most optimized code thanks to function specialization[1], and it can be combined with another technique to provide a non-type-prefixed API, as I discuss here[2] and demonstrate in practice here[3]. I'd also like to point to my own approach to generics[4] that is similar to the one described here in that it hides extra type information in the container handle's type - information that is later extracted by the API macros and passed into the relevant functions. My approach is different in that rather than exploiting unions, it exploits functions pointers' ability to hold multiple types (i.e. the return type and argument types) in one pointer. Because function pointers are "normal" C types, this approach doesn't suffer from the aforementioned typedef/boilerplate problem (and it allows for API macros that are agnostic to both element type/s and container type). However, the cost is that the code inside the library becomes rather complex, so I usually recommend the generic-headers/pseudo-template approach as the one that most people ought to take when implementing their own generic containers. [1] https://gist.github.com/attractivechaos/6815764c213f38802227... [2] https://github.com/JacksonAllan/CC/blob/main/articles/Better... [3] https://github.com/JacksonAllan/Verstable [4] https://github.com/JacksonAllan/CC

map ); insert( &our_map, 5, 0.5f ); printf( "%f\n", *get( &our_map, 5 ) ); cleanup( &our_map ); } CC is the only C data-structure library that offers such ergonomics, to the best of my knowledge. Of course, performance is also important. To this end, CC's hash tables (i.e. its maps and sets) have performed well in benchmarks both by me[2] and by others.[3] Its red-black trees (i.e. its ordered maps and sets) have also been benchmarked and proven to perform on par with their C++ Standard Library counterparts.[4] Some of the techniques upon which CC relies are explained briefly in its FAQ[5] and more thoroughly in a series of Reddit comments that I made back when the library was first released.[6] I am working on a series of articles to describe these techniques more systematically, the first of which I published earlier.[7] Thanks for reading! [1] https://github.com/JacksonAllan/CC#rationale [2] https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/ [3] https://gist.github.com/attractivechaos/6815764c213f38802227... [4] https://github.com/JacksonAllan/CC/releases/tag/v1.3.0 [5] https://github.com/JacksonAllan/CC?tab=readme-ov-file#how-do... [6] https://www.reddit.com/r/C_Programming/comments/zvubfb/comme... [7] https://github.com/JacksonAllan/CC/blob/main/articles/Better...

st argument of the // outermost get has none: printf( "%f", *get( get( &our_map, 456 ), 0 ) ); // The "proper", albeit cumbersome, way to achieve the same thing without a // warning: vec( float ) *itr = get( &our_map, 456 ); printf( "%f", *get( itr, 0 ) );

ifying arguments as "inline". IIRC, this library uses this style of generic programming with a very nice API: https://github.com/JacksonAllan/CC It's just unfortunate that everything needs to get inlined for good performance.

grow/rehash at 0.85-0.9): https://strong-starlight-4ea0ed.netlify.app/ Tsl, Martinus, and CC are all Robin Hood tables (https://github.com/Tessil/robin-map, https://github.com/martinus/robin-hood-hashing, and https://github.com/JacksonAllan/CC, respectively). Absl (from Google) and Boost are well-known C++ SIMD-based hash tables. Khash (https://github.com/attractivechaos/klib/blob/master/khash.h) is, I think, an ordinary open-addressing table using quadratic probing. Fastmap is a new, yet-to-be-published design that is fundamentally similar to bytell (https://www.youtube.com/watch?v=M2fKMP47slQ) but also incorporates some aspects of the aforementioned SIMD maps (in particular, it stores a 4-bit fragment of the hash code to avoid most false key comparisons). As you can see, all the Robin Hood maps spike upwards dramatically as the load factor gets high, becoming as much as 5-6 times slower at 0.95 vs 0.5 in one of the benchmarks (uint64_t key, 256-bit struct value: Total time to erase 1000 existing elements with N elements in map). Only the SIMD maps (with Boost being the clear better performer of the two) and Fastmap appear mostly immune to load factor in all benchmarks, although the SIMD maps do - I believe - use tombstones for deletion in at least some cases. I’ve only read briefly about bi-directional linear probing – never experimented with it.