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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk