[boost] Re: Proposal: intrusive containers

From: Olaf Krzikalla (krzikalla_at_[hidden])
Date: 2005-04-04 15:26:18

Hi,

thank you and the others for the positive feedback.

Jaap Suter wrote:
> 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.
Interestingly enough, the motivation for the intrusive containers came 
from legacy stuff. And in an initial approach I tried to use legacy prev 
and next, but failed. But today I tried it again and it was quite easy. 
Some things just need time. You can now download a new version, there is 
a new legacy accessor. As I've also stated on the page, I think, that 
this legacy accessor will actually fits most of the needs (btw, it seems 
to be the fastest accessor, too [not measured yet]) and hence will be 
renamed shortly.

> 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.
Checking for correctness will be always a crucial thing in C++, because 
the speed caveat is often an issue. And intrusive containers are no 
exceptions. So I still hesitate to add checks. But policy-based checks 
are a possibility.

> 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.
Interesting ideas. An islist is of course a natural extension, since 
intrusive containers will be used in environments with spare ressources.

All in all, I still have to collect ideas. It seems, that in the end 
there will be some full-fledged policy-based intrusive containers.

Best regards
Olaf Krzikalla