...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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:
std::list<Object*>
.
Intrusive containers have some important advantages:
T*
in a std::list<T*>
has linear complexity).
Intrusive containers have also downsides:
Table 19.1. Summary of intrusive containers advantages and disadvantages
Issue |
Intrusive |
Non-intrusive |
---|---|---|
Memory management |
External |
Internal through allocator |
Insertion/Erasure time |
Faster |
Slower |
Memory locality |
Better |
Worse |
Can insert the same object in more than one container |
Yes |
No |
Exception guarantees |
Better |
Worse |
Computation of iterator from value |
Constant |
Non-constant |
Insertion/erasure predictability |
High |
Low |
Memory use |
Minimal |
More than minimal |
Insert objects by value retaining polymorphic behavior |
Yes |
No (slicing) |
User must modify the definition of the values to insert |
Yes |
No |
Containers are copyable |
No |
Yes |
Inserted object's lifetime managed by |
User (more complex) |
Container (less complex) |
Container invariants can be broken without using the container |
Easier |
Harder (only with containers of pointers) |
Thread-safety analysis |
Harder |
Easier |
For a performance comparison between Intrusive and Non-intrusive containers see Performance section.