When designing Boost.Intrusive the following guidelines have been taken into account:
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,
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 wants 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 possibility to avoid constant-time size operations can save some size on containers, and this extra size optimization is noticeable when the container is empty or contains few values.
Boost.Intrusive should be a basic building block to build more complex containers and this guideline has motivated many design decisions. For example, the possibility to have more than one hook per user type opens the possibility to implement multi-index containers on top of Boost.Intrusive.
Boost.Intrusive containers implement advanced
functions taking function objects as arguments (
insert_check...). These functions come
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 programer might want to use node algorithms directly or build special hooks that take advantage of its application environment.
For example, the programmer can use can customize parts of Boost.Intrusive to manage old data structures whose definition can't be changed.