Boost logo

Boost :

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

"Marcin Kaliciñski" <kalita_at_[hidden]> wrote in message
|> 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,


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?


Boost list run by bdawes at, gregod at, cpdaniel at, john at