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 value_type. <aside> 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... 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. 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. </aside> -Howard