Re: [boost] [intrusive] Intrusive containers library strikes back

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2006-09-18 10:57:56

Kevin Sopp wrote:

> Hi,
> I'm working on an intrusive dynamic multi-index container.
> I've got some code working which allows me to add sequential views
> at runtime. I wondered as well if it was possible to share code for common
> operations in these containers. AFAIK pointer containers are just adaptors
> over standard containers.

Sharing core operations is definitely a good idea. But that will also 
set dependencies that you might want to avoid. For example one could 
imagine these dependencies(-> means depends on):

multi_index -> intrusive_multi_index -> intrusive
                                          ^
                                          |
             interprocess_containers  ----

I don't know if Joaquín would want to add more dependencies to 
multi_index. Maybe this also limits the Joaquin's development rate.

Anyway, the basic features I would like to have in this core operations are:

-> list (doubly linked), rb tree, slist(singly linked) algorithms.
-> Support for non-raw pointers.

Based on these algorithms, it would nice to have these basic intrusive 
classes:

-> list (with optional constant-time size)
-> slist (with optional constant-time size)
-> set/rbtree (with optional constant-time size)
-> multiset/rbtree
-> unordered_set
-> unordered_multiset

Olaf's code has also options implemented as policies:

-> Node destructor might automatic unlink the node from the container
-> Container destructor might automatic unlink all the nodes

Olaf's offers also 3 type of accessors to make a class intrusive-capable:

-> Derivation from accessor
-> Member accessor
-> Legacy accessor (for ilist)

Member accesor has a performance penalty and I don't know if people 
would like to use it.

Perhaps we should outline a layered approach to see which features each 
library needs a have common code library.

Regards,

Ion