| I really prefer intrusive data structures, for the exact reasons outlined in the article. I've myself written many implementations of intrusive structures. But now I'd like to present the greatest of them, a super-generic implementation of an intrusive AVL tree in C. See [1], and example [2]. - It relies on a user-defined concept of a "link". In particular, this means the structure can be in an array and linked with array indices, and can be copied correctly with a single memcpy. Of course the user may still use pointers as links. - It supports implementation of user-defined associative operations (e.g. sum). This consists of operations:
CAvl_AssocSum: Calculate the sum of all the nodes.
CAvl_ExclusiveAssocPrefixSum: Calculate the sum of elements from the first one up to but not including node X.
CAvl_FindLastExclusiveAssocPrefixSumLesserEqual: Find the first node where the sum of all preceding nodes is >=X.
Of course these all have O(log n) time complexity. - The implementation is made generic by include files which rely on macros a lot. Other than the macro madness, I think this is better then C++ templates, due to easy #if, where in templates one would need to jump through hoops due to non-existence of static_if. [1] https://github.com/ambrop72/badvpn/tree/master/structure (see CAvl_*
[2] https://github.com/ambrop72/badvpn/blob/master/examples/cavl... (also see cavl_test_tree.h in the same dir defining some parameters for the structure) |
And either throw away type safety completely or end up with a huge macro soup (which is even worse to debug than template soup). I also don't understand your static_if remark.
I'm not saying intrusive lists are never useful but saying that intrusive lists are generally better than the STL is just terrible advice.
I'm not a huge fan of C++ but if there's something I miss dearly when writing C it's generic containers.