...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. The size overhead is moderate for
user classes (usually the size of three pointers). Many operations have logarithmic
time complexity.
Boost.Intrusive also offers pseudo-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 an amortized constant time complexity.
Each of these intrusive containers can be configured with constant or linear time size:
size()
function has not 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:
offset_ptr
.
Boost.Intrusive can be configured to use
this smart pointer to allow shared memory intrusive containers.