Boost logo

Boost :

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-19 14:05:24

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.

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.



Boost list run by bdawes at, gregod at, cpdaniel at, john at