Intrusive and non-intrusive containers

| Home | Libraries | People | FAQ | More

## Intrusive and non-intrusive containers

### Differences between intrusive and non-intrusive containers

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.

### Properties of Boost.Intrusive containers

Semantically, a Boost.Intrusive container is similar to an 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:

- 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*>`.
- The use of dynamic allocation to create copies of passed values can be a performance and size bottleneck in some applications. Normally, dynamic allocation imposes a size overhead for each allocation to store bookeeping information and a synchronization to protected concurrent allocation from different threads.
- Only copies of objects are stored in non-intrusive containers. Hence copy or move constructors and copy or move assignment operators are required. Non-copyable and non-movable objects can't be stored in non-intrusive containers.
- It's not possible to store a derived object in a STL-container while retaining its original type.

Intrusive containers have some important advantages:

- Operating with intrusive containers doesn't invoke any memory management at all. The time and size overhead associated with dynamic memory can be minimized.
- Iterating an Intrusive container needs less memory accesses than the semantically equivalent container of pointers: iteration is faster.
- Intrusive containers offer better exception guarantees than non-intrusive containers. In some situation intrusives containers offer a no-throw guarantee that can't be achieved with non-intrusive containers.
- The computation of an iterator to an element from a pointer or reference to that element is a constant time operation (computing the position of `T*` in a `std::list<T*>` has linear complexity).
- Intrusive containers offer predictability when inserting and erasing objects since no memory managed is done with intrusive containers. Memory management usually is not a predicable operation so complexity guarantees from non-intrusive containers are looser than the guarantees offered by intrusive containers.

Intrusive containers have also downsides:

- Each type stored in an intrusive container needs additional memory holding the maintenance information needed by the container. Hence, whenever a certain type shall be stored in an intrusive container you have to change the definition of that type appropriately. Although this task is easy with Boost.Intrusive, touching the definition of a type is sometimes a crucial issue.
- In intrusive containers you don't store a copy of an object, but they rather the original object is linked with other objects in the container. Objects don't need copy-constructors or assignment operators to be stored in intrusive containers. But you have to take care of possible side effects, whenever you change the contents of an object (this is especially important for associative containers).
- The user has to manage the lifetime of inserted objects independently from the containers.
- Again you have to be careful: in contrast to STL containers it's easy to render an iterator invalid without touching the intrusive container directly, because the object can be disposed before is erased from the container.
- Boost.Intrusive containers are non-copyable and non-assignable. Since intrusive containers don't have allocation capabilities, these operations have no sense. However, swapping can be used to implement move-capabilities. To ease the implementation of copy constructors and assignment operators of classes storing Boost.Intrusive containers, Boost.Intrusive offers special cloning functions. See Cloning Boost.Intrusive containers section for more information.
- Analyzing thread-safety of a program that uses containers is harder with intrusive containers, becuase the container might be modified indirectly without an explicitly call to a container member.

Table 9.1. Summay 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 hold non-copyable and non-movable objects by value | 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.