Boost C++ Libraries

Boost.Intrusive should be a valuable tool in performance sensitive environments, and following this guideline, Boost.Intrusive has been designed to offer well known complexity guarantees. Apart from that, some options, like optional constant-time, have been designed to offer faster complexity guarantees in some functions, like slist::splice.

The advanced lookup and insertion functions for associative containers, taking an arbitrary key type and predicates, were designed to avoid unnecessary object constructions.

Boost.Intrusive should be useful in space constrained environments, and following this guideline Boost.Intrusive separates node algorithms and intrusive containers to avoid instantiating node algorithms for each user type. For example, a single class of red-black algorithms will be instantiated to implement all set and multiset containers using raw pointers. This way, Boost.Intrusive seeks to avoid any code size overhead associated with templates.

Apart from that, Boost.Intrusive implements some size improvements: for example, red-black trees embed the color bit in the parent pointer lower bit, if nodes are two-byte aligned. The option to forgo constant-time size operations can reduce container size, and this extra size optimization is noticeable when the container is empty or contains few values.

Boost.Intrusive can be a basic building block to build more complex containers and this potential has motivated many design decisions. For example, the ability to have more than one hook per user type opens the opportunity to implement multi-index containers on top of Boost.Intrusive.

Boost.Intrusive containers implement advanced functions taking function objects as arguments (clone_from, erase_and_dispose, insert_check, etc.). These functions come in handy when implementing non-intrusive containers (for example, STL-like containers) on top of intrusive containers.

Boost.Intrusive offers a wide range of containers but also allows the construction of custom containers reusing Boost.Intrusive elements. The programmer might want to use node algorithms directly or build special hooks that take advantage of an application environment.

For example, the programmer can customize parts of Boost.Intrusive to manage old data structures whose definition can't be changed.