Howard Hinnant wrote:
It always amuses me when Ion *knows* I'm lurking. :-) Caught red- handed again!
Something related to containers/move semantics/performance is just too attractive to ignore ;-)
And I haven't been lurking quite closely enough to know if this matters, but in both CodeWarrior and gcc the value_type is elided from the embedded end node. I.e. a node_base is actually embedded which contains only the links, and node derives from node_base and adds the value_type.
The same happens with Intrusive. The user derives or stores a hook to make the class intrusive-friendly. The hook contains a minimum generic node that just stores pointers. All the low-level (link, unlink, rebalance...) algorithms operate with these minimal nodes to avoid instantiating algorithms for all user types. The end node is a minimal node. When the user access to the real value (for example dereferencing an iterator), a downcasting or similar transformation is done to obtain the whole value from the minimal node.
std::list<my_data, my_allocator<my_data>> l; char buffer[sizeof(my_node)] a_node; // alignment magic... l.get_allocator().set_allocate(&a_node); l.push_back(a_node.data_);
or something along those lines (I'm going from memory). It was very low level and my_data_ was a pod, so I didn't have to worry about double constructing and such. It worked pretty well performance wise, but was admittedly pretty ugly and I couldn't claim it was portable.
<advertisement> The philosophy behind Intrusive was to build something that would make building STL-like containers trivial. It's also a way to extract all the common code unrelated to object construction so that we could easily construct new value_types using copy construction, move construction or even in-place construction, reusing the same binary code to insert them in the container. As an experiment, I've implemented all Interprocess node containers using Intrusive, so I think Intrusive offers enough functions to do so. </advertisement> Regards, Ion