Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk