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
Boost.Intrusive offers a wide range of intrusive containers:
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.
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.
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.
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.
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:
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:
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.
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:
Apart from that, Boost.Intrusive offers additional features:
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.
offset_ptr. Boost.Intrusive
can be configured to use this smart pointer to allow shared memory intrusive
containers.