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.