Confusion about one element in more boost::intrusive containers

Question

I don't quite understand how it is possible that the same elements can appear in different intrusive containers while preserving the performance and memory usage guarantees that the boost::intrusive documentation states.

The documentation says that:

an intrusive container does not store copies of passed objects, but it stores the objects themselves. The additional data needed to insert the object in the container must be provided by the object itself. For example, to insert MyClass in an intrusive container that implements a linked list, MyClass must contain the needed next and previous pointers:

class MyClass
{
   MyClass *next;
   MyClass *previous;
   // ...
};

When underlining the differences between STL and boost::intrusive containers, the documentation also says:

A non-intrusive container has some limitations:

An object can only belong to one container: If you want to share an object between two containers, you either have to store multiple copies of those objects or you need to use containers of pointers: std::list<Object*>.

Makes sense, an element can't be in two std::lists. Okay. But how can one instance of type MyClass be inserted in two different boost::intrusive::list 's, for example, considering that such an element can only have one pointer to the next element and one to the previous element. If I am not wrong, this only works if you assume that modifying one container might also modify the other one and vice-versa.

Answer 1

The Boost.Intrusive library doesn't litterally ask you to define prev and next pointers -- in that part of the documentation, the presence of prev and next pointers is merely a conceptual illustration of how intrusive containers work.

The actual of defining intrusive containers is to include a hook through inheritance or as a member that contains the prev and next pointers. By including several hooks (tagged with different static types), you can include the same object in several differnet intrusive containers (each tagged with different static types).

See http://www.boost.org/doc/libs/1_38_0/doc/html/intrusive/usage.html to see how the hooks work. See this StackOverflow answer for an example of how to do this with multiple intrusive contianers.

This has some limitations -- you can't include your objects in an arbitrary set of multiple intrusive containers defined at runtime -- you have to know what containers you want to use when you're coding them initially, and build knowledge of each one into your objects.