[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