Re: [Boost-users] [review] intrusive container comments

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-03-21 17:32:06

[This should have been on the dev-list, but ended up here by mistake; 
anyway, let's continue it here]

Ion Gaztañaga skrev:
> Hi Thorsten,
> 
> Thorsten Ottosen wrote:

>> Therefore I think there are compelling reasons for exploring
>> a different design: an extrusive design where the node-structure
>> is not part of the object.
> 
> Interesting. "Extrusive" sounds cool ;-)
> 
>> This happens when all live objects are added to an intrusive container.
>>
>> An example: consider an ilist of size N. The node structure requires two 
>> T* objects and so the space required is
>>
>>   N * 2 * sizeof(T*)
> 
> Ok.
> 
>> An extrusive approach would look a bit like this:
>>
>> template< class T >
>> class extrusive_list
>> {
>>   struct Node
>>   {
>>      T* prev;
>>      T* next;
>>      T* me;

hm...correction:

   struct Node
   {
     Node* prev;
     Node* next;
     T* me;
   };
>>   };
>>   std::vector<Node> nodes;
>> };
>>
>> Thus the space required would be
>>
>>
>>   N * 3 * sizeof(T*)
> 
> When an a node is erased from the container, I suppose you are you going 
> to erase it from the vector (otherwise, you would need to track the free 
> and used Nodes), so depending when the Node was placed (in the beginning 
> or end of the vector), the overhead of an erasure can be high.
> 
> Wait! Another option would be to convert a Node in a union so that free 
> Nodes can form a linked list when they are not used, and add to to 
> extrusive_list a pointer to the first free Node. If there are no free 
> Nodes to reuse, the vector can be safely expanded and the last nodes can 
> form again a linked list of free nodes.

This is good thinking :-) Alternatively I think the index into the 
vector of the first node in the unused list could work.

> But you lose exception safety in 
> insertions, a unique property of intrusive containers, because the 
> needed memory is already allocated.

right; however, the exception-safety could be guaranteed if
the user call's set_capacity() to be large enough to hold the
number of anticipated insertions. Typically you would do
this up front.

>> Let me know what you all think.
> 
> Still not sure about the advantages (and I'm afraid they are not trivial 
> to implement efficiently), but I'm interested in the idea. Are you 
> volunteering to write the alter-ego of Intrusive, Extrusive? Even this 
> Extrusive library would benefit from its evil twin Intrusive ;-)

I'm not volunteering, no. Too busy even to do a proper review of your 
library.

I have zero experience with the normal use cases for intrusive 
containers. What I would like to know is if typically all objects is 
inside intrusive containers; also for the use of 2,3, or 4 simultaneous 
containers.

-Thorsten