Boost C++ Libraries

The main difference between intrusive containers and non-intrusive containers is that in C++ non-intrusive containers store copies of values passed by the user. Containers use the Allocator template parameter to allocate the stored values:

#include <list>
#include <assert.h>

int main()
{
   std::list<MyClass> myclass_list;

   MyClass myclass(...);
   myclass_list.push_back(myclass);

   //The stored object is different from the original object
   assert(&myclass != &myclass_list.front());
   return 0;
}

To store the newly allocated copy of myclass, the container needs additional data: std::list usually allocates nodes that contain pointers to the next and previous node and the value itself. Something similar to:

//A possible implementation of a std::list<MyClass> node
class list_node
{
   list_node *next;
   list_node *previous;
   MyClass    value; 
};

On the other hand, 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;
   //Other members...
};

int main()
{
   acme_intrusive_list<MyClass> list;

   MyClass myclass;
   list.push_back(myclass);

   //"myclass" object is stored in the list
   assert(&myclass == &list.front());
   return 0;
}

As we can see, knowing which additional data the class should contain is not an easy task. Boost.Intrusive offers several intrusive containers and an easy way to make user classes compatible with those containers.

Semantically, a Boost.Intrusive container is similar to a STL container holding pointers to objects. That is, if you have an intrusive list holding objects of type T, then std::list<T*> would allow you to do quite the same operations (maintaining and navigating a set of objects of type T and types derived from it).

A non-intrusive container has some limitations:

Intrusive containers have some important advantages:

Intrusive containers have also downsides:

For a performance comparison between Intrusive and Non-intrusive containers see Performance section.