[boost] Re: Intrusive containers: second iteration

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2005-05-03 11:20:40

"Marcin Kaliciñski" <kalita_at_[hidden]> wrote in message 
news:d53ven$q88$1_at_sea.gmane.org...
|> 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.

ok, but...

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

I buy the performance goal; I'm just not too comfortable with the intrusive 
approach; It must be posibly to look
at this from a more "view" like perspektive (no pun intended) and integrate it 
with those ideas.

For example,

unintrusve_list<T>

could store strutures of the type

struct Foo
{
    Foo* next, prev;
    T* data;
};

I don't see any extra overhead by making this non-intrusive.

I assume the intrusive approach means that I can only put the elements into 
one list; the non-intrrusive would't have that requirement.

Does it make sense?

-Thorsten