[boost] Re: Proposal: intrusive containers

From: Jaap Suter (boost_at_[hidden])
Date: 2005-04-03 14:10:43

> I have finished the first version of my STL-like intrusive containers
> More information on:
> http://people.freenet.de/turtle++/intrusive.html

Hi Olaf,

I am using intrusive lists a lot in my work, and I would love to see 
high-quality Boost versions.

I have not looked at your code, but I'm impressed with your write-up, and it 
already addresses many issues. Here are my initial comments and thoughts:

1. Instead of providing the two options of deriving and embedding, let the 
user provide ADL-style 'next' and 'prev' lookup functions that for a given 
type provide hooks to the intrusive containers. Look at the 
boost::intrusive_ptr documentation for more information on this style. You 
can still provide the existing two methods as possible ways of providing 
these hooks, but if my legacy code (or for some other reason) has types with 
their own next and prev pointers, I still want to be able to use your code.

2. As you mention, inserting an object twice leads to problems. In general, 
intrusive lists need to be handled with more care. I would like to see a 
diagnostics mode that checks invariants and preconditions. Things to check 
for would be checking if an instance doesn't already exist on inserts, and 
checking whether there are no loops in a list. Because this will make 
list-manipulation really slow, I'd like to be able to enable this on a 
per-instance basis, probably through boolean-ish or policy-based template 
parameters.

3. I would love to see a single-linked intrusive container that only 
supports forward iteration, as well as a list decorator that turns an 
exiting single or doubly linked list into a ring.

Thanks for the work, it looks very promising!

Regards,

Jaap Suter