"Marcin Kaliciñski" <kalita@poczta.onet.pl> wrote in message news:d53ven$q88$1@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