[boost] Re: Proposal: intrusive containers

From: Daniel James (daniel_at_[hidden])
Date: 2005-04-03 15:02:46

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.

I'm not sure about this, most of the difficulty is involved in 
manipulating the links - iterator adaptor or facade can be used to 
easily create iterators for types with their own next and prev pointers.

> 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.

If there was a check that a node wasn't in a container on insertion 
wouldn't these problems disappear?

Daniel