[boost] Re: Intrusive containers: second iteration

From: Marcin Kaliciñski (kalita_at_[hidden])
Date: 2005-05-01 20:29:41

> struct Link
> {
>    Link* prev, next;
> };
>
> So if you say the library is about performance, then I assume Link's 
> cannot be
> heap-allocated; so
> where are they allocated?

Nowhere. They are part of the object stored in the container. STL containers 
(apart from array-like ones such as vector) have structures that are 
external to the object. For example std::list has 1 node for every object 
stored in it. Thus, you have 2 allocations per each object in std::list - 
one for object itself and another one for its node. Putting prev and next 
pointers into the object makes the node no longer neccessary.

Intrusive containers also have several other advantages:
- adding object into container does not require making copies
- one object can be in more than one intrusive container at once

I've seen a lot of libraries written in C using this sort of approach, and 
also tried to write some in C++ but got nowhere close to Olaf. Where 
performance is critical, this is the right choice. It would be great if we 
had standarized intrusive containers in boost.

cheers,
M.