The behavior of list.h essentially boils to downcasting from a list node to its container. Allowing multiple list nodes in the same container, and re-use of the same node for different lists. How do templates make this type-safe?
By using composition instead of inheritance, it avoids the downcasting.
If you want to, you can even have objects that are elements in several different lists using tag types to let the compiler keep the lists from getting cross-linked. Or you may prefer to use the node pointers for different things at your discretion.
Self-removal on destruction can be useful too. All without any more run-time overhead than the two pointers you need in C.
I tried reading the code in intrusive/list_hook.hpp and intrusive/list.hpp, and it's quite difficult to read. However, it does seem that it inserts an extra pointer to the member (beyond the prev/next) in order to avoid the "cast". If it indeed does so, it is again less optimal than Linux's list.h. On 64-bit machines, 8 extra bytes for each list element is not always negligible.
Also, the examples do not showcase using the same list member node to put in multiple lists. There's also the unsafety of putting the list node in a union (mentioned in the article) which adds unsafety regardless of templates or not.
I agree about destructors improving safety, I was specifically talking about templates.
With list.h, it is possible to get the same safety (unless I am misunderstanding something about the boost example) by wrapping the list anchor and node structs with a struct (typically done by a macro to define the anchor/node), which adds an array-of-0-elements of the type of the container. This allows adding the same type checks demonstrated here using templates, implemented in the list iteration, insertion/deletion and downcasting macros.
I tried reading the code in intrusive/list_hook.hpp and intrusive/list.hpp, and it's quite difficult to read.
Yeah those Boost projects sometimes go off the deep end with the overengineering and abstraction a bit.
However, it does seem that it inserts an extra pointer to the member (beyond the prev/next) in order to avoid the "cast".
If it's a true C++ pointer-to-member often those can be completely optimized out if the compiler has the type information available at the time.
I've done a (much simpler) intrusive DLL template that certainly did not have that additional pointer, but I'm not sure if it met all of your requirements. I know it supported membership in multiple lists, but I don't think they were heterogeneous collections.
If it indeed does so, it is again less optimal than Linux's list.h. On 64-bit machines, 8 extra bytes for each list element is not always negligible.
Agree, I'm all for performance. At least when I'm on that kind of project.
Also, the examples do not showcase using the same list member node to put in multiple lists.
For that you could derive from multiple base hooks with different tag classes, or compose multiple member_hook<class T, class Hook, Hook T::* PtrToMember>. Each would have a different PtrToMember, but it would be known at compile time and thus should be optimize-outable.
There's also the unsafety of putting the list node in a union (mentioned in the article) which adds unsafety regardless of templates or not.
Boost has a safe type-discriminated union class you could probably use for that if you wanted to.
With list.h, it is possible to get the same safety (unless I am misunderstanding something about the boost example) by wrapping the list anchor and node structs with a struct (typically done by a macro to define the anchor/node), which adds an array-of-0-elements of the type of the container. This allows adding the same type checks demonstrated here using templates, implemented in the list iteration, insertion/deletion and downcasting macros.
Perhaps you could add an array of size 1 to represent the element data following the last pair of pointers. Or I may not be understanding this. Can you point me to an example online?
