Presenting Boost.Intrusive containers

Boost.Intrusive offers a wide range of intrusive containers:

slist: An intrusive singly linked list. The size overhead is very small for user classes (usually the size of one pointer) but many operations have linear time complexity, so the user must be careful if he wants to avoid performance problems.
list: A std::list like intrusive linked list. The size overhead is quite small for user classes (usually the size of two pointers). Many operations have constant time complexity.
set/multiset/rbtree: std::set/std::multiset like intrusive associative containers based on red-black trees. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.
avl_set/avl_multiset/avltree: A std::set/std::multiset like intrusive associative containers based on AVL trees. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.
splay_set/splay_multiset/splaytree: std::set/std::multiset like intrusive associative containers based on splay trees. Splay trees have no constant operations, but they have some interesting caching properties. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.
sg_set/sg_multiset/sgtree: A std::set/std::multiset like intrusive associative containers based on scapegoat trees. Scapegoat can be configured with the desired balance factor to achieve the desired rebalancing frequency/search time compromise. The size overhead is moderate for user classes (usually the size of three pointers). Many operations have logarithmic time complexity.

Boost.Intrusive also offers semi-intrusive containers:

unordered_set/unordered_multiset: std::tr1::unordered_set/std::tr1::unordered_multiset like intrusive unordered associative containers. The size overhead is moderate for user classes (an average of two pointers per element). Many operations have amortized constant time complexity.

Most of these intrusive containers can be configured with constant or linear time size:

Linear time size: The intrusive container doesn't hold a size member that is updated with every insertion/erasure. This implies that the size() function doesn't have constant time complexity. On the other hand, the container is smaller, and some operations, like splice() taking a range of iterators in linked lists, have constant time complexity instead of linear complexity.
Constant time size: The intrusive container holds a size member that is updated with every insertion/erasure. This implies that the size() function has constant time complexity. On the other hand, increases the size of the container, and some operations, like splice() taking a range of iterators, have linear time complexity in linked lists.

To make user classes compatible with these intrusive containers Boost.Intrusive offers two types of hooks for each container type:

Base hook: The hook is stored as a public base class of the user class.
Member hook: The hook is stored as a public member of the user class.

Apart from that, Boost.Intrusive offers additional features:

Safe mode hooks: Hook constructor initializes the internal node to a well-known safe state and intrusive containers check that state before inserting a value in the container using that hook. When erasing an element from the container, the container puts the node of the hook in the safe state again. This allows a safer use mode and it can be used to detect programming errors. It implies a slight performance overhead in some operations and can convert some constant time operations to linear time operations.
Auto-unlink hooks: The hook destructor removes the object from the container automatically and the user can safely unlink the object from the container without referring to the container.
Non-raw pointers: If the user wants to use smart pointers instead of raw pointers, Boost.Intrusive hooks can be configured to use any type of pointer. This configuration information is also transmitted to the containers, so all the internal pointers used by intrusive containers configured with these hooks will be smart pointers. As an example, Boost.Interprocess defines a smart pointer compatible with shared memory, called offset_ptr. Boost.Intrusive can be configured to use this smart pointer to allow shared memory intrusive containers.

Boost C++ Libraries

Presenting Boost.Intrusive containers