Boost.Intrusive offers a wide range of intrusive
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.
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.
like intrusive associative containers. The size overhead is moderate for
user classes (usually the size of three pointers). Many operations have logarithmic
Boost.Intrusive also offers pseudo-intrusive
like intrusive unordered associative containers. The size overhead is moderate
for user classes (an average of two pointers per element). Many operations
have an amortized constant time complexity.
Each of these intrusive containers can be configured with constant or linear
Linear time size: The intrusive container
doesn't hold a size member that it's updated with every insertion/erasure.
This implies that the
size() function has not constant time complexity.
On the other hand, the container is smaller, and some operations, like
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 it's updated with every insertion/erasure. This
implies that the
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
Safe mode hooks: Hook constructor initializes
the internal data to a well-known safe state and intrusive containers check
that state before inserting a value in the container. When erasing an element
from the container, the container puts the hook in the safe state again.
This allows a safer use mode and it can be used to detect programming errors.
It implies an slight performance overhead in some operations and can convert
some constant time operations in 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 having any reference 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 pointers. 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
an smart pointer compatible with shared memory, called
Boost.Intrusive can be configured to use
this smart pointer to allow shared memory intrusive containers.