Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Intrusive and non-intrusive containers

Differences between intrusive and non-intrusive containers
Properties of Boost.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.

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:

  • 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 bookkeeping 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 situations intrusive 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 management is done with intrusive containers. Memory management usually is not a predictable 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 will 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 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 make 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 the thread safety of a program that uses containers is harder with intrusive containers, because the container might be modified indirectly without an explicit call to a container member.

Table 12.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 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.


PrevUpHomeNext