Boost logo

Boost :

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2007-03-18 19:55:33

On Mar 18, 2007, at 8:10 AM, Ion Gaztañaga wrote:

> //Imagine list allocates the "end" node using the allocator
> std::list<MyObject> list;
> //If we want list to be usable after being moved
> //we must COPY the allocator and ALLOCATE a new
> //end node. Both operations might throw!
> std::list<MyObject> list2(std::move(list));
> Howard can correct me if I'm wrong but I think the Metrowerks/
> Freescale
> implementation of std containers using move semantics store the end
> node
> inside the container to achieve no throw guarantee in default
> construction and move operations in node containers.

It always amuses me when Ion *knows* I'm lurking. :-) Caught red-
handed again!

Yes, the CodeWarrior Freescale list, map, multimap, set, multiset use
the embedded end-node technique. And it is possible this issue is
about to come to a head, not sure. Fwiw, gcc 4.x also uses the same
technique (but I claim CodeWarrior was there first :-)). And yes, I
think this design for node-based STL containers is far superior to the
heap-allocated end node.

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

I once did an intrusive std::list, using the CodeWarrior std::list
implementation by using a custom allocator. I told the allocator
where to allocate the next node and it just did so. The allocator had
to have knowledge of the node layout for the std::list, making it not
really officially portable. But how many node layouts could there be
in practice?

struct my_node
     my_node* prev_;
     my_node* next_;
     my_data_ data_;


std::list<my_data, my_allocator<my_data>> l;
char buffer[sizeof(my_node)] a_node; // alignment magic...

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.
Fwiw, the application was malloc/free (never actually shipped). I
managed the memory blocks in the malloc heap using std::list -
intrusively, one list node per memory block.


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