2 / Copyright (c) 2006-2013 Ion Gaztanaga
4 / Distributed under the Boost Software License, Version 1.0. (See accompanying
5 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8 [library Boost.Intrusive
10 [authors [Krzikalla, Olaf], [Gaztanaga, Ion]]
11 [copyright 2005 Olaf Krzikalla, 2006-2013 Ion Gaztanaga]
14 [purpose Intrusive containers]
16 Distributed under the Boost Software License, Version 1.0.
17 (See accompanying file LICENSE_1_0.txt or copy at
18 [@http://www.boost.org/LICENSE_1_0.txt])
22 [section:introduction Introduction]
24 [section:introduction_presenting Presenting Boost.Intrusive]
26 [*Boost.Intrusive] is a library presenting some intrusive containers to
27 the world of C++. Intrusive containers are special containers
28 that offer [link intrusive.performance better performance]
29 and exception safety guarantees than non-intrusive containers (like STL containers).
31 The performance benefits of intrusive containers makes them ideal as a building
32 block to efficiently construct complex containers like multi-index containers or
33 to design high performance code like memory allocation algorithms.
35 While intrusive containers were and are widely used in C, they
36 became more and more forgotten in C++ due to the presence of the standard
37 containers which don't support intrusive techniques.[*Boost.Intrusive] wants to
38 push intrusive containers usage encapsulating the implementation in
39 STL-like interfaces. Hence anyone familiar with standard containers can easily use
44 [section:introduction_building_intrusive Building Boost.Intrusive]
46 There is no need to compile anything to use [*Boost.Intrusive], since it's
47 a header only library. Just include your Boost header directory in your
48 compiler include path.
54 [section:intrusive_vs_nontrusive Intrusive and non-intrusive containers]
56 [section:differences_intrusive_vs_nontrusive Differences between intrusive and non-intrusive containers]
58 The main difference between intrusive containers and non-intrusive containers is
59 that in C++ non-intrusive containers store [*copies] of values passed by the user.
60 Containers use the `Allocator` template parameter to allocate the stored values:
69 std::list<MyClass> myclass_list;
72 myclass_list.push_back(myclass);
74 //The stored object is different from the original object
75 assert(&myclass != &myclass_list.front());
80 To store the newly allocated copy of `myclass`, the container needs additional
81 data: `std::list` usually allocates nodes that contain pointers to the
82 next and previous node and the value itself. Something similar to:
86 //A possible implementation of a std::list<MyClass> node
95 On the other hand, an intrusive container does not store copies of passed objects,
96 but it stores the objects themselves. The additional data needed to insert the object
97 in the container must be provided by the object itself. For example, to insert `MyClass`
98 in an intrusive container that implements a linked list, `MyClass` must contain the
99 needed ['next] and ['previous] pointers:
112 acme_intrusive_list<MyClass> list;
115 list.push_back(myclass);
117 //"myclass" object is stored in the list
118 assert(&myclass == &list.front());
122 As we can see, knowing which additional data the class should contain is not
123 an easy task. [*Boost.Intrusive] offers several intrusive containers and an easy
124 way to make user classes compatible with those containers.
128 [section:properties_of_intrusive Properties of Boost.Intrusive containers]
130 Semantically, a [*Boost.Intrusive] container is similar to a STL container
131 holding pointers to objects. That is, if you have an intrusive list holding
132 objects of type `T`, then `std::list<T*>` would allow you to do quite the
133 same operations (maintaining and navigating a set of objects of type T and
134 types derived from it).
136 A non-intrusive container has some limitations:
138 * An object can only belong to one container: If you want to share an object
139 between two containers, you either have to store multiple copies of those
140 objects or you need to use containers of pointers: `std::list<Object*>`.
142 * The use of dynamic allocation to create copies of passed values can be a performance
143 and size bottleneck in some applications. Normally, dynamic allocation imposes
144 a size overhead for each allocation to store bookkeeping information and a
145 synchronization to protected concurrent allocation from different threads.
147 * Only copies of objects are stored in non-intrusive containers. Hence copy
148 or move constructors and copy or move assignment operators are required. Non-copyable
149 and non-movable objects can't be stored in non-intrusive containers.
151 * It's not possible to store a derived object in a STL-container while
152 retaining its original type.
154 Intrusive containers have some important advantages:
156 * Operating with intrusive containers doesn't invoke any memory management at all.
157 The time and size overhead associated with dynamic memory can be minimized.
159 * Iterating an Intrusive container needs less memory accesses than the semantically
160 equivalent container of pointers: iteration is faster.
162 * Intrusive containers offer better exception guarantees than non-intrusive containers.
163 In some situations intrusive containers offer a no-throw guarantee that can't be
164 achieved with non-intrusive containers.
166 * The computation of an iterator to an element from a pointer or reference to that element
167 is a constant time operation (computing the position of `T*` in a `std::list<T*>` has
170 * Intrusive containers offer predictability when inserting and erasing objects since no
171 memory management is done with intrusive containers. Memory management usually is not a predictable
172 operation so complexity guarantees from non-intrusive containers are looser than the guarantees
173 offered by intrusive containers.
175 Intrusive containers have also downsides:
177 * Each type stored in an intrusive container needs additional memory holding the
178 maintenance information needed by the container. Hence, whenever a certain type will
179 be stored in an intrusive container [*you have to change the definition of that type]
180 appropriately. Although this task is easy with [*Boost.Intrusive], touching the
181 definition of a type is sometimes a crucial issue.
183 * In intrusive containers you don't store a copy of an object, [*but rather the original object
184 is linked with other objects in the container]. Objects don't need copy-constructors or assignment
185 operators to be stored in intrusive containers. But you have to take care of possible side effects,
186 whenever you change the contents of an object (this is especially important for
187 associative containers).
189 * The user [*has to manage the lifetime of inserted objects] independently from the
192 * Again you have to be [*careful]: in contrast to STL containers [*it's easy to render an
193 iterator invalid] without touching the intrusive container directly, because the object
194 can be disposed before is erased from the container.
196 * [*Boost.Intrusive] containers are [*non-copyable and non-assignable]. Since intrusive
197 containers don't have allocation capabilities, these operations make no sense. However,
198 swapping can be used to implement move capabilities. To ease the implementation of
199 copy constructors and assignment operators of classes storing [*Boost.Intrusive]
200 containers, [*Boost.Intrusive] offers special cloning functions. See
201 [link intrusive.clone_from Cloning Boost.Intrusive containers] section for more information.
203 * Analyzing the thread safety of a program that uses containers is harder with intrusive containers, because
204 the container might be modified indirectly without an explicit call to a container member.
206 [table Summary of intrusive containers advantages and disadvantages
207 [[Issue] [Intrusive] [Non-intrusive]]
208 [[Memory management] [External] [Internal through allocator]]
209 [[Insertion/Erasure time] [Faster] [Slower]]
210 [[Memory locality] [Better] [Worse]]
211 [[Can hold non-copyable and non-movable objects by value] [Yes] [No]]
212 [[Exception guarantees] [Better] [Worse]]
213 [[Computation of iterator from value] [Constant] [Non-constant]]
214 [[Insertion/erasure predictability] [High] [Low]]
215 [[Memory use] [Minimal] [More than minimal]]
216 [[Insert objects by value retaining polymorphic behavior] [Yes] [No (slicing)]]
217 [[User must modify the definition of the values to insert] [Yes] [No]]
218 [[Containers are copyable] [No] [Yes]]
219 [[Inserted object's lifetime managed by] [User (more complex)] [Container (less complex)]]
220 [[Container invariants can be broken without using the container] [Easier] [Harder (only with containers of pointers)]]
221 [[Thread-safety analysis] [Harder] [Easier]]
224 For a performance comparison between Intrusive and Non-intrusive containers see
225 [link intrusive.performance Performance] section.
231 [section:usage How to use Boost.Intrusive]
233 If you plan to insert a class in an intrusive container, you have to make some decisions
234 influencing the class definition itself. Each class that will be used in an intrusive
235 container needs some appropriate data members storing the information needed by the
236 container. We will take a simple intrusive container, the intrusive list
237 ([classref boost::intrusive::list boost::intrusive::list]), for the following
238 examples, but all [*Boost.Intrusive] containers are very similar. To compile
239 the example using [classref boost::intrusive::list boost::intrusive::list],
244 #include <boost/intrusive/list.hpp>
246 Every class to be inserted in an intrusive container, needs to contain a hook that
247 will offer the necessary data and resources to be insertable in the container.
248 With [*Boost.Intrusive] you just choose the hook to be a public base class or
249 a public member of the class to be inserted. [*Boost.Intrusive] also offers
250 more flexible hooks for advanced users, as explained in the chapter
251 [link intrusive.function_hooks Using function hooks], but usually base or member
252 hooks are good enough for most users.
254 [section:usage_base_hook Using base hooks]
256 For [classref boost::intrusive::list list], you can publicly derive from
257 [classref boost::intrusive::list_base_hook list_base_hook].
261 template <class ...Options>
262 class list_base_hook;
264 The class can take several options. [*Boost.Intrusive] classes receive arguments in the
265 form `option_name<option_value>`. You can specify the following options:
267 * [*`tag<class Tag>`]: this argument serves as a tag, so you can derive from more than one
268 [classref boost::intrusive::list_base_hook list_base_hook] and hence put an object in
269 multiple intrusive lists at the same time. An incomplete type can serve as a tag.
270 If you specify two base hooks, you [*must] specify a different
271 tag for each one. Example: `list_base_hook< tag<tag1> >`. If no tag is specified
272 a default one will be used (more on default tags later).
274 * [*`link_mode<link_mode_type LinkMode>`]: The second template argument controls the
275 linking policy. [*Boost.Intrusive] currently supports
276 3 modes: `normal_link`, `safe_link` and `auto_unlink`. By default, `safe_link`
277 mode is used. More about these in sections
278 [link intrusive.safe_hook Safe hooks] and [link intrusive.auto_unlink_hooks Auto-unlink hooks].
279 Example: `list_base_hook< link_mode<auto_unlink> >`
281 * [*`void_pointer<class VoidPointer>`]: this option is the pointer type to be used
282 internally in the hook. The default value is `void *`, which means that raw pointers
283 will be used in the hook. More about this in the section titled
284 [link intrusive.using_smart_pointers Using smart pointers with Boost.Intrusive containers].
285 Example: `list_base_hook< void_pointer< my_smart_ptr<void> >`
287 For the following examples, let's forget the options and use the default values:
291 #include <boost/intrusive/list.hpp>
293 using namespace boost::intrusive;
296 //Base hook with default tag, raw pointers and safe_link mode
297 : public list_base_hook<>
300 After that, we can define the intrusive list:
304 template <class T, class ...Options>
307 `list` receives the type to be inserted in the container (`T`) as the first parameter
308 and optionally, the user can specify options. We have 3 option types:
310 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
311 [*`value_traits<class ValueTraits>`]: All these options specify the relationship
312 between the type `T` to be inserted in the list and the hook (since we can
313 have several hooks in the same `T` type). `member_hook` will be explained
314 a bit later and `value_traits` will be explained in the
315 [link intrusive.value_traits Containers with custom ValueTraits] section.
316 [*If no option is specified, the container will be configured to use the base
317 hook with the default tag].
318 Some options configured for the hook (the type of the pointers, link mode, etc.)
319 will be propagated to the container.
321 * [*`constant_time_size<bool Enabled>`]: Specifies if a constant time `size()`
322 function is demanded for the container. This will instruct the intrusive
323 container to store an additional member to keep track of the current size of the
324 container. By default, constant-time size is activated.
326 * [*`size_type<class SizeType>`]: Specifies an unsigned type that can hold
327 the size of the container. This type will be the type returned by `list.size()`
328 and the type stored in the intrusive container if `constant_time_size<true>`
330 The user normally will not need to change this type, but some
331 containers can have a `size_type` that might be different from `std::size_t`
332 (for example, STL-like containers use the `size_type` defined by their allocator).
333 [*Boost.Intrusive] can be used to implement such containers specifying the
334 the type of the size. By default the type is `std::size_t`.
336 Example of a constant-time size intrusive list that will store Foo objects, using
337 the base hook with the default tag:
341 typedef list<Foo> FooList;
343 Example of an intrusive list with non constant-time size that will store Foo objects:
347 typedef list<Foo, constant_time_size<false> > FooList;
349 Remember that the user must specify the base hook in the container declaration
350 if the base hook has no default tag, because that usually means that the type
351 has more than one base hook, and a container shall know which hook will be
356 #include <boost/intrusive/list.hpp>
358 using namespace boost::intrusive;
363 typedef list_base_hook< tag<my_tag> > BaseHook;
364 typedef list_base_hook< tag<my_tag2> > BaseHook2;
365 class Foo : public BaseHook, public BaseHook2
368 typedef list< Foo, base_hook<BaseHook> > FooList;
369 typedef list< Foo, base_hook<BaseHook2> > FooList2;
371 Once the list is defined, we can use it:
375 //An object to be inserted in the list
379 list.push_back(object);
381 assert(&list.front() == &foo_object);
385 [section:usage_member_hook Using member hooks]
387 Sometimes an 'is-a' relationship between list hooks and the list value types
388 is not desirable. In this case, using a member hook as a data member instead of
389 'disturbing' the hierarchy might be the right way: you can add a public data
390 member `list_member_hook<...>` to your class.
391 This class can be configured with the same options as `list_base_hook`
392 except the option `tag`:
396 template <class ...Options>
397 class list_member_hook;
403 #include <boost/intrusive/list.hpp>
408 list_member_hook<> hook_;
412 When member hooks are used, the `member_hook` option is used to configure the
417 //This option will configure "list" to use the member hook
418 typedef member_hook<Foo, list_member_hook<>, &Foo::hook_> MemberHookOption;
420 //This list will use the member hook
421 typedef list<Foo, MemberHookOption> FooList;
423 Now we can use the container:
427 //An object to be inserted in the list
431 list.push_back(object);
433 assert(&list.front() == &foo_object);
437 However, member hooks have some implementation limitations: If there is a virtual inheritance
438 relationship between the parent and the member hook, then the distance between the parent
439 and the hook is not a compile-time fixed value so obtaining the address of
440 the parent from the member hook is not possible without reverse engineering compiler
441 produced RTTI. Apart from this, the non-standard pointer to member implementation for classes
442 with complex inheritance relationships in MSVC ABI compatible-compilers is not supported
443 by member hooks since it also depends on compiler-produced RTTI information.
445 [section:usage_both_hooks Using both hooks]
447 You can insert the same object in several intrusive containers at the same time,
448 using one hook per container. This is a full example using base and member hooks:
450 [import ../example/doc_how_to_use.cpp]
451 [doc_how_to_use_code]
455 [section:usage_lifetime Object lifetime]
457 Even if the interface of [classref boost::intrusive::list list] is similar to
458 `std::list`, its usage is a bit different: You always have to keep in mind that
459 you directly store objects in intrusive containers, not copies. The lifetime of a
460 stored object is not bound to or managed by the container:
462 * When the container gets destroyed before the object, the object is not destroyed,
463 so you have to be careful to avoid resource leaks.
465 * When the object is destroyed before the container, your program is likely to crash,
466 because the container contains a pointer to an non-existing object.
473 [section:usage_when When to use?]
475 Intrusive containers can be used for highly optimized algorithms, where speed is a crucial
478 * additional memory management should be avoided.
479 * the programmer needs to efficiently track the construction and destruction of objects.
480 * exception safety, especially the no-throw guarantee, is needed.
481 * the computation of an iterator to an element from a pointer or reference
482 to that element should be a constant time operation.
483 * it's important to achieve a well-known worst-time system response.
484 * localization of data (e.g. for cache hit optimization) leads to measurable effects.
486 The last point is important if you have a lot of containers over a set of elements. E.g. if
487 you have a vector of objects (say, `std::vector<Object>`), and you also have a list
488 storing a subset of those objects (`std::list<Object*>`), then operating on an Object
489 from the list iterator (`std::list<Object*>::iterator`) requires two steps:
491 * Access from the iterator (usually on the stack) to the list node storing a pointer to `Object`.
492 * Access from the pointer to `Object` to the Object stored in the vector.
494 While the objects themselves are tightly packed in the memory of the vector
495 (a vector's memory is guaranteed to be contiguous), and form something
496 like a data block, list nodes may be dispersed in the heap memory.
497 Hence depending on your system you might get a lot of cache misses. The same doesn't hold
498 for an intrusive list. Indeed, dereferencing an iterator from an intrusive list is performed in
499 the same two steps as described above. But the list node is already embedded in the Object, so
500 the memory is directly tracked from the iterator to the Object.
502 It's also possible to use intrusive containers when the objects to be stored can
503 have different or unknown size. This allows storing base and derived objects
504 in the same container, as shown in the following example:
506 [import ../example/doc_window.cpp]
509 Due to certain properties of intrusive containers
510 they are often more difficult to use than their STL-counterparts. That's why you
511 should avoid them in public interfaces of libraries. Classes to be stored in intrusive
512 containers must change their implementation to store the hook and this is not always
513 possible or desirable.
517 [section:concepts_summary Concept summary]
519 Here is a small summary of the basic concepts that will be used in the following
522 [variablelist Brief Concepts Summary
523 [[Node Algorithms][A class containing typedefs and static functions that define
524 basic operations that can be applied to a group of `node`s. It's independent
525 from the node definition and configured using a NodeTraits template
526 parameter that describes the node.]]
527 [[Node Traits][A class that stores basic information and operations to insert a node into a group of nodes.]]
528 [[Hook][A class that a user must add as a base class or as a member to make the user class compatible with intrusive containers. A Hook encapsulates a `node`]]
529 [[Intrusive Container][A class that stores user classes that have the needed hooks. It takes a ValueTraits template parameter as configuration information.]]
530 [[Semi-Intrusive Container][Similar to an intrusive container but a semi-intrusive container needs additional memory (e.g. an auxiliary array) to work.]]
531 [[Value Traits][A class containing typedefs and operations to obtain the node to be used by Node Algorithms from the user class and the inverse.]]
536 [section:presenting_containers Presenting Boost.Intrusive containers]
538 [*Boost.Intrusive] offers a wide range of intrusive containers:
540 * [*slist]: An intrusive singly linked list. The size overhead is very small
541 for user classes (usually the size of one pointer) but many operations have linear
542 time complexity, so the user must be careful if he wants to avoid performance problems.
544 * [*list]: A `std::list` like intrusive linked list. The size overhead is quite
545 small for user classes (usually the size of two pointers). Many operations have
546 constant time complexity.
548 * [*set/multiset/rbtree]: `std::set/std::multiset` like intrusive associative containers
549 based on red-black trees.
550 The size overhead is moderate for user classes (usually the size of three pointers).
551 Many operations have logarithmic time complexity.
553 * [*avl_set/avl_multiset/avltree]: A `std::set/std::multiset` like intrusive associative
554 containers based on AVL trees.
555 The size overhead is moderate for user classes (usually the size of three pointers).
556 Many operations have logarithmic time complexity.
558 * [*splay_set/splay_multiset/splaytree]: `std::set/std::multiset` like intrusive associative
559 containers based on splay trees. Splay trees have no constant operations, but they
560 have some interesting caching properties.
561 The size overhead is moderate for user classes (usually the size of three pointers).
562 Many operations have logarithmic time complexity.
564 * [*sg_set/sg_multiset/sgtree]: A `std::set/std::multiset` like intrusive associative
565 containers based on scapegoat trees. Scapegoat can be configured with the desired
566 balance factor to achieve the desired rebalancing frequency/search time compromise.
567 The size overhead is moderate for user classes (usually the size of three pointers).
568 Many operations have logarithmic time complexity.
570 [*Boost.Intrusive] also offers semi-intrusive containers:
572 * [*unordered_set/unordered_multiset]: `std::tr1::unordered_set/std::tr1::unordered_multiset`
573 like intrusive unordered associative containers.
574 The size overhead is moderate for user classes (an average of two pointers per element).
575 Many operations have amortized constant time complexity.
577 Most of these intrusive containers can be configured with constant or linear time
580 * [*Linear time size]: The intrusive container doesn't hold a size member that is
581 updated with every insertion/erasure. This implies that the `size()` function doesn't have constant
582 time complexity. On the other hand, the container is smaller, and some operations, like
583 `splice()` taking a range of iterators in linked lists, have constant time complexity
584 instead of linear complexity.
586 * [*Constant time size]: The intrusive container holds a size member that is updated
587 with every insertion/erasure. This implies that the `size()` function has constant time
588 complexity. On the other hand, increases the size of the container, and some operations,
589 like `splice()` taking a range of iterators, have linear time complexity in linked lists.
591 To make user classes compatible with these intrusive containers [*Boost.Intrusive]
592 offers two types of hooks for each container type:
594 * [*Base hook]: The hook is stored as a public base class of the user class.
596 * [*Member hook]: The hook is stored as a public member of the user class.
598 Apart from that, [*Boost.Intrusive] offers additional features:
600 * [*Safe mode hooks]: Hook constructor initializes the internal `node` to a well-known
601 safe state and intrusive containers check that state before inserting a value in the
602 container using that hook. When erasing an element from the container, the container
603 puts the `node` of the hook in the safe state again. This allows a safer use mode and it can
604 be used to detect programming errors. It implies a slight performance overhead in some
605 operations and can convert some constant time operations to linear time operations.
607 * [*Auto-unlink hooks]: The hook destructor removes the object from the container
608 automatically and the user can safely unlink the object from the container without
609 referring to the container.
611 * [*Non-raw pointers]: If the user wants to use smart pointers instead of raw pointers,
612 [*Boost.Intrusive] hooks can
613 be configured to use any type of pointer. This configuration information is also
614 transmitted to the containers, so all the internal pointers used by intrusive containers
615 configured with these hooks will be smart pointers. As an example,
616 [*Boost.Interprocess] defines a smart pointer compatible with shared memory,
617 called `offset_ptr`. [*Boost.Intrusive] can be configured to use this smart pointer
618 to allow shared memory intrusive containers.
622 [section:safe_hook Safe hooks]
624 [section:features Features of the safe mode]
626 [*Boost.Intrusive] hooks can be configured to operate in safe-link mode.
627 The safe mode is activated by default, but it can be also explicitly activated:
631 //Configuring the safe mode explicitly
632 class Foo : public list_base_hook< link_mode<safe_link> >
635 With the safe mode the user can detect if the object
636 is actually inserted in a container without any external reference. Let's review the basic features of the safe mode:
638 * Hook's constructor puts the hook in a well-known default state.
640 * Hook's destructor checks if the hook is in the well-known default state. If not,
641 an assertion is raised.
643 * Every time an object is inserted in the intrusive container, the container
644 checks if the hook is in the well-known default state. If not,
645 an assertion is raised.
647 * Every time an object is being erased from the intrusive container, the container
648 puts the erased object in the well-known default state.
650 With these features, without any external reference the user can know if the object
651 has been inserted in a container by calling the `is_linked()` member function.
652 If the object is not actually inserted
653 in a container, the hook is in the default state, and if it is inserted in a container, the
654 hook is not in the default state.
658 [section:configuring Configuring safe-mode assertions]
660 By default, all safe-mode assertions raised by [*Boost-Intrusive] hooks
661 and containers in are implemented using `BOOST_ASSERT`, which can be configured by
662 the user. See [@http://www.boost.org/libs/utility/assert.html] for more
663 information about `BOOST_ASSERT`.
665 `BOOST_ASSERT` is globally configured, so the user might
666 want to redefine intrusive safe-mode assertions without modifying the global
667 `BOOST_ASSERT`. This can be achieved redefining the following macros:
669 * `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT`: This assertion will be
670 used in insertion functions of the intrusive containers to check that
671 the hook of the value to be inserted is default constructed.
672 * `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT`: This assertion will be
673 used in hooks' destructors to check that the hook is in a default state.
675 If any of these macros is not redefined, the assertion will default to `BOOST_ASSERT`.
676 If `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT` or `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT`
677 is defined and the programmer needs to include a file to configure that assertion, it can define
678 `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE` or `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT_INCLUDE`
679 with the name of the file to include:
683 #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT MYASSERT
684 #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE <myassert.h>
690 [section:auto_unlink_hooks Auto-unlink hooks]
692 [section:auto_unlink_hooks_what What's an auto-unlink hook?]
694 [*Boost.Intrusive] offers additional hooks with unique features:
696 * When the destructor of the hook is called, the hook checks if the node is inserted
697 in a container. If so, the hook removes the node from the container.
698 * The hook has a member function called `unlink()` that can be used to unlink the
699 node from the container at any time, without having any reference to the container,
700 if the user wants to do so.
702 These hooks have exactly the same size overhead as their analog non auto-unlinking
703 hooks, but they have a restriction: they can only be used with
704 [link intrusive.presenting_containers non-constant time containers].
705 There is a reason for this:
707 * Auto-unlink hooks don't store any reference to the container where they are inserted.
708 * Only containers with non constant-time `size()` allow removing an object from the container
709 without referring to the container.
711 This auto-unlink feature is useful in certain applications
712 but it must be used [*very carefully]:
714 * If several threads are using the same container the destructor of the auto-unlink
715 hook will be called without any thread synchronization so removing the object is
718 * Container contents change silently without modifying the container directly.
719 This can lead to surprising effects.
721 These auto-unlink hooks have also safe-mode properties:
723 * Hooks' constructors put the hook in a well-known default state.
725 * Every time an object is inserted in the intrusive container, the container
726 checks if the hook is in the well-known default state. If not,
727 an assertion is raised.
729 * Every time an object is erased from an intrusive container, the container
730 puts the erased object in the well-known default state.
734 [section:auto_unlink_hooks_example Auto-unlink hook example]
736 Let's see an example of an auto-unlink hook:
738 [import ../example/doc_auto_unlink.cpp]
739 [doc_auto_unlink_code]
743 [section:auto_unlink_and_constant_time Auto-unlink hooks and containers with constant-time `size()`]
745 As explained, [*Boost.Intrusive] auto-unlink hooks are incompatible with containers
746 that have constant-time `size()`, so if you try to define such container with an
747 auto-unlink hook's value_traits, you will get a static assertion:
751 #include <boost/intrusive/list.hpp>
753 using boost::intrusive;
757 class MyClass : public list_base_hook< link_mode<auto_unlink> >
760 list <MyClass, constant_time_size<true> > bad_list;
768 leads to an error similar to:
771 error : use of undefined type 'boost::STATIC_ASSERTION_FAILURE<false>'
774 Pointing to code like this:
778 //Constant-time size is incompatible with auto-unlink hooks!
779 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));
781 This way, there is no way to compile a program if you try to use auto-unlink hooks
782 in constant-time size containers.
788 [section:slist Intrusive singly linked list: slist]
790 [classref boost::intrusive::slist slist] is the simplest intrusive container of
791 [*Boost.Intrusive]: a singly linked list. The memory overhead
792 it imposes is 1 pointer per node. The size of an empty, non constant-time size
793 [classref boost::intrusive::slist slist] is the size of 1 pointer. This
794 lightweight memory overhead comes with drawbacks, though: many operations have
795 linear time complexity, even some that usually are constant time, like
796 [classref boost::intrusive::slist::swap swap]. [classref boost::intrusive::slist slist]
797 only provides forward iterators.
799 For most cases, a doubly linked list is preferable because it offers more
800 constant-time functions with a slightly bigger size overhead.
801 However, for some applications like
802 constructing more elaborate containers, singly linked lists are essential
803 because of their low size overhead.
805 [section:slist_hooks slist hooks]
807 Like the rest of [*Boost.Intrusive] containers,
808 [classref boost::intrusive::slist slist] has two hook types:
812 template <class ...Options>
813 class slist_base_hook;
815 * [classref boost::intrusive::slist_base_hook slist_base_hook]:
816 the user class derives publicly from
817 [classref boost::intrusive::slist_base_hook slist_base_hook] to make
818 it [classref boost::intrusive::slist slist]-compatible.
822 template <class ...Options>
823 class slist_member_hook;
825 * [classref boost::intrusive::slist_member_hook slist_member_hook]:
826 the user class contains a public
827 [classref boost::intrusive::slist_member_hook slist_member_hook] to make
828 it [classref boost::intrusive::slist slist]-compatible.
830 [classref boost::intrusive::slist_base_hook slist_base_hook] and
831 [classref boost::intrusive::slist_member_hook slist_member_hook]
832 receive the same options explained in
833 the section [link intrusive.usage How to use Boost.Intrusive]:
835 * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
836 so you can derive from more than one slist hook.
837 Default: `tag<default_tag>`.
839 * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
840 Default: `link_mode<safe_link>`.
842 * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
843 internally in the hook and propagated to the container.
844 Default: `void_pointer<void*>`.
848 [section:slist_container slist container]
852 template <class T, class ...Options>
855 [classref boost::intrusive::slist slist] receives the options explained in
856 the section [link intrusive.usage How to use Boost.Intrusive]:
858 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
859 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
860 to configure the container. (To learn about value traits go to the section
861 [link intrusive.value_traits Containers with custom ValueTraits].)
863 * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
864 Default: `constant_time_size<true>`
866 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
867 of the container. Default: `size_type<std::size_t>`.
869 [classref boost::intrusive::slist slist] can receive additional options:
871 * [*`linear<bool Enable>`]: the singly linked list is implemented as a
872 null-terminated list instead of a circular list. This allows `O(1)` swap,
873 but losses some operations like `container_from_end_iterator`.
874 * [*`cache_last<bool Enable>`]: `slist` also stores a pointer to the
875 last element of the singly linked list. This allows `O(1)` swap,
876 `splice_after(iterator, slist &)` and makes the list offer new functions
877 like `push_back(reference)` and `back()`. Logically, the size an empty list is
878 increased in `sizeof(void_pointer)` and the cached last node pointer must
879 be updated in every operation, and that might incur in a slight performance impact.
881 `auto_unlink` hooks are not usable if `linear<true>` and/or `cache_last<true>` options are
882 used. If `auto_unlink` hooks are used and those options are specified, a static
883 assertion will be raised.
887 [section:slist_example Example]
889 Now let's see a small example using both hooks:
891 [import ../example/doc_slist.cpp]
898 [section:list Intrusive doubly linked list: list]
900 [classref boost::intrusive::list list] is a doubly linked list. The memory overhead
901 it imposes is 2 pointers per node. An empty, non constant-time size [classref boost::intrusive::list list]
902 also has the size of 2 pointers. [classref boost::intrusive::list list]
903 has many more constant-time operations than [classref boost::intrusive::slist slist]
904 and provides a bidirectional iterator. It is recommended to use
905 [classref boost::intrusive::list list] instead of
906 [classref boost::intrusive::slist slist] if the size overhead is acceptable:
908 [section:list_hooks list hooks]
910 Like the rest of [*Boost.Intrusive] containers,
911 [classref boost::intrusive::list list] has two hook types:
915 template <class ...Options>
916 class list_base_hook;
918 * [classref boost::intrusive::list_base_hook list_base_hook]: the user class
919 derives publicly from [classref boost::intrusive::list_base_hook list_base_hook]
920 to make it [classref boost::intrusive::list list]-compatible.
924 template <class ...Options>
925 class list_member_hook;
927 * [classref boost::intrusive::list_member_hook list_member_hook]:
928 the user class contains a public
929 [classref boost::intrusive::list_member_hook list_member_hook] to make
930 it [classref boost::intrusive::list list]-compatible.
932 [classref boost::intrusive::list_base_hook list_base_hook] and
933 [classref boost::intrusive::list_member_hook list_member_hook] receive
934 the same options explained in the section
935 [link intrusive.usage How to use Boost.Intrusive]:
937 * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
938 so you can derive from more than one list hook.
939 Default: `tag<default_tag>`.
941 * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
942 Default: `link_mode<safe_link>`.
944 * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
945 internally in the hook and propagated to the container.
946 Default: `void_pointer<void*>`.
950 [section:list_container list container]
954 template <class T, class ...Options>
957 [classref boost::intrusive::list list] receives the same options explained in
958 the section [link intrusive.usage How to use Boost.Intrusive]:
960 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
961 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
962 to configure the container. (To learn about value traits go to the section
963 [link intrusive.value_traits Containers with custom ValueTraits].)
965 * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
966 Default: `constant_time_size<true>`
968 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
969 of the container. Default: `size_type<std::size_t>`
973 [section:list_example Example]
975 Now let's see a small example using both hooks:
977 [import ../example/doc_list.cpp]
984 [section:set_multiset Intrusive associative containers: set, multiset, rbtree]
986 [*Boost.Intrusive] also offers associative containers that can be very useful
987 when creating more complex associative containers, like containers maintaining
988 one or more indices with different sorting semantics. Boost.Intrusive associative
989 containers, like most STL associative container implementations are based on
992 The memory overhead of these containers is usually 3 pointers and a bit (with
993 alignment issues, this means 3 pointers and an integer).
994 This size can be reduced to 3 pointers if pointers have even alignment
995 (which is usually true in most systems).
997 An empty, non constant-time size [classref boost::intrusive::set set],
998 [classref boost::intrusive::multiset multiset] or
999 [classref boost::intrusive::rbtree rbtree]
1000 has also the size of 3 pointers and an integer (3 pointers when optimized for size).
1001 These containers have logarithmic complexity in many
1003 searches, insertions, erasures, etc. [classref boost::intrusive::set set] and
1004 [classref boost::intrusive::multiset multiset] are the
1005 intrusive equivalents of standard `std::set` and `std::multiset` containers.
1007 [classref boost::intrusive::rbtree rbtree] is a superset of
1008 [classref boost::intrusive::set set] and
1009 [classref boost::intrusive::multiset multiset] containers that offers
1010 functions to insert unique and multiple keys.
1012 [section:set_multiset_hooks set, multiset and rbtree hooks]
1014 [classref boost::intrusive::set set],
1015 [classref boost::intrusive::multiset multiset] and
1016 [classref boost::intrusive::rbtree rbtree] share the same hooks.
1017 This is an advantage, because the same
1018 user type can be inserted first in a [classref boost::intrusive::multiset multiset]
1019 and after that in [classref boost::intrusive::set set] without
1020 changing the definition of the user class.
1024 template <class ...Options>
1025 class set_base_hook;
1027 * [classref boost::intrusive::set_base_hook set_base_hook]:
1028 the user class derives publicly from
1029 [classref boost::intrusive::set_base_hook set_base_hook] to make
1030 it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.
1034 template <class ...Options>
1035 class set_member_hook;
1037 * [classref boost::intrusive::set_member_hook set_member_hook]:
1038 the user class contains a public
1039 [classref boost::intrusive::set_member_hook set_member_hook] to make
1040 it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.
1042 [classref boost::intrusive::set_base_hook set_base_hook] and
1043 [classref boost::intrusive::set_member_hook set_member_hook] receive
1044 the same options explained in the section
1045 [link intrusive.usage How to use Boost.Intrusive] plus a size optimization option:
1047 * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
1048 so you can derive from more than one base hook.
1049 Default: `tag<default_tag>`.
1051 * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
1052 Default: `link_mode<safe_link>`.
1054 * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
1055 internally in the hook and propagated to the container.
1056 Default: `void_pointer<void*>`.
1058 * [*`optimize_size<bool Enable>`]: The hook will be optimized for size
1059 instead of speed. The hook will embed the color bit of the red-black
1060 tree node in the parent pointer if pointer alignment is even.
1061 In some platforms, optimizing the size might reduce speed performance a bit
1062 since masking operations will be needed to access parent pointer and color attributes,
1063 in other platforms this option improves performance due to improved memory locality.
1064 Default: `optimize_size<false>`.
1068 [section:set_multiset_containers set, multiset and rbtree containers]
1072 template <class T, class ...Options>
1075 template <class T, class ...Options>
1078 template <class T, class ...Options>
1081 These containers receive the same options explained in the section
1082 [link intrusive.usage How to use Boost.Intrusive]:
1084 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
1085 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
1086 to configure the container. (To learn about value traits go to the section
1087 [link intrusive.value_traits Containers with custom ValueTraits].)
1089 * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
1090 Default: `constant_time_size<true>`
1092 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
1093 of the container. Default: `size_type<std::size_t>`
1095 And they also can receive an additional option:
1097 * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
1098 in containers. The comparison functor must induce a strict weak ordering.
1099 Default: `compare< std::less<T> >`
1103 [section:set_multiset_example Example]
1105 Now let's see a small example using both hooks and both containers:
1107 [import ../example/doc_set.cpp]
1114 [section:unordered_set_unordered_multiset Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset]
1116 [*Boost.Intrusive] also offers hashed containers that can be very useful to implement
1117 fast-lookup containers. These containers
1118 ([classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_multiset unordered_multiset])
1119 are semi-intrusive containers: they need additional memory apart from the hook
1120 stored in the `value_type`. This additional
1121 memory must be passed in the constructor of the container.
1123 Unlike C++ TR1 unordered associative containers (which are also hashed containers),
1124 the contents of these semi-intrusive containers are not rehashed to maintain a
1125 load factor: that would require memory management and intrusive containers don't
1126 implement any memory management at all. However, the user can request an explicit
1127 rehashing passing a new bucket array.
1128 This also offers an additional guarantee over TR1 unordered associative containers:
1129 [*iterators are not invalidated when inserting an element] in the container.
1131 As with TR1 unordered associative containers, rehashing invalidates iterators,
1132 changes ordering between elements and changes which buckets elements appear in,
1133 but does not invalidate pointers or references to elements.
1135 Apart from expected hash and equality function objects, [*Boost.Intrusive] unordered
1136 associative containers' constructors take an argument specifying an auxiliary
1137 bucket vector to be used by the container.
1139 [section:unordered_set_unordered_multiset_performance unordered_set and unordered_multiset performance notes]
1141 The size overhead for a hashed container is moderate: 1 pointer per value plus
1142 a bucket array per container. The size of an element of the bucket array
1143 is usually one pointer. To obtain a good performance hashed container,
1144 the bucket length is usually the same as the number of elements that the
1145 container contains, so a well-balanced hashed container (`bucket_count()` is
1146 equal to `size()` ) will have an equivalent overhead of two pointers per element.
1148 An empty, non constant-time size [classref boost::intrusive::unordered_set unordered_set] or
1149 [classref boost::intrusive::unordered_multiset unordered_multiset]
1150 has also the size of `bucket_count()` pointers.
1152 Insertions, erasures, and searches, have amortized constant-time complexity in
1153 hashed containers. However, some worst-case guarantees are linear. See
1154 [classref boost::intrusive::unordered_set unordered_set] or
1155 [classref boost::intrusive::unordered_multiset unordered_multiset] for complexity guarantees
1158 [*Be careful with non constant-time size hashed containers]: some operations, like
1159 `empty()`, have linear complexity, unlike other [*Boost.Intrusive] containers.
1163 [section:unordered_set_unordered_multiset_hooks unordered_set and unordered_multiset hooks]
1165 [classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_multiset unordered_multiset] share the same hooks. This is an advantage, because the same
1166 user type can be inserted first in a [classref boost::intrusive::unordered_multiset unordered_multiset] and after that in [classref boost::intrusive::unordered_set unordered_set] without
1167 changing the definition of the user class.
1171 template <class ...Options>
1172 class unordered_set_base_hook;
1174 * [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook]:
1175 the user class derives publicly from
1176 [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] to make
1177 it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible.
1181 template <class ...Options>
1182 class unordered_set_member_hook;
1184 * [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook]:
1185 the user class contains a public
1186 [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] to make
1187 it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible.
1189 [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] and
1190 [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] receive
1191 the same options explained in the section
1192 [link intrusive.usage How to use Boost.Intrusive]:
1194 * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
1195 so you can derive from more than one base hook.
1196 Default: `tag<default_tag>`.
1198 * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
1199 Default: `link_mode<safe_link>`.
1201 * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
1202 internally in the hook and propagated to the container.
1203 Default: `void_pointer<void*>`.
1205 Apart from them, these hooks offer additional options:
1207 * [*`store_hash<bool Enabled>`]: This option reserves additional space in
1208 the hook to store the hash value of the object once it's introduced in the
1209 container. When this option is used, the unordered container will store
1210 the calculated hash value in the hook and rehashing operations won't need
1211 to recalculate the hash of the value.
1212 This option will improve the performance of unordered containers when
1213 rehashing is frequent or hashing the value is a slow operation.
1214 Default: `store_hash<false>`.
1216 * [*`optimize_multikey<bool Enabled>`]: This option reserves additional space in
1217 the hook that will be used to group equal elements in unordered multisets,
1218 improving significantly the performance when many equal values are inserted
1219 in these containers. Default: `optimize_multikey<false>`.
1223 [section:unordered_set_unordered_multiset_containers unordered_set and unordered_multiset containers]
1227 template<class T, class ...Options>
1228 class unordered_set;
1230 template<class T, class ...Options>
1231 class unordered_multiset;
1233 As mentioned, unordered containers need an auxiliary array to work. [*Boost.Intrusive]
1234 unordered containers receive this auxiliary array packed in a type called `bucket_traits`
1235 (which can be also customized by a container option). All unordered containers receive
1236 a `bucket_traits` object in their constructors. The default `bucket_traits` class
1237 is initialized with a pointer to an array of buckets and its size:
1241 #include <boost/intrusive/unordered_set.hpp>
1243 using namespace boost::intrusive;
1245 struct MyClass : public unordered_set_base_hook<>
1248 typedef unordered_set<MyClass>::bucket_type bucket_type;
1249 typedef unordered_set<MyClass>::bucket_traits bucket_traits;
1253 bucket_type buckets[100];
1254 unordered_set<MyClass> uset(bucket_traits(buckets, 100));
1258 Each hashed container needs [*its own bucket traits], that is, [*its own
1259 bucket vector]. Two hashed containers
1260 [*can't] share the same `bucket_type` elements. The bucket array [*must] be
1261 destroyed [*after] the container using it is destroyed, otherwise, the result
1264 [classref boost::intrusive::unordered_set unordered_set] and
1265 [classref boost::intrusive::unordered_multiset unordered_multiset]
1266 receive the same options explained in the section
1267 [link intrusive.usage How to use Boost.Intrusive]:
1269 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
1270 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
1271 to configure the container. (To learn about value traits go to the section
1272 [link intrusive.value_traits Containers with custom ValueTraits].)
1274 * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
1275 Default: `constant_time_size<true>`
1277 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
1278 of the container. Default: `size_type<std::size_t>`
1280 And they also can receive additional options:
1282 * [*`equal<class Equal>`]: Equality function for the objects to be inserted
1283 in containers. Default: `equal< std::equal_to<T> >`
1285 * [*`hash<class Hash>`]: Hash function to be used in the container.
1286 Default: `hash< boost::hash<T> >`
1288 * [*`bucket_traits<class BucketTraits>`]: A type that wraps the bucket vector to
1289 be used by the unordered container. Default: a type initialized by the address
1290 and size of a bucket array and stores both variables internally.
1292 * [*`power_2_buckets<bool Enabled>`]: The user guarantees that only bucket arrays
1293 with power of two length will be used. The container will then use masks instead of modulo
1294 operations to obtain the bucket number from the hash value. Masks are faster than
1295 modulo operations and for some applications modulo operations can impose
1296 a considerable overhead. In debug mode an assertion will be raised if the user
1297 provides a bucket length that is not power of two.
1298 Default: `power_2_buckets<false>`.
1300 * [*`cache_begin<bool Enabled>`]:
1301 [*Note: this option is not compatible with `auto_unlink` hooks].
1302 Due to its internal structure, finding the first
1303 element of an unordered container (`begin()` operation) is
1304 amortized constant-time. It's possible to speed up `begin()` and other operations
1305 related to it (like `clear()`) if the container caches internally the position
1306 of the first element. This imposes the overhead of one pointer to the size
1307 of the container. Default: `cache_begin<false>`.
1309 * [*`compare_hash<bool Enabled>`]:
1310 [*Note: this option requires `store_hash<true>` option in the hook].
1311 When the comparison function is expensive,
1312 (e.g. strings with a long common predicate) sometimes (specially when the
1313 load factor is high or we have many equivalent elements in an
1314 [classref boost::intrusive::unordered_multiset unordered_multiset] and
1315 no `optimize_multikey<>` is activated in the hook)
1316 the equality function is a performance problem. Two equal values must have
1317 equal hashes, so comparing the hash values of two elements before using the
1318 comparison functor can speed up some implementations.
1320 * [*`incremental<bool Enabled>`]: Activates incremental hashing (also known as Linear Hashing).
1321 This option implies `power_2_buckets<true>` and the container will require power of two buckets.
1322 For more information on incremental hashing, see
1323 [@http://en.wikipedia.org/wiki/Linear_hashing `Linear hash` on Wikipedia]
1324 Default: `incremental<false>`
1328 [section:unordered_set_unordered_multiset_example Example]
1330 Now let's see a small example using both hooks and both containers:
1332 [import ../example/doc_unordered_set.cpp]
1333 [doc_unordered_set_code]
1337 [section:custom_bucket_traits Custom bucket traits]
1339 Instead of using the default `bucket_traits` class to store the bucket array, a user
1340 can define his own class to store the bucket array using the [*['bucket_traits<>]]
1341 option. A user-defined bucket-traits must fulfill the following interface:
1345 class my_bucket_traits
1347 bucket_ptr bucket_begin();
1348 const_bucket_ptr bucket_begin() const;
1349 std::size_t bucket_count() const;
1353 The following bucket traits just stores a pointer to the bucket
1354 array but the size is a compile-time constant. Note the use of the auxiliary
1355 [classref boost::intrusive::unordered_bucket unordered_bucket] and
1356 [classref boost::intrusive::unordered_bucket_ptr unordered_bucket_ptr]
1357 utilities to obtain the type of the bucket and its pointer before defining
1358 the unordered container:
1360 [import ../example/doc_bucket_traits.cpp]
1367 [section:avl_set_multiset Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree]
1369 Similar to red-black trees, AVL trees are balanced binary trees.
1370 AVL trees are often compared with red-black trees because they support the same set of operations
1371 and because both take O(log n) time for basic operations.
1372 AVL trees are more rigidly balanced than Red-Black trees, leading to slower insertion and
1373 removal but faster retrieval, so AVL trees perform better
1374 than red-black trees for lookup-intensive applications.
1376 [*Boost.Intrusive] offers 3 containers based on avl trees:
1377 [classref boost::intrusive::avl_set avl_set],
1378 [classref boost::intrusive::avl_multiset avl_multiset] and
1379 [classref boost::intrusive::avltree avltree]. The first two are similar to
1380 [classref boost::intrusive::set set] or
1381 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1382 that offers functions both to insert unique and multiple keys.
1384 The memory overhead of these containers with Boost.Intrusive hooks is usually 3
1385 pointers and 2 bits (due to alignment, this usually means 3 pointers plus an integer).
1386 This size can be reduced to 3 pointers if pointers have 4 byte alignment
1387 (which is usually true in 32 bit systems).
1389 An empty, non constant-time size [classref boost::intrusive::avl_set avl_set],
1390 [classref boost::intrusive::avl_multiset avl_multiset] or
1391 [classref boost::intrusive::avltree avltree]
1392 also has a size of 3 pointers and an integer (3 pointers when optimized for size).
1394 [section:avl_set_multiset_hooks avl_set, avl_multiset and avltree hooks]
1396 [classref boost::intrusive::avl_set avl_set],
1397 [classref boost::intrusive::avl_multiset avl_multiset] and
1398 [classref boost::intrusive::avltree avltree]
1399 share the same hooks.
1403 template <class ...Options>
1404 class avl_set_base_hook;
1406 * [classref boost::intrusive::avl_set_base_hook avl_set_base_hook]:
1407 the user class derives publicly from this class to make
1408 it compatible with avl tree based containers.
1412 template <class ...Options>
1413 class avl_set_member_hook;
1415 * [classref boost::intrusive::set_member_hook set_member_hook]:
1416 the user class contains a public member of this class to make
1417 it compatible with avl tree based containers.
1419 [classref boost::intrusive::avl_set_base_hook avl_set_base_hook] and
1420 [classref boost::intrusive::avl_set_member_hook avl_set_member_hook] receive
1421 the same options explained in the section
1422 [link intrusive.usage How to use Boost.Intrusive] plus an option to optimize
1423 the size of the node:
1425 * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
1426 so you can derive from more than one base hook.
1427 Default: `tag<default_tag>`.
1429 * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
1430 Default: `link_mode<safe_link>`.
1432 * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
1433 internally in the hook and propagated to the container.
1434 Default: `void_pointer<void*>`.
1436 * [*`optimize_size<bool Enable>`]: The hook will be optimized for size
1437 instead of speed. The hook will embed the balance bits of the AVL
1438 tree node in the parent pointer if pointer alignment is multiple of 4.
1439 In some platforms, optimizing the size might reduce speed performance a bit
1440 since masking operations will be needed to access parent pointer and balance factor attributes,
1441 in other platforms this option improves performance due to improved memory locality.
1442 Default: `optimize_size<false>`.
1446 [section:set_multiset_containers avl_set, avl_multiset and avltree containers]
1450 template <class T, class ...Options>
1453 template <class T, class ...Options>
1456 template <class T, class ...Options>
1459 These containers receive the same options explained in the section
1460 [link intrusive.usage How to use Boost.Intrusive]:
1462 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
1463 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
1464 to configure the container. (To learn about value traits go to the section
1465 [link intrusive.value_traits Containers with custom ValueTraits].)
1467 * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
1468 Default: `constant_time_size<true>`
1470 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
1471 of the container. Default: `size_type<std::size_t>`
1473 And they also can receive an additional option:
1475 * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
1476 in containers. The comparison functor must induce a strict weak ordering.
1477 Default: `compare< std::less<T> >`
1481 [section:avl_set_multiset_example Example]
1483 Now let's see a small example using both hooks and
1484 [classref boost::intrusive::avl_set avl_set]/
1485 [classref boost::intrusive::avl_multiset avl_multiset]
1488 [import ../example/doc_avl_set.cpp]
1495 [section:splay_set_multiset Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree]
1497 C++ associative containers are usually based on red-black tree implementations (e.g.: STL,
1498 Boost.Intrusive associative containers). However, there are other interesting data
1499 structures that offer some advantages (and also disadvantages).
1501 Splay trees are self-adjusting binary search trees used typically in caches, memory
1502 allocators and other applications, because splay trees have a "caching effect": recently
1503 accessed elements have better access times than elements accessed less frequently.
1504 For more information on splay trees see [@http://en.wikipedia.org/wiki/Splay_tree the corresponding Wikipedia entry].
1506 [*Boost.Intrusive] offers 3 containers based on splay trees:
1507 [classref boost::intrusive::splay_set splay_set],
1508 [classref boost::intrusive::splay_multiset splay_multiset] and
1509 [classref boost::intrusive::splaytree splaytree]. The first two are similar to
1510 [classref boost::intrusive::set set] or
1511 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1512 that offers functions both to insert unique and multiple keys.
1514 The memory overhead of these containers with Boost.Intrusive hooks is usually 3 pointers.
1515 An empty, non constant-time size splay container has also a size of 3 pointers.
1517 [section:splay_set_multiset_disadvantages Advantages and disadvantages of splay tree based containers]
1519 Splay tree based intrusive containers have logarithmic complexity in many
1520 operations like searches, insertions, erasures, etc., but if some elements are
1521 more frequently accessed than others, splay trees perform faster searches than equivalent
1522 balanced binary trees (such as red-black trees).
1524 The caching effect offered by splay trees comes with a cost: the tree must be
1525 rebalanced when an element is searched. To maintain const-correctness and thread-safety
1526 guarantees, this caching effect is not updated when const versions of
1527 search functions like `find()`, `lower_bound()`, `upper_bound()`, `equal_range()`,
1528 `count()`... are called. This means that using splay-tree based associative containers as drop-in
1529 replacements of [classref boost::intrusive::set set]/
1530 [classref boost::intrusive::multiset multiset], specially for const search functions,
1531 might not result in desired performance improvements.
1533 If element searches are randomized, the tree will be continuously srebalanced
1534 without taking advantage of the cache effect, so splay trees can offer worse
1535 performance than other balanced trees for several search patterns.
1537 [*Boost.Intrusive] splay associative containers don't use their own hook types but plain Binary search tree hooks.
1538 See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more
1539 information about these hooks.
1543 [section:set_multiset_containers splay_set, splay_multiset and splaytree containers]
1547 template <class T, class ...Options>
1550 template <class T, class ...Options>
1551 class splay_multiset;
1553 template <class T, class ...Options>
1556 These containers receive the same options explained in the section
1557 [link intrusive.usage How to use Boost.Intrusive]:
1559 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
1560 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
1561 to configure the container. (To learn about value traits go to the section
1562 [link intrusive.value_traits Containers with custom ValueTraits].)
1564 * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
1565 Default: `constant_time_size<true>`
1567 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
1568 of the container. Default: `size_type<std::size_t>`
1570 And they also can receive an additional option:
1572 * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
1573 in containers. The comparison functor must induce a strict weak ordering.
1574 Default: `compare< std::less<T> >`
1578 [section:splay_set_multiset_example Example]
1580 Now let's see a small example using
1581 [classref boost::intrusive::splay_set splay_set]/
1582 [classref boost::intrusive::splay_multiset splay_multiset]
1585 [import ../example/doc_splay_set.cpp]
1586 [doc_splay_set_code]
1593 [section:sg_set_multiset Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree]
1595 A scapegoat tree is a self-balancing binary search tree, that provides worst-case O(log n)
1596 lookup time, and O(log n) amortized insertion and deletion time.
1597 Unlike other self-balancing binary search trees that provide worst case O(log n) lookup
1598 time, scapegoat trees have no additional per-node overhead compared to a regular binary
1601 A binary search tree is said to be weight balanced if half the nodes are on the left
1602 of the root, and half on the right. An a-height-balanced tree is defined with defined
1603 with the following equation:
1605 [*['height(tree) <= log1/a(tree.size())]]
1607 * [*['a == 1]]: A tree forming a linked list is considered balanced.
1608 * [*['a == 0.5]]: Only a perfectly balanced binary is considered balanced.
1610 Scapegoat trees are loosely ['a-height-balanced] so:
1612 [*['height(tree) <= log1/a(tree.size()) + 1]]
1614 Scapegoat trees support any a between 0.5 and 1. If a is higher, the tree is rebalanced
1615 less often, obtaining quicker insertions but slower searches. Lower
1616 a values improve search times. Scapegoat-trees implemented in [*Boost.Intrusive] offer the possibility of
1617 [*changing a at run-time] taking advantage of the flexibility of scapegoat trees.
1618 For more information on scapegoat trees see [@http://en.wikipedia.org/wiki/Scapegoat_tree Wikipedia entry].
1620 Scapegoat trees also have downsides:
1622 * They need additional storage of data on the
1623 root (the size of the tree, for example) to achieve logarithmic complexity operations
1624 so it's not possible to offer `auto_unlink` hooks. The size of an empty scapegoat
1625 tree is also considerably increased.
1627 * The operations needed to determine if the tree is unbalanced require floating-point
1628 operations like ['log1/a]. If the system has no floating point operations (like some
1629 embedded systems), scapegoat tree operations might become slow.
1631 [*Boost.Intrusive] offers 3 containers based on scapegoat trees:
1632 [classref boost::intrusive::sg_set sg_set],
1633 [classref boost::intrusive::sg_multiset sg_multiset] and
1634 [classref boost::intrusive::sgtree sgtree]. The first two are similar to
1635 [classref boost::intrusive::set set] or
1636 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1637 that offers functions both to insert unique and multiple keys.
1639 The memory overhead of these containers with Boost.Intrusive hooks is 3
1642 An empty, [classref boost::intrusive::sg_set sg_set],
1643 [classref boost::intrusive::sg_multiset sg_multiset] or
1644 [classref boost::intrusive::sgtree sgtree]
1645 has also the size of 3 pointers, two integers and two floating point values
1646 (equivalent to the size of 7 pointers on most systems).
1648 [*Boost.Intrusive] scapegoat associative containers don't use their own hook types but plain Binary search tree hooks.
1649 See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more
1650 information about these hooks.
1652 [section:sg_set_multiset_containers sg_set, sg_multiset and sgtree containers]
1656 template <class T, class ...Options>
1659 template <class T, class ...Options>
1662 template <class T, class ...Options>
1665 These containers receive the same options explained in the section
1666 [link intrusive.usage How to use Boost.Intrusive]:
1668 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
1669 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
1670 to configure the container. (To learn about value traits go to the section
1671 [link intrusive.value_traits Containers with custom ValueTraits].)
1673 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
1674 of the container. Default: `size_type<std::size_t>`
1676 And they also can receive additional options:
1678 * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
1679 in containers. The comparison functor must induce a strict weak ordering.
1680 Default: `compare< std::less<T> >`
1682 * [*`floating_point<bool Enable>`]:
1683 When this option is deactivated, the scapegoat tree loses the ability to change
1684 the balance factor a at run-time, but the size of an empty container is reduced
1685 and no floating point operations are performed, normally increasing container
1686 performance. The fixed a factor that is used when this option is activated
1687 is ['1/sqrt(2) ~ 0,70711]. Default: `floating_point<true>`
1691 [section:sg_set_multiset_example Example]
1693 Now let's see a small example using binary search tree hooks and
1694 [classref boost::intrusive::sg_set sg_set]/
1695 [classref boost::intrusive::sg_multiset sg_multiset]
1698 [import ../example/doc_sg_set.cpp]
1706 [section:treap_set_multiset Intrusive treap based associative containers: treap_set, treap_multiset and treap]
1708 The name ['treap] is a mixture of ['tree] and ['heap] indicating that Treaps exhibit the properties of both
1709 binary search trees and heaps. A treap is a binary search tree that orders the nodes
1710 by a key but also by a priority attribute. The nodes are ordered so that the keys form a binary search tree and
1711 the priorities obey the max heap order property.
1713 * If v is a left descendant of u, then key[v] < key[u];
1714 * If v is a right descendant of u, then key[v] > key[u];
1715 * If v is a child of u, then priority[v] <= priority[u];
1717 If priorities are non-random, the tree will usually be unbalanced; this worse theoretical average-case
1718 behavior may be outweighed by better expected-case behavior, as the most important items will be near the root.
1719 This means most important objects will be retrieved faster than less important items and for items keys with equal keys
1720 most important objects will be found first. These properties are important for some applications.
1722 The priority comparison will be provided just like the key comparison, via a function object that will be
1723 stored in the intrusive container. This means that the priority can be stored in the value to be introduced
1724 in the treap or computed on flight (via hashing or similar).
1726 [*Boost.Intrusive] offers 3 containers based on treaps:
1727 [classref boost::intrusive::treap_set treap_set],
1728 [classref boost::intrusive::treap_multiset treap_multiset] and
1729 [classref boost::intrusive::treap treap]. The first two are similar to
1730 [classref boost::intrusive::set set] or
1731 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1732 that offers functions both to insert unique and multiple keys.
1734 The memory overhead of these containers with Boost.Intrusive hooks is 3
1737 An empty, [classref boost::intrusive::treap_set treap_set],
1738 [classref boost::intrusive::treap_multiset treap_multiset] or
1739 [classref boost::intrusive::treap treap]
1740 has also the size of 3 pointers and an integer (supposing empty function objects for key and priority
1741 comparison and constant-time size).
1743 [*Boost.Intrusive] treap associative containers don't use their own hook types but plain Binary search tree hooks.
1744 See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more
1745 information about these hooks.
1747 [section:treap_set_multiset_containers treap_set, treap_multiset and treap containers]
1751 template <class T, class ...Options>
1754 template <class T, class ...Options>
1755 class treap_multiset;
1757 template <class T, class ...Options>
1760 These containers receive the same options explained in the section
1761 [link intrusive.usage How to use Boost.Intrusive]:
1763 * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
1764 [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
1765 to configure the container. (To learn about value traits go to the section
1766 [link intrusive.value_traits Containers with custom ValueTraits].)
1768 * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
1769 Default: `constant_time_size<true>`
1771 * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
1772 of the container. Default: `size_type<std::size_t>`
1774 And they also can receive additional options:
1776 * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
1777 in containers. The comparison functor must induce a strict weak ordering.
1778 Default: `compare< std::less<T> >`
1780 * [*`priority<class PriorityCompare>`]: Priority Comparison function for the objects to be inserted
1781 in containers. The comparison functor must induce a strict weak ordering.
1782 Default: `priority< priority_compare<T> >`
1784 The default `priority_compare<T>` object function will call an unqualified function `priority_order`
1785 passing two constant `T` references as arguments and should return true if the first argument has
1786 higher priority (it will be searched faster), inducing strict weak ordering.
1787 The function will be found using ADL lookup so that
1788 the user just needs to define a `priority_order` function in the same namespace as his class:
1794 friend bool priority_order(const MyType &a, const MyType &b)
1802 struct MyType{ ... };
1804 bool priority_order(const MyType &a, const MyType &b)
1807 } //namespace mytype {
1811 [section:treap_set_exceptions Exception safety of treap-based intrusive containers]
1813 In general, intrusive containers offer strong safety guarantees, but treap containers must deal
1814 with two possibly throwing functors (one for value ordering, another for priority ordering).
1815 Moreover, treap erasure operations require rotations based on the priority order function and
1816 this issue degrades usual `erase(const_iterator)` no-throw guarantee. However, intrusive offers
1817 the strongest possible behaviour in these situations. In summary:
1819 * If the priority order functor does not throw, treap-based containers, offer exactly the same
1820 guarantees as other tree-based containers.
1822 * If the priority order functor throws, treap-based containers offer strong guarantee.
1826 [section:treap_set_multiset_example Example]
1828 Now let's see a small example using binary search tree hooks and
1829 [classref boost::intrusive::treap_set treap_set]/
1830 [classref boost::intrusive::treap_multiset treap_multiset]
1833 [import ../example/doc_treap_set.cpp]
1834 [doc_treap_set_code]
1840 [section:bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook]
1842 Binary search tree hooks can be used with several tree-like containers that don't
1843 need any additional metadata for rebalancing operations. This has many advantages
1844 since binary search tree hooks can also be used to insert values in
1845 plain binary search tree, splay tree, scapegoat tree, and treap containers.
1849 template <class ...Options>
1850 class bs_set_base_hook;
1852 * [classref boost::intrusive::bs_set_base_hook bs_set_base_hook]:
1853 the user class derives publicly from this class to make
1854 it compatible with the mentioned tree based containers.
1858 template <class ...Options>
1859 class bs_set_member_hook;
1861 * [classref boost::intrusive::bs_set_member_hook bs_set_member_hook]:
1862 the user class contains a public member of this class to make
1863 it compatible with the mentioned tree based containers.
1865 [classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
1866 [classref boost::intrusive::bs_set_member_hook bs_set_member_hook] receive
1867 the same options explained in the section
1868 [link intrusive.usage How to use Boost.Intrusive]:
1870 * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
1871 so you can derive from more than one base hook.
1872 Default: `tag<default_tag>`.
1874 * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
1875 Default: `link_mode<safe_link>`.
1877 * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
1878 internally in the hook and propagated to the container.
1879 Default: `void_pointer<void*>`.
1883 [section:advanced_lookups_insertions Advanced lookup and insertion functions for associative containers]
1885 [section:advanced_lookups Advanced lookups]
1887 [*Boost.Intrusive] associative containers offer the same interface as STL associative
1888 containers. However, STL and TR1 ordered and unordered simple associative containers
1889 (`std::set`, `std::multiset`, `std::tr1::unordered_set` and `std::tr1::unordered_multiset`)
1890 have some inefficiencies caused by the interface: the user can only operate with `value_type`
1891 objects. When using these containers we must use `iterator find(const value_type &value)`
1892 to find a value. The same happens in other functions
1893 like `equal_range`, `lower_bound`, `upper_bound`, etc.
1895 However, sometimes the object to be searched is quite expensive to construct:
1897 [import ../example/doc_assoc_optimized_code.cpp]
1898 [doc_assoc_optimized_code_normal_find]
1900 `Expensive` is an expensive object to construct. If "key" c-string is quite long
1901 `Expensive` has to construct a `std::string` using heap memory. Like
1902 `Expensive`, many times the only member taking part in ordering issues is just
1903 a small part of the class. For example, with `Expensive`, only the internal
1904 `std::string` is needed to compare the object.
1906 In both containers, if we call `get_from_set/get_from_unordered_set` in a loop, we might get a performance penalty,
1907 because we are forced to create a whole `Expensive` object to be able to find an
1910 Sometimes this interface limitation is severe, because
1911 we [*might not have enough information to construct the object] but we might
1912 [*have enough information to find the object]. In this case, a name is enough
1913 to search `Expensive` in the container but constructing an `Expensive`
1914 might require more information that the user might not have.
1916 To solve this, [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]
1917 offer alternative functions, which take any type comparable with the value and a
1918 functor that should be compatible with the
1919 ordering function of the associative container.
1920 [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]
1921 offers functions that take any key type and compatible hash and equality functions. Now, let's see the
1922 optimized search function:
1924 [doc_assoc_optimized_code_optimized_find]
1926 This new arbitrary key overload is also available for other functions taking
1927 values as arguments:
1936 Check [classref boost::intrusive::set set],
1937 [classref boost::intrusive::multiset multiset],
1938 [classref boost::intrusive::unordered_set unordered_set],
1939 [classref boost::intrusive::unordered_multiset unordered_multiset]
1940 references to know more about those functions.
1944 [section:advanced_insertions Advanced insertions]
1946 A similar issue happens with insertions in simple ordered and unordered associative
1947 containers with unique keys (`std::set` and `std::tr1::unordered_set`). In these containers,
1948 if a value is already present, the value to be inserted is discarded. With expensive
1949 values, if the value is already present, we can suffer efficiency problems.
1951 [classref boost::intrusive::set set] and [classref boost::intrusive::unordered_set unordered_set]
1952 have insertion functions to check efficiently, without
1953 constructing the value, if a value is present or not and if it's not present, a
1954 function to insert it immediately without any further lookup.
1955 For example, using the same `Expensive` class,
1956 this function can be inefficient:
1958 [doc_assoc_optimized_code_normal_insert]
1960 If the object is already present, we are constructing an `Expensive` that
1961 will be discarded, and this is a waste of resources. Instead of that, let's use
1962 `insert_check` and `insert_commit` functions:
1964 [doc_assoc_optimized_code_optimized_insert]
1966 `insert_check` is similar to a normal `insert` but:
1968 * `insert_check` can be used with arbitrary keys
1969 * if the insertion is possible (there is no equivalent value) `insert_check` collects all the needed information
1970 in an `insert_commit_data` structure, so that `insert_commit`:
1971 * [*does not execute] further comparisons
1972 * can be executed with [*constant-time complexity]
1973 * has [*no-throw guarantee].
1975 These functions must be used with care, since
1976 no other insertion or erasure must be executed between an `insert_check` and an `insert_commit`
1977 pair. Otherwise, the behaviour is undefined.
1978 `insert_check` and `insert_commit` will come in handy
1979 for developers programming efficient non-intrusive associative containers.
1980 See [classref boost::intrusive::set set]
1981 and [classref boost::intrusive::unordered_set unordered_set] reference for more information about
1982 `insert_check` and `insert_commit`.
1984 With multiple ordered and unordered associative containers
1985 ([classref boost::intrusive::multiset multiset] and
1986 [classref boost::intrusive::unordered_multiset unordered_multiset]) there is
1987 no need for these advanced insertion functions, since insertions are always successful.
1991 [section:positional_insertions Positional insertions]
1993 Some ordered associative containers offer low-level functions to bypass ordering
1994 checks and insert nodes directly in desired tree positions. These functions are
1995 provided for performance reasons when values to be inserted in the container are
1996 known to fulfill order (sets and multisets) and uniqueness (sets) invariants. A
1997 typical usage of these functions is when intrusive associative containers are used
1998 to build non-intrusive containers and the programmer wants to speed up assignments
1999 from other associative containers: if the ordering and uniqueness properties are the same,
2000 there is no need to waste time checking the position of each source value, because values
2001 are already ordered: back insertions will be much more efficient.
2003 [*Note:] These functions [*don't check preconditions] so they must used with care. These
2004 are functions are low-level operations [*will break container invariants if
2005 ordering and uniqueness preconditions are not assured by the caller.]
2007 Let's see an example:
2009 [import ../example/doc_positional_insertion.cpp]
2010 [doc_positional_insertion]
2015 For more information about advanced lookup and insertion functions see
2016 associative containers' documentation (e.g.
2017 [classref boost::intrusive::set set],
2018 [classref boost::intrusive::multiset multiset],
2019 [classref boost::intrusive::unordered_set unordered_set] and
2020 [classref boost::intrusive::unordered_multiset unordered_multiset] references).
2024 [section:erasing_and_disposing Erasing and disposing values from Boost.Intrusive containers]
2026 One of the most tedious tasks when using intrusive containers is the management of the erased elements.
2027 When using STL containers, the container itself unlinks and destroys the contained elements, but with
2028 intrusive containers, the user must explicitly destroy the object after erasing an element from the container.
2029 This makes STL-like functions erasing multiple objects unhelpful: the user can't destroy every erased element.
2030 For example, let's take the function `remove_if` from [classref boost::intrusive::list list]:
2034 template<class Pred>
2035 void remove_if(Pred pred);
2037 How can the user destroy the elements (say, using `operator delete`) that will be erased according
2038 to the predicate? [*Boost.Intrusive] containers offer additional functions that take a function
2039 object that will be called after the element has been erased from the container. For example,
2040 [classref boost::intrusive::list list] offers:
2044 template<class Pred, class Disposer>
2045 void remove_and_dispose_if(Pred pred, Disposer disposer)
2047 With this function the user can efficiently remove and destroy elements if the disposer
2048 function destroys an object: `remove_and_dispose_if`
2049 will call the "disposer" function object for every removed element. [classref boost::intrusive::list list] offers
2050 more functions taking a disposer function object as argument, like `erase_and_dispose`, `clear_and_dispose`,
2051 `remove_and_dispose`, etc.
2053 Note that the disposing function does not need to just destroy the object. It can
2054 implement any other operation like inserting the remove object in another container.
2055 Let's see a small example:
2057 [import ../example/doc_erasing_and_disposing.cpp]
2058 [doc_erasing_and_disposing]
2060 All [*Boost.Intrusive] containers offer these "erase + dispose" additional members for all functions
2061 that erase an element from the container.
2067 [section:clone_from Cloning Boost.Intrusive containers]
2069 As previously mentioned, [*Boost.Intrusive] containers are [*non-copyable and non-assignable], because
2070 intrusive containers don't allocate memory at all. To implement a copy-constructor or assignment operator,
2071 the user must clone one by one all the elements of the container and insert them in another intrusive container.
2072 However, cloning by hand is usually more inefficient than a member cloning function and a specialized cloning
2073 function can offer more guarantees than the manual cloning (better exception safety guarantees, for example).
2075 To ease the implementation of copy constructors and assignment operators of classes containing [*Boost.Intrusive]
2076 containers, all [*Boost.Intrusive] containers offer a special cloning function called `clone_from`.
2078 Apart from the container to be cloned, `clone_from` takes two function objects as arguments. For example, consider the
2079 `clone_from` member function of [classref boost::intrusive::list list]:
2083 template <class Cloner, class Disposer>
2084 void clone_from(const list &src, Cloner cloner, Disposer disposer);
2086 This function will make `*this` a clone of `src`. Let's explain the arguments:
2088 * The first parameter is the list to be cloned.
2089 * The second parameter is a function object that will clone `value_type` objects and
2090 return a pointer to the clone. It must implement the following function:
2091 `pointer operator()(const value_type &)`.
2092 * The second parameter is a function object that will dispose `value_type` objects. It's used first
2093 to empty the container before cloning and to dispose the elements if an exception is thrown.
2095 The cloning function works as follows:
2097 * First it clears and disposes all the elements from *this using the disposer function object.
2098 * After that it starts cloning all the elements of the source container using the cloner function object.
2099 * If any operation in the cloning function (for example, the cloner function object) throws,
2100 all the constructed elements are disposed using the disposer function object.
2103 Here is an example of `clone_from`:
2105 [import ../example/doc_clone_from.cpp]
2110 [section:function_hooks Using function hooks]
2112 A programmer might find that base or member hooks are not flexible enough in some situations.
2113 In some applications it would be optimal to put a hook deep inside a member of a class or just outside the class.
2114 [*Boost.Intrusive] has an easy option to allow such cases: [classref boost::intrusive::function_hook function_hook].
2116 This option is similar to [classref boost::intrusive::member_hook member_hook] or
2117 [classref boost::intrusive::base_hook base_hook], but the programmer can specify a function
2118 object that tells the container how to obtain a hook from a value and vice versa.
2119 The programmer just needs to define the following function object:
2123 //This functor converts between value_type and a hook_type
2127 typedef /*impl-defined*/ hook_type;
2128 typedef /*impl-defined*/ hook_ptr;
2129 typedef /*impl-defined*/ const_hook_ptr;
2130 typedef /*impl-defined*/ value_type;
2131 typedef /*impl-defined*/ pointer;
2132 typedef /*impl-defined*/ const_pointer;
2133 //Required static functions
2134 static hook_ptr to_hook_ptr (value_type &value);
2135 static const_hook_ptr to_hook_ptr(const value_type &value);
2136 static pointer to_value_ptr(hook_ptr n);
2137 static const_pointer to_value_ptr(const_hook_ptr n);
2140 Converting from values to hooks is generally easy, since most hooks are
2141 in practice members or base classes of class data members. The inverse operation
2142 is a bit more complicated, but [*Boost.Intrusive] offers a bit of help with the function
2143 [funcref boost::intrusive::get_parent_from_member get_parent_from_member],
2144 which allows easy conversions from the address of a data member to the address of
2145 the parent holding that member. Let's see a little example of
2146 [classref boost::intrusive::function_hook function_hook]:
2148 [import ../example/doc_function_hooks.cpp]
2149 [doc_function_hooks]
2154 [section:recursive Recursive Boost.Intrusive containers]
2156 [*Boost.Intrusive] containers can be used to define recursive structures very easily,
2157 allowing complex data structures with very low overhead. Let's see an example:
2159 [import ../example/doc_recursive.cpp]
2162 Recursive data structures using [*Boost.Intrusive] containers must avoid using hook deduction to avoid early type
2167 //This leads to compilation error (Recursive is instantiated by
2168 //'list' to deduce hook properties (pointer type, tag, safe-mode...)
2172 list< Recursive > l;
2176 //Ok, programmer must specify the hook type to avoid early Recursive instantiation
2179 list< Recursive, base_hook<BaseHook> > l;
2184 Member hooks are not suitable for recursive structures:
2191 Recursive(const Recursive&);
2192 Recursive & operator=(const Recursive&);
2195 list_member_hook<> memhook;
2196 list< Recursive, member_hook<Recursive, list_member_hook<>, &Recursive::memhook> > children;
2199 Specifying `&Recursive::memhook` (that is, the offset between memhook and Recursive) provokes an early
2200 instantiation of `Recursive`. To define recursive structures using member hooks, a programmer should use
2201 [classref ::boost::interprocess::function_hook function_hook]:
2203 [import ../example/doc_recursive_member.cpp]
2204 [doc_recursive_member]
2209 [section:using_smart_pointers Using smart pointers with Boost.Intrusive containers]
2211 [*Boost.Intrusive] hooks can be configured to use other pointers than raw pointers.
2212 When a [*Boost.Intrusive] hook is configured with a smart pointer as an argument,
2213 this pointer configuration is passed to the containers. For example, if the following
2214 hook is configured with a smart pointer (for example, an offset pointer from
2215 [*Boost.Interprocess]):
2217 [import ../example/doc_offset_ptr.cpp]
2220 Any intrusive list constructed using this hook will be ready for shared memory,
2221 because the intrusive list will also use offset pointers internally. For example,
2222 we can create an intrusive list in shared memory combining [*Boost.Interprocess]
2223 and [*Boost.Intrusive]:
2227 [section:smart_pointers_requirements Requirements for smart pointers compatible with Boost.Intrusive]
2229 Not every smart pointer is compatible with [*Boost.Intrusive]:
2231 * It must be compatible with C++11 [@http://en.cppreference.com/w/cpp/memory/pointer_traits `std::pointer_traits`]
2232 requirements. [*Boost.Intrusive] uses its own [classref boost::intrusive::pointer_traits pointer_traits]
2233 class to implement those features in both C++11 and C++03 compilers.
2234 * It must have the same ownership semantics as a raw pointer. This means that
2235 resource management smart pointers (like `boost::shared_ptr`) can't be used.
2237 The conversion from the smart pointer to a raw pointer will be implemented as a recursive call to
2238 `operator->()` until the function returns a raw pointer.
2244 [section:obtaining_iterators_from_values Obtaining iterators from values]
2246 [*Boost.Intrusive] offers another useful feature that's not present in STL
2247 containers: it's possible to obtain an iterator to a value from the value itself.
2248 This feature is implemented in [*Boost.Intrusive] containers by a
2249 function called `iterator_to`:
2253 iterator iterator_to(reference value);
2254 const_iterator iterator_to(const_reference value);
2256 For [*Boost.Intrusive] containers that have local iterators, like unordered
2257 associative containers, we can also obtain local iterators:
2261 local_iterator local_iterator_to(reference value);
2262 const_local_iterator local_iterator_to(const_reference value) const;
2264 For most [*Boost.Intrusive] containers
2265 ([classref boost::intrusive::list list],
2266 [classref boost::intrusive::slist slist],
2267 [classref boost::intrusive::set set],
2268 [classref boost::intrusive::multiset multiset]) we have an alternative
2269 static `s_iterator_to` function.
2271 For unordered associative containers
2272 ([classref boost::intrusive::unordered_set unordered_set],
2273 [classref boost::intrusive::multiset multiset]),
2274 `iterator_to` has no static alternative function.
2275 On the other hand, `local_iterator_to` functions
2276 have their `s_local_iterator_to` static alternatives.
2278 Alternative static functions are available under certain circumstances
2279 explained in the [link intrusive.value_traits.stateful_value_traits Stateful value traits] section;
2280 if the programmer uses hooks provided by [*Boost.Intrusive], those functions
2283 Let's see a small function that shows the use of `iterator_to` and
2284 `local_iterator_to`:
2286 [import ../example/doc_iterator_from_value.cpp]
2287 [doc_iterator_from_value]
2291 [section:any_hooks Any Hooks: A single hook for any Intrusive container]
2293 Sometimes, a class programmer wants to place a class in several intrusive
2294 containers but no at the same time. In this case, the programmer might
2295 decide to insert two hooks in the same class.
2300 : public list_base_hook<>, public slist_base_hook<> //...
2303 However, there is a more size-efficient alternative in [*Boost.Intrusive]: "any" hooks
2304 ([classref boost::intrusive::any_base_hook any_base_hook] and
2305 [classref boost::intrusive::any_member_hook any_member_hook]).
2306 These hooks can be used to store a type in several containers
2307 offered by [*Boost.Intrusive] minimizing the size of the class.
2309 These hooks support these options:
2311 * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
2312 so you can derive from more than one slist hook.
2313 Default: `tag<default_tag>`.
2315 * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
2316 `link_mode<auto_unlink>` is [*not] supported and `link_mode<safe_mode>`
2317 might offer weaker error detection in any hooks than in other hooks.
2318 Default: `link_mode<safe_link>`.
2320 * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
2321 internally in the hook and propagated to the container.
2322 Default: `void_pointer<void*>`.
2324 `auto_unlink` can't be supported because the hook does not know in which type of
2325 container might be currently inserted. Additionally, these hooks don't support `unlink()` and
2326 `swap_nodes()` operations for the same reason.
2328 Here is an example that creates a class with two any hooks, and uses one to insert the
2329 class in a [classref slist] and the other one in a [classref list].
2331 [import ../example/doc_any_hook.cpp]
2336 [section:concepts Concepts explained]
2338 This section will expand the explanation of previously presented basic concepts
2339 before explaining the customization options of [*Boost.Intrusive].
2341 * [*Node Algorithms]: A set of static functions that implement basic operations
2342 on a group of nodes: initialize a node, link_mode_type a node to a group of nodes,
2343 unlink a node from another group of nodes, etc. For example, a circular
2344 singly linked list is a group of nodes, where each node has a pointer to the
2345 next node. [*Node Algorithms] just require a [*NodeTraits]
2346 template parameter and they can work with any [*NodeTraits] class that fulfills
2347 the needed interface. As an example, here is a class that implements operations
2348 to manage a group of nodes forming a circular singly linked list:
2352 template<class NodeTraits>
2353 struct my_slist_algorithms
2355 typedef typename NodeTraits::node_ptr node_ptr;
2356 typedef typename NodeTraits::const_node_ptr const_node_ptr;
2358 //Get the previous node of "this_node"
2359 static node_ptr get_prev_node(node_ptr this_node)
2361 node_ptr p = this_node;
2362 while (this_node != NodeTraits::get_next(p))
2363 p = NodeTraits::get_next(p);
2367 // number of elements in the group of nodes containing "this_node"
2368 static std::size_t count(const_node_ptr this_node)
2370 std::size_t result = 0;
2371 const_node_ptr p = this_node;
2373 p = NodeTraits::get_next(p);
2375 } while (p != this_node);
2383 * [*Node Traits]: A class that encapsulates the basic information and
2384 operations on a node within a group of nodes:
2385 the type of the node, a function to obtain the pointer to the next node, etc.
2386 [*Node Traits] specify the configuration information [*Node Algorithms]
2387 need. Each type of [*Node Algorithm] expects an interface that compatible
2388 [*Node Traits] classes must implement.
2389 As an example, this is the definition of a [*Node Traits] class that
2390 is compatible with the previously presented `my_slist_algorithms`:
2394 struct my_slist_node_traits
2396 //The type of the node
2402 typedef node * node_ptr;
2403 typedef const node * const_node_ptr;
2405 //A function to obtain a pointer to the next node
2406 static node_ptr get_next(const_node_ptr n)
2407 { return n->next_; }
2409 //A function to set the pointer to the next node
2410 static void set_next(node_ptr n, node_ptr next)
2411 { n->next_ = next; }
2415 * [*Hook]: A class that the user must add as a base class or as a member to his own
2416 class to make that class insertable in an intrusive container. Usually the hook
2417 contains a node object that will be used to form the group of nodes:
2418 For example, the following class is a [*Hook] that the user can add as a base class,
2419 to make the user class compatible with a singly linked list container:
2423 class my_slist_base_hook
2424 //This hook contains a node, that will be used
2425 //to link the user object in the group of nodes
2426 : private my_slist_node_traits::node
2428 typedef my_slist_node_traits::node_ptr node_ptr;
2429 typedef my_slist_node_traits::const_node_ptr const_node_ptr;
2431 //Converts the generic node to the hook
2432 static my_slist_base_hook *to_hook_ptr(node_ptr p)
2433 { return static_cast<my_slist_base_hook*>(p); }
2435 //Returns the generic node stored by this hook
2436 node_ptr to_node_ptr()
2437 { return static_cast<node *const>(this); }
2443 //To make MyClass compatible with an intrusive singly linked list
2444 //derive our class from the hook.
2446 : public my_slist_base_hook
2448 void set(int value);
2455 * [*Intrusive Container]: A container that offers a STL-like interface to store
2456 user objects. An intrusive container can be templatized to store different
2457 value types that use different hooks. An intrusive container is also more elaborate
2458 than a group of nodes: it can store the number of elements to achieve constant-time
2459 size information, it can offer debugging facilities, etc.
2460 For example, an [classref boost::intrusive::slist slist] container
2461 (intrusive singly linked list) should
2462 be able to hold `MyClass` objects that might have decided to store the hook
2463 as a base class or as a member. Internally, the container will use [*Node Algorithms]
2464 to implement its operations, and an intrusive container is configured using
2465 a template parameter called [*ValueTraits]. [*ValueTraits] will contain
2466 the information to convert user classes in nodes compatible with [*Node Algorithms].
2467 For example, this a possible [classref boost::intrusive::slist slist] implementation:
2471 template<class ValueTraits, ...>
2475 typedef typename ValueTraits::value_type value_type;
2477 //More typedefs and functions
2480 //Insert the value as the first element of the list
2481 void push_front (reference value)
2483 node_ptr to_insert(ValueTraits::to_node_ptr(value));
2484 circular_list_algorithms::link_after(to_insert, get_root_node());
2491 * [*Semi-Intrusive Container]: A semi-intrusive container is similar to an
2492 intrusive container, but apart from the values to be inserted in the container,
2493 it needs additional memory (for example, auxiliary arrays or indexes).
2495 * [*Value Traits]: As we can see, to make our classes intrusive-friendly we add
2496 a simple hook as a member or base class. The hook contains a generic node
2497 that will be inserted in a group of nodes. [*Node Algorithms] just work
2498 with nodes and don't know anything about user classes. On the other
2499 hand, an intrusive container needs to know how to obtain a node from a user class,
2500 and also the inverse operation.
2501 So we can define [*ValueTraits] as the glue between user classes and nodes
2502 required by [*Node Algorithms].
2503 Let's see a possible implementation of a value traits class that glues MyClass
2504 and the node stored in the hook:
2508 struct my_slist_derivation_value_traits
2511 typedef slist_node_traits node_traits;
2512 typedef MyClass value_type;
2513 typedef node_traits::node_ptr node_ptr;
2514 typedef value_type* pointer;
2517 //Converts user's value to a generic node
2518 static node_ptr to_node_ptr(reference value)
2519 { return static_cast<slist_base_hook &>(value).to_node_ptr(); }
2521 //Converts a generic node into user's value
2522 static value_type *to_value_ptr(node_traits::node *n)
2523 { static_cast<value_type*>(slist_base_hook::to_hook_ptr(n)); }
2531 [section:node_algorithms Node algorithms with custom NodeTraits]
2533 As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive]
2534 containers are implemented using node algorithms that work on generic nodes.
2536 Sometimes, the use of intrusive containers is expensive for some environments
2537 and the programmer might want to avoid all the template instantiations
2538 related to [*Boost.Intrusive] containers. However, the user can still benefit
2539 from [*Boost.Intrusive] using the node algorithms, because some of those algorithms,
2540 like red-black tree algorithms, are not trivial to write.
2542 All node algorithm classes are
2543 templatized by a `NodeTraits` class. This class encapsulates the needed internal
2544 type declarations and operations to make a node compatible with node algorithms.
2545 Each type of node algorithms has its own requirements:
2547 [section:circular_slist_algorithms Intrusive singly linked list algorithms]
2549 These algorithms are static
2550 members of the [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms] class:
2554 template<class NodeTraits>
2555 struct circular_slist_algorithms;
2557 An empty list is formed by a node whose pointer to the next node points
2558 to itself. [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms]
2559 is configured with a NodeTraits class, which encapsulates
2560 the information about the node to be manipulated. NodeTraits must support the
2561 following interface:
2565 * `node`: The type of the node that forms the circular list
2567 * `node_ptr`: The type of a pointer to a node (usually node*)
2569 * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
2571 [*Static functions]:
2573 * `static node_ptr get_next(const_node_ptr n);`:
2574 Returns a pointer to the next node stored in "n".
2576 * `static void set_next(node_ptr n, node_ptr next);`:
2577 Sets the pointer to the next node stored in "n" to "next".
2579 Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
2582 [import ../example/doc_slist_algorithms.cpp]
2583 [doc_slist_algorithms_code]
2585 For a complete list of functions see
2586 [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms reference].
2590 [section:circular_list_algorithms Intrusive doubly linked list algorithms]
2592 These algorithms are static
2593 members of the [classref boost::intrusive::circular_list_algorithms circular_list_algorithms] class:
2597 template<class NodeTraits>
2598 struct circular_list_algorithms;
2600 An empty list is formed by a node whose pointer to the next node points
2601 to itself. [classref boost::intrusive::circular_list_algorithms circular_list_algorithms]
2602 is configured with a NodeTraits class, which encapsulates
2603 the information about the node to be manipulated. NodeTraits must support the
2604 following interface:
2608 * `node`: The type of the node that forms the circular list
2610 * `node_ptr`: The type of a pointer to a node (usually node*)
2612 * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
2614 [*Static functions]:
2616 * `static node_ptr get_next(const_node_ptr n);`:
2617 Returns a pointer to the next node stored in "n".
2619 * `static void set_next(node_ptr n, node_ptr next);`:
2620 Sets the pointer to the next node stored in "n" to "next".
2622 * `static node_ptr get_previous(const_node_ptr n);`:
2623 Returns a pointer to the previous node stored in "n".
2625 * `static void set_previous(node_ptr n, node_ptr prev);`:
2626 Sets the pointer to the previous node stored in "n" to "prev".
2628 Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
2631 [import ../example/doc_list_algorithms.cpp]
2632 [doc_list_algorithms_code]
2634 For a complete list of functions see
2635 [classref boost::intrusive::circular_list_algorithms circular_list_algorithms reference].
2639 [section:rbtree_algorithms Intrusive red-black tree algorithms]
2641 These algorithms are static
2642 members of the [classref boost::intrusive::rbtree_algorithms rbtree_algorithms] class:
2646 template<class NodeTraits>
2647 struct rbtree_algorithms;
2650 An empty tree is formed by a node whose pointer to the parent node is null,
2651 the left and right node pointers point to itself, and whose color is red.
2652 [classref boost::intrusive::rbtree_algorithms rbtree_algorithms]
2653 is configured with a NodeTraits class, which encapsulates
2654 the information about the node to be manipulated. NodeTraits must support the
2655 following interface:
2659 * `node`: The type of the node that forms the circular rbtree
2661 * `node_ptr`: The type of a pointer to a node (usually node*)
2663 * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
2665 * `color`: The type that can store the color of a node
2667 [*Static functions]:
2669 * `static node_ptr get_parent(const_node_ptr n);`:
2670 Returns a pointer to the parent node stored in "n".
2672 * `static void set_parent(node_ptr n, node_ptr p);`:
2673 Sets the pointer to the parent node stored in "n" to "p".
2675 * `static node_ptr get_left(const_node_ptr n);`:
2676 Returns a pointer to the left node stored in "n".
2678 * `static void set_left(node_ptr n, node_ptr l);`:
2679 Sets the pointer to the left node stored in "n" to "l".
2681 * `static node_ptr get_right(const_node_ptr n);`:
2682 Returns a pointer to the right node stored in "n".
2684 * `static void set_right(node_ptr n, node_ptr r);`:
2685 Sets the pointer to the right node stored in "n" to "r".
2687 * `static color get_color(const_node_ptr n);`:
2688 Returns the color stored in "n".
2690 * `static void set_color(node_ptr n, color c);`:
2691 Sets the color stored in "n" to "c".
2693 * `static color black();`:
2694 Returns a value representing the black color.
2696 * `static color red();`:
2697 Returns a value representing the red color.
2699 Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
2702 [import ../example/doc_rbtree_algorithms.cpp]
2703 [doc_rbtree_algorithms_code]
2705 For a complete list of functions see
2706 [classref boost::intrusive::rbtree_algorithms rbtree_algorithms reference].
2710 [section:splaytree_algorithms Intrusive splay tree algorithms]
2712 These algorithms are static
2713 members of the [classref boost::intrusive::splaytree_algorithms splaytree_algorithms] class:
2717 template<class NodeTraits>
2718 struct splaytree_algorithms;
2721 An empty tree is formed by a node whose pointer to the parent node is null,
2722 and whose left and right nodes pointers point to itself.
2723 [classref boost::intrusive::splaytree_algorithms splaytree_algorithms]
2724 is configured with a NodeTraits class, which encapsulates
2725 the information about the node to be manipulated. NodeTraits must support the
2726 following interface:
2730 * `node`: The type of the node that forms the circular splaytree
2732 * `node_ptr`: The type of a pointer to a node (usually node*)
2734 * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
2736 [*Static functions]:
2738 * `static node_ptr get_parent(const_node_ptr n);`:
2739 Returns a pointer to the parent node stored in "n".
2741 * `static void set_parent(node_ptr n, node_ptr p);`:
2742 Sets the pointer to the parent node stored in "n" to "p".
2744 * `static node_ptr get_left(const_node_ptr n);`:
2745 Returns a pointer to the left node stored in "n".
2747 * `static void set_left(node_ptr n, node_ptr l);`:
2748 Sets the pointer to the left node stored in "n" to "l".
2750 * `static node_ptr get_right(const_node_ptr n);`:
2751 Returns a pointer to the right node stored in "n".
2753 * `static void set_right(node_ptr n, node_ptr r);`:
2754 Sets the pointer to the right node stored in "n" to "r".
2756 Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
2759 [import ../example/doc_splaytree_algorithms.cpp]
2760 [doc_splaytree_algorithms_code]
2762 For a complete list of functions see
2763 [classref boost::intrusive::splaytree_algorithms splaytree_algorithms reference].
2767 [section:avltree_algorithms Intrusive avl tree algorithms]
2769 [classref boost::intrusive::avltree_algorithms avltree_algorithms] have the same
2770 interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
2774 template<class NodeTraits>
2775 struct avltree_algorithms;
2777 [classref boost::intrusive::avltree_algorithms avltree_algorithms]
2778 is configured with a NodeTraits class, which encapsulates
2779 the information about the node to be manipulated. NodeTraits must support the
2780 following interface:
2784 * `node`: The type of the node that forms the circular avltree
2786 * `node_ptr`: The type of a pointer to a node (usually node*)
2788 * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
2790 * `balance`: A type that can represent 3 balance types (usually an integer)
2792 [*Static functions]:
2794 * `static node_ptr get_parent(const_node_ptr n);`:
2795 Returns a pointer to the parent node stored in "n".
2797 * `static void set_parent(node_ptr n, node_ptr p);`:
2798 Sets the pointer to the parent node stored in "n" to "p".
2800 * `static node_ptr get_left(const_node_ptr n);`:
2801 Returns a pointer to the left node stored in "n".
2803 * `static void set_left(node_ptr n, node_ptr l);`:
2804 Sets the pointer to the left node stored in "n" to "l".
2806 * `static node_ptr get_right(const_node_ptr n);`:
2807 Returns a pointer to the right node stored in "n".
2809 * `static void set_right(node_ptr n, node_ptr r);`:
2810 Sets the pointer to the right node stored in "n" to "r".
2812 * `static balance get_balance(const_node_ptr n);`:
2813 Returns the balance factor stored in "n".
2815 * `static void set_balance(node_ptr n, balance b);`:
2816 Sets the balance factor stored in "n" to "b".
2818 * `static balance negative();`:
2819 Returns a value representing a negative balance factor.
2821 * `static balance zero();`:
2822 Returns a value representing a zero balance factor.
2824 * `static balance positive();`:
2825 Returns a value representing a positive balance factor.
2827 Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
2830 [import ../example/doc_avltree_algorithms.cpp]
2831 [doc_avltree_algorithms_code]
2833 For a complete list of functions see
2834 [classref boost::intrusive::avltree_algorithms avltree_algorithms reference].
2839 [section:treap_algorithms Intrusive treap algorithms]
2841 [classref boost::intrusive::treap_algorithms treap_algorithms] have the same
2842 interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
2846 template<class NodeTraits>
2847 struct treap_algorithms;
2849 [classref boost::intrusive::treap_algorithms treap_algorithms]
2850 is configured with a NodeTraits class, which encapsulates
2851 the information about the node to be manipulated. NodeTraits must support the
2852 following interface:
2856 * `node`: The type of the node that forms the circular treap
2858 * `node_ptr`: The type of a pointer to a node (usually node*)
2860 * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
2862 [*Static functions]:
2864 * `static node_ptr get_parent(const_node_ptr n);`:
2865 Returns a pointer to the parent node stored in "n".
2867 * `static void set_parent(node_ptr n, node_ptr p);`:
2868 Sets the pointer to the parent node stored in "n" to "p".
2870 * `static node_ptr get_left(const_node_ptr n);`:
2871 Returns a pointer to the left node stored in "n".
2873 * `static void set_left(node_ptr n, node_ptr l);`:
2874 Sets the pointer to the left node stored in "n" to "l".
2876 * `static node_ptr get_right(const_node_ptr n);`:
2877 Returns a pointer to the right node stored in "n".
2879 * `static void set_right(node_ptr n, node_ptr r);`:
2880 Sets the pointer to the right node stored in "n" to "r".
2882 Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
2885 [import ../example/doc_treap_algorithms.cpp]
2886 [doc_treap_algorithms_code]
2888 For a complete list of functions see
2889 [classref boost::intrusive::treap_algorithms treap_algorithms reference].
2896 /[section:sgtree_algorithms Intrusive sg tree algorithms]
2899 /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms] have the same
2900 /interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
2904 / template<class NodeTraits>
2905 / struct sgtree_algorithms;
2907 /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms]
2908 /is configured with a NodeTraits class, which encapsulates
2909 /the information about the node to be manipulated. NodeTraits must support the
2910 /following interface:
2914 /* `node`: The type of the node that forms the circular sgtree
2916 /* `node_ptr`: The type of a pointer to a node (usually node*)
2918 /* `const_node_ptr`: The type of a pointer to a const node (usually const node*)
2920 /[*Static functions]:
2922 /* `static node_ptr get_parent(const_node_ptr n);`:
2923 / Returns a pointer to the parent node stored in "n".
2925 /* `static void set_parent(node_ptr n, node_ptr p);`:
2926 / Sets the pointer to the parent node stored in "n" to "p".
2928 /* `static node_ptr get_left(const_node_ptr n);`:
2929 / Returns a pointer to the left node stored in "n".
2931 /* `static void set_left(node_ptr n, node_ptr l);`:
2932 / Sets the pointer to the left node stored in "n" to "l".
2934 /* `static node_ptr get_right(const_node_ptr n);`:
2935 / Returns a pointer to the right node stored in "n".
2937 /* `static void set_right(node_ptr n, node_ptr r);`:
2938 / Sets the pointer to the right node stored in "n" to "r".
2940 /Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
2943 /[import ../example/doc_sgtree_algorithms.cpp]
2944 /[doc_sgtree_algorithms_code]
2946 /For a complete list of functions see
2947 /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms reference].
2954 [section:value_traits Containers with custom ValueTraits]
2956 As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive]
2957 containers need a `ValueTraits` class to perform transformations between nodes and
2958 user values. `ValueTraits` can be explicitly configured (using the `value_traits<>` option)
2959 or implicitly configured (using hooks and their `base_hook<>`/`member_hook<>` options).
2960 `ValueTraits` contains
2961 all the information to glue the `value_type` of the containers and the node to be
2962 used in node algorithms, since these types can be different. Apart from this,
2963 `ValueTraits` also stores information about the link policy of the values to be inserted.
2965 Instead of using [*Boost.Intrusive] predefined hooks
2966 a user might want to develop customized containers, for example, using nodes that are
2967 optimized for a specific
2968 application or that are compatible with a legacy ABI. A user might want
2969 to have only two additional pointers in his class and insert the class in a doubly
2970 linked list sometimes and in a singly linked list in other situations. You can't
2971 achieve this using [*Boost.Intrusive] predefined hooks. Now, instead of using
2972 `base_hook<...>` or `member_hook<...>` options the user will specify the
2973 `value_traits<...>` options. Let's see how we can do this:
2975 [section:value_traits_interface ValueTraits interface]
2977 `ValueTraits` has the following interface:
2981 #include <boost/intrusive/pointer_traits.hpp>
2982 #include <boost/intrusive/link_mode.hpp>
2984 struct my_value_traits
2986 typedef implementation_defined node_traits;
2987 typedef implementation_defined value_type;
2988 typedef node_traits::node_ptr node_ptr;
2989 typedef node_traits::const_node_ptr const_node_ptr;
2990 typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
2991 <value_type>::type::pointer pointer;
2992 typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
2993 <const value_type>::type::pointer const_pointer;
2995 static const link_mode_type link_mode = some_linking_policy;
2997 static node_ptr to_node_ptr (value_type &value);
2998 static const_node_ptr to_node_ptr (const value_type &value);
2999 static pointer to_value_ptr (node_ptr n);
3000 static const_pointer to_value_ptr (const_node_ptr n);
3003 Let's explain each type and function:
3005 * [*['node_traits]]: The node configuration that is needed by node algorithms.
3006 These node traits and algorithms are
3007 described in the previous chapter: [link intrusive.node_algorithms Node Algorithms].
3009 * If my_value_traits is meant to be used with [classref boost::intrusive::slist slist],
3010 `node_traits` should follow
3011 the interface needed by [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms].
3013 * If my_value_traits is meant to be used with [classref boost::intrusive::list list],
3014 `node_traits` should follow
3015 the interface needed by [classref boost::intrusive::circular_list_algorithms circular_list_algorithms].
3017 * If my_value_traits is meant to be used with [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset],
3018 `node_traits` should follow
3019 the interface needed by [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
3021 * If my_value_traits is meant to be used with [classref boost::intrusive::unordered_set unordered_set]/
3022 [classref boost::intrusive::unordered_multiset unordered_multiset], `node_traits`
3023 should follow the interface needed by [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms].
3025 * [*['node_ptr]]: A typedef for `node_traits::node_ptr`.
3027 * [*['const_node_ptr]]: A typedef for `node_traits::const_node_ptr`.
3029 * [*['value_type]]: The type that the user wants to insert in the container. This type can be
3030 the same as `node_traits::node` but it can be different (for example, `node_traits::node`
3031 can be a member type of `value_type`). If `value_type` and `node_traits::node` are the
3032 same type, the `to_node_ptr` and `to_value_ptr` functions are trivial.
3034 * [*['pointer]]: The type of a pointer to a `value_type`. It must be the same pointer type
3035 as `node_ptr`: If `node_ptr` is `node*`, `pointer` must be `value_type*`. If
3036 `node_ptr` is `smart_ptr<node_traits::node>`, `pointer` must be `smart_ptr<value_type>`.
3037 This can be generically achieved using `boost::intrusive::pointer_traits` (portable implementation of C++11
3038 `std::pointer_traits`).
3040 * [*['const_pointer]]: The type of a pointer to a `const value_type`. It must be the same pointer type
3041 as `node_ptr`: If `node_ptr` is `node*`, `const_pointer` must be `const value_type*`. If
3042 `node_ptr` is `smart_ptr<node_traits::node>`, `const_pointer` must be `smart_ptr<const value_type>`.
3044 * [*['link_mode]]: Indicates that `value_traits` needs some additional work or checks from the
3045 container. The types are enumerations defined in the `link_mode.hpp` header.
3046 These are the possible types:
3048 * [*`normal_link`]: If this linking policy is specified in a `ValueTraits` class
3049 as the link mode, containers
3050 configured with such `ValueTraits` won't set the hooks
3051 of the erased values to a default state. Containers also won't
3052 check that the hooks of the new values are default initialized.
3054 * [*`safe_link`]: If this linking policy is specified as the link mode
3055 in a `ValueTraits` class, containers
3056 configured with this `ValueTraits` will set the hooks
3057 of the erased values to a default state. Containers also will
3058 check that the hooks of the new values are default initialized.
3060 * [*`auto_unlink`]: Same as "safe_link" but containers with
3061 constant-time size features won't be
3062 compatible with `ValueTraits` configured with this policy.
3063 Containers also know that a value can be silently erased from
3064 the container without using any function provided by the containers.
3066 * [*['static node_ptr to_node_ptr (value_type &value)]] and
3067 [*['static const_node_ptr to_node_ptr (const value_type &value)]]:
3068 These functions take a reference to a value_type and return a pointer to the node
3069 to be used with node algorithms.
3071 * [*['static pointer to_value_ptr (node_ptr n)]] and
3072 [*['static const_pointer to_value_ptr (const_node_ptr n)]]:
3073 These functions take a pointer to a node and return a pointer to the value
3074 that contains the node.
3078 [section:value_traits_example Custom ValueTraits example]
3080 Let's define our own `value_traits` class to be able to use [*Boost.Intrusive]
3081 containers with an old C structure whose definition can't be changed.
3082 That legacy type has two pointers that can be used to build singly and doubly linked
3083 lists: in singly linked lists we only need a pointer, whereas in doubly
3084 linked lists, we need two pointers. Since we only have two pointers, we can't insert
3085 the object in both a singly and a doubly linked list at the same time.
3086 This is the definition of the old node:
3088 [import ../example/doc_value_traits.cpp]
3089 [doc_value_traits_code_legacy]
3091 Now we have to define a NodeTraits class that will implement the functions/typedefs
3092 that will make the legacy node compatible with [*Boost.Intrusive] algorithms. After that,
3093 we'll define a ValueTraits class that will configure [*Boost.Intrusive] containers:
3095 [doc_value_traits_value_traits]
3097 Defining a value traits class that simply defines `value_type` as
3098 `legacy_node_traits::node` is a common approach when defining customized
3099 intrusive containers, so [*Boost.Intrusive] offers a templatized
3100 [classref boost::intrusive::trivial_value_traits trivial_value_traits] class
3101 that does exactly what we want:
3103 [doc_value_traits_trivial]
3105 Now we can just define the containers that will store the legacy abi objects and write
3108 [doc_value_traits_test]
3110 As seen, several key elements of [*Boost.Intrusive] can be reused with custom user types,
3111 if the user does not want to use the provided [*Boost.Intrusive] facilities.
3115 [section:reusing_node_algorithms Reusing node algorithms for different values]
3117 In the previous example, `legacy_node_traits::node` type and
3118 `legacy_value_traits::value_type` are the same type, but this is not necessary. It's possible
3119 to have several `ValueTraits` defining the same `node_traits` type (and thus, the same `node_traits::node`).
3120 This reduces the number of node algorithm instantiations, but
3121 now `ValueTraits::to_node_ptr` and `ValueTraits::to_value_ptr` functions need to offer
3122 conversions between both types. Let's see a small example:
3124 First, we'll define the node to be used in the algorithms. For a linked list,
3125 we just need a node that stores two pointers:
3127 [import ../example/doc_advanced_value_traits.cpp]
3128 [doc_advanced_value_traits_code]
3130 Now we'll define two different types that will be inserted in intrusive lists and
3131 a templatized `ValueTraits` that will work for both types:
3133 [doc_advanced_value_traits_value_traits]
3135 Now define two containers. Both containers will instantiate the same list algorithms
3136 (`circular_list_algorithms<simple_node_traits>`),
3137 due to the fact that the value traits used to define the containers provide the same `node_traits` type:
3139 [doc_advanced_value_traits_containers]
3141 All [*Boost.Intrusive] containers using predefined hooks use this technique to minimize code size:
3142 all possible [classref boost::intrusive::list list] containers
3143 created with predefined hooks that define the same `VoidPointer` type
3144 share the same list algorithms.
3148 [section:simplifying_value_traits Simplifying value traits definition]
3150 The previous example can be further simplified using the
3151 [classref boost::intrusive::derivation_value_traits derivation_value_traits]
3152 class to define a value traits class with a value that stores the
3153 `simple_node` as a base class:
3155 [import ../example/doc_derivation_value_traits.cpp]
3156 [doc_derivation_value_traits_value_traits]
3158 We can even choose to store `simple_node` as a member of `value_1` and `value_2`
3159 classes and use [classref boost::intrusive::member_value_traits member_value_traits]
3160 to define the needed value traits classes:
3162 [import ../example/doc_member_value_traits.cpp]
3163 [doc_member_value_traits_value_traits]
3167 [section:stateful_value_traits Stateful value traits]
3169 Until now all shown custom value traits are stateless, that is, [*the transformation between nodes
3170 and values is implemented in terms of static functions]. It's possible to use [*stateful] value traits
3171 so that we can separate nodes and values and [*avoid modifying types to insert nodes].
3172 [*Boost.Intrusive] differentiates between stateful and stateless value traits by checking if all
3173 Node <-> Value transformation functions are static or not (except for Visual 7.1, since overloaded
3174 static function detection is not possible, in this case the implementation checks if the class is empty):
3176 * If all Node <-> Value transformation functions are static , a [*stateless]
3177 value traits is assumed. transformations must be static functions.
3178 * Otherwise a [*stateful] value traits is assumed.
3180 Using stateful value traits it's possible to create containers of non-copyable/movable objects [*without modifying]
3181 the definition of the class to be inserted. This interesting property is achieved without using global variables
3182 (stateless value traits could use global variables to achieve the same goal), so:
3184 * [*Thread-safety guarantees]: Better thread-safety guarantees can be achieved with stateful
3185 value traits, since accessing global resources might require synchronization primitives that
3186 can be avoided when using internal state.
3187 * [*Flexibility]: A stateful value traits type can be configured at run-time.
3188 * [*Run-time polymorphism]: A value traits might implement node <-> value
3189 transformations as virtual functions. A single container type could be
3190 configured at run-time to use different node <-> value relationships.
3192 Stateful value traits have many advantages but also some downsides:
3194 * [*Performance]: Value traits operations should be very efficient since they are basic operations used by containers.
3195 [*A heavy node <-> value transformation will hurt intrusive containers' performance].
3196 * [*Exception guarantees]: The stateful ValueTraits must maintain no-throw guarantees, otherwise, the
3197 container invariants won't be preserved.
3198 * [*Static functions]: Some static functions offered by intrusive containers are not
3199 available because node <-> value transformations are not static.
3200 * [*Bigger iterators]: The size of some iterators is increased because the iterator
3201 needs to store a pointer to the stateful value traits to implement node to value
3202 transformations (e.g. `operator*()` and `operator->()`).
3204 An easy and useful example of stateful value traits is when an array of values can be indirectly introduced
3205 in a list guaranteeing no additional allocation apart from the initial resource reservation:
3207 [import ../example/doc_stateful_value_traits.cpp]
3208 [doc_stateful_value_traits]
3214 [section:thread_safety Thread safety guarantees]
3216 Intrusive containers have thread safety guarantees similar to STL containers.
3218 * Several threads having read or write access to different instances is safe as long as inserted
3219 objects are different.
3220 * Concurrent read-only access to the same container is safe.
3222 Some Intrusive hooks (auto-unlink hooks, for example) modify containers without
3223 having a reference to them: this is considered a write access to the container.
3225 Other functions, like checking if an object is already inserted in a container using the `is_linked()`
3226 member of safe hooks, constitute read access on the container without having a reference to it, so no other
3227 thread should have write access (direct or indirect) to that container.
3229 Since the same object can be inserted in several containers at the same time using different hooks,
3230 the thread safety of [*Boost.Intrusive] is related to the containers and also to the object whose lifetime
3231 is manually managed by the user.
3233 As we can see, the analysis of the thread-safety of a program using [*Boost.Intrusive] is harder
3234 than with non-intrusive containers.
3236 To analyze the thread safety, consider the following points:
3238 * The auto-unlink hook's destructor and `unlink()` functions modify the container indirectly.
3239 * The safe mode and auto-unlink hooks' `is_linked()` functions are a read access to the container.
3240 * Inserting an object in containers that will be modified by different threads has no thread safety
3241 guarantee, although in most platforms it will be thread-safe without locking.
3245 [section:scary_iterators Scary Iterators]
3247 The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf,
3248 SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's
3249 iterator types have no dependency on any type argument apart from the container's `value_type`,
3250 `difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal,
3251 the types of a standard container's iterators should not depend on the container's `key_compare`,
3252 `hasher`, `key_equal`, or `allocator` types.
3254 That paper demonstrated that SCARY operations were crucial to the performant implementation of common
3255 design patterns using STL components. It showed that implementations that support SCARY operations reduce
3256 object code bloat by eliminating redundant specializations of iterator and algorithm templates.
3258 [*Boost.Intrusive] containers are a bit different from standard containers. In particular, they have no
3259 allocator parameter and they can be configured with additional options not present in STL-like containers.
3260 Thus [*Boost.Intrusive] offers its own `SCARY iterator` implementation, where iterator types don't
3261 change when the container is configured with an option that does not alter the value <-> node transformation.
3262 More concretely, the following options and conditions guarantee that iterator types are unchanged:
3264 * [*All containers]: `size_type<>`, `constant_time_size<>`,
3265 * [*`slist`]: `cache_last<>`, `linear<>`,
3266 * [*`unordered_[multi]set`]: `hash<>`, `equal<>`, `power_2_buckets<>`, `cache_begin<>`.
3267 * [*All tree-like containers] (`[multi]set`, `avl_[multi]set`, `sg_[multi]set`, `bs_[multi]set`,
3268 `splay_[multi]set`, `treap_[multi]set`): `compare<>`.
3269 * [*`treap_[multi]set`]: `priority<>`
3270 * [*`bs_[multi]set`, `sg_[multi]set`, `treap_[multi]set`, `splay_[multi]set`]:
3271 They share the same iterator type when configured with the same options.
3275 [section:equal_range_stability Stability and insertion with hint in ordered associative containers with equivalent keys]
3277 [*Boost.Intrusive] ordered associative containers with equivalent keys offer stability guarantees, following
3278 [@http://open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 C++ standard library's defect #233 resolution],
3279 explained in document [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html Comments on LWG issue 233: Insertion hints in associative containers].
3282 * A ['Insert without hint] member function always insert at the upper bound of an equal range.
3283 * A ['Insert with hint] member function inserts the new value [*before the hint] if hint's and new node's keys are equivalent.
3284 * Implements Andrew Koenig ['as close as possible to hint] proposal. A new element is always be inserted as close to the hint as possible.
3285 So, for example, if there is a subsequence of equivalent values, `a.begin()` as the hint means that the new element should be inserted
3286 before the subsequence even if `a.begin()` is far away. This allows code to always append (or prepend) an equal range with something
3287 as simple as: `m.insert(m.end(), new_node);` or `m.insert(m.begin(), new_node);`
3291 [section:obtaining_same_type_reducing_space Obtaining the same types and reducing symbol length]
3293 The flexible option specification mechanism used by [*Boost.Intrusive] for hooks and containers
3294 has a couple of downsides:
3296 * If a user specifies the same options in different order or specifies some options and leaves the
3297 rest as defaults, the type of the created container/hook will be different. Sometimes
3298 this is annoying, because two programmers specifying the same options might end up with incompatible
3299 types. For example, the following two lists, although using the same options, do not have
3304 #include <boost/intrusive/list.hpp>
3306 using namespace boost::intrusive;
3308 //Explicitly specify constant-time size and size type
3309 typedef list<T, constant_time_size<true>, size_type<std::size_t> List1;
3311 //Implicitly specify constant-time size and size type
3312 typedef list<T> List2;
3314 * Option specifiers lead to long template symbols for classes and functions. Option specifiers themselves
3315 are verbose and without variadic templates, several default template parameters are assigned for
3316 non-specified options. Object and debugging information files can grow and compilation times
3317 may suffer if long names are produced.
3319 To solve these issues [*Boost.Intrusive] offers some helper metafunctions that reduce symbol lengths
3320 and create the same type if the same options (either explicitly or implicitly) are used. These also
3321 improve compilation times. All containers and hooks have their respective `make_xxx` versions.
3322 The previously shown example can be rewritten like this to obtain the same list type:
3326 #include <boost/intrusive/list.hpp>
3328 using namespace boost::intrusive;
3330 #include <boost/intrusive/list.hpp>
3332 using namespace boost::intrusive;
3334 //Explicitly specify constant-time size and size type
3335 typedef make_list<T, constant_time_size<true>, size_type<std::size_t>::type List1;
3337 //Implicitly specify constant-time size and size type
3338 typedef make_list<T>::type List2;
3340 Produced symbol lengths and compilation times will usually be shorter and object/debug files smaller.
3341 If you are concerned with file sizes and compilation times, this option is your best choice.
3345 [section:design_notes Design Notes]
3347 When designing [*Boost.Intrusive] the following guidelines have been taken into account:
3349 [section:performance_sensitive Boost.Intrusive in performance sensitive environments]
3351 [*Boost.Intrusive] should be a valuable tool in performance sensitive environments,
3352 and following this guideline, [*Boost.Intrusive] has been designed to offer well
3353 known complexity guarantees. Apart from that, some options, like optional
3354 constant-time, have been designed to offer faster complexity guarantees in some
3355 functions, like `slist::splice`.
3357 The advanced lookup and insertion functions for associative containers, taking
3358 an arbitrary key type and predicates, were designed to avoid unnecessary object
3363 [section:space_constrained Boost.Intrusive in space constrained environments]
3365 [*Boost.Intrusive] should be useful in space constrained environments,
3366 and following this guideline [*Boost.Intrusive] separates node algorithms
3367 and intrusive containers to avoid instantiating node algorithms for each
3368 user type. For example, a single class of red-black algorithms will be instantiated
3369 to implement all set and multiset containers using raw pointers. This way,
3370 [*Boost.Intrusive] seeks to avoid any code size overhead associated with templates.
3372 Apart from that, [*Boost.Intrusive] implements some size improvements: for example,
3373 red-black trees embed the color bit in the parent pointer lower bit, if nodes
3374 are two-byte aligned. The option to forgo constant-time size operations can
3375 reduce container size, and this extra size optimization is noticeable
3376 when the container is empty or contains few values.
3380 [section:basic_building_block Boost.Intrusive as a basic building block]
3382 [*Boost.Intrusive] can be a basic building block to build more complex containers
3383 and this potential has motivated many design decisions. For example, the ability
3384 to have more than one hook per user type opens the opportunity to implement multi-index
3385 containers on top of [*Boost.Intrusive].
3387 [*Boost.Intrusive] containers implement advanced functions taking function objects
3388 as arguments (`clone_from`, `erase_and_dispose`, `insert_check`, etc.). These
3389 functions come in handy when implementing non-intrusive containers
3390 (for example, STL-like containers) on top of intrusive containers.
3394 [section:extending_intrusive Extending Boost.Intrusive]
3396 [*Boost.Intrusive] offers a wide range of containers but also allows the
3397 construction of custom containers reusing [*Boost.Intrusive] elements.
3398 The programmer might want to use node algorithms directly or
3399 build special hooks that take advantage of an application environment.
3401 For example, the programmer can customize parts of [*Boost.Intrusive]
3402 to manage old data structures whose definition can't be changed.
3408 [section:performance Performance]
3410 [*Boost.Intrusive] containers offer speed improvements compared to non-intrusive containers
3413 * They minimize memory allocation/deallocation calls.
3414 * They obtain better memory locality.
3416 This section will show performance tests comparing some operations on
3417 `boost::intrusive::list` and `std::list`:
3419 * Insertions using `push_back` and container destruction will show the
3420 overhead associated with memory allocation/deallocation.
3421 * The `reverse` member function will show the advantages of the compact
3422 memory representation that can be achieved with intrusive containers.
3423 * The `sort` and `write access` tests will show the advantage of intrusive containers
3424 minimizing memory accesses compared to containers of pointers.
3426 Given an object of type `T`, [classref boost::intrusive::list boost::intrusive::list<T>]
3427 can replace `std::list<T>` to avoid memory allocation overhead,
3428 or it can replace `std::list<T*>` when the user wants containers with
3429 polymorphic values or wants to share values between several containers.
3430 Because of this versatility, the performance tests will be executed for 6 different
3433 * 3 intrusive lists holding a class named `itest_class`,
3434 each one with a different linking policy (`normal_link`, `safe_link`, `auto_unlink`).
3435 The `itest_class` objects will be tightly packed in a `std::vector<itest_class>` object.
3437 * `std::list<test_class>`, where `test_class` is exactly the same as `itest_class`,
3438 but without the intrusive hook.
3440 * `std::list<test_class*>`. The list will contain pointers to `test_class` objects
3441 tightly packed in a `std::vector<test_class>` object. We'll call this configuration ['compact pointer list]
3443 * `std::list<test_class*>`. The list will contain pointers to `test_class` objects owned by a
3444 `std::list<test_class>` object. We'll call this configuration ['disperse pointer list].
3446 Both `test_class` and `itest_class` are templatized classes that can be configured with
3447 a boolean to increase the size of the object. This way, the tests can be executed with
3448 small and big objects. Here is the first part of the testing code, which shows
3449 the definitions of `test_class` and `itest_class` classes, and some other
3452 [import ../perf/perf_list.cpp]
3453 [perf_list_value_type]
3455 As we can see, `test_class` is a very simple class holding an `int`. `itest_class`
3456 is just a class that has a base hook ([classref boost::intrusive::list_base_hook list_base_hook])
3457 and also derives from `test_class`.
3459 `func_ptr_adaptor` is just a functor adaptor to convert function objects taking
3460 `test_list` objects to function objects taking pointers to them.
3462 You can find the full test code in the
3463 [@../../libs/intrusive/perf/perf_list.cpp perf_list.cpp] source file.
3465 [section:performance_results_push_back Back insertion and destruction]
3467 The first test will measure the benefits we can obtain with intrusive containers
3468 avoiding memory allocations and deallocations. All the objects to be
3469 inserted in intrusive containers are allocated in a single allocation call,
3470 whereas `std::list` will need to allocate memory for each object and deallocate it
3471 for every erasure (or container destruction).
3473 Let's compare the code to be executed for each container type for different insertion tests:
3475 [perf_list_push_back_intrusive]
3477 For intrusive containers, all the values are created in a vector and after that
3478 inserted in the intrusive list.
3480 [perf_list_push_back_stdlist]
3482 For a standard list, elements are pushed back using push_back().
3484 [perf_list_push_back_stdptrlist]
3486 For a standard compact pointer list, elements are created in a vector and pushed back
3487 in the pointer list using push_back().
3489 [perf_list_push_back_disperse_stdptrlist]
3491 For a ['disperse pointer list], elements are created in a list and pushed back
3492 in the pointer list using push_back().
3494 These are the times in microseconds for each case, and the normalized time:
3496 [table Back insertion + destruction times for Visual C++ 7.1 / Windows XP
3497 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3498 [[`normal_link` intrusive list] [5000 / 22500] [1 / 1]]
3499 [[`safe_link` intrusive list] [7812 / 32187] [1.56 / 1.43]]
3500 [[`auto_unlink` intrusive list] [10156 / 41562] [2.03 / 1.84]]
3501 [[Standard list] [26875 / 97500] [5.37 / 4.33]]
3502 [[Standard compact pointer list] [76406 / 86718] [15.28 / 3.85]]
3503 [[Standard disperse pointer list] [146562 / 175625] [29.31 / 7.80]]
3506 [table Back insertion + destruction times for GCC 4.1.1 / MinGW over Windows XP
3507 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3508 [[`normal_link` intrusive list] [4375 / 22187] [1 / 1]]
3509 [[`safe_link` intrusive list] [7812 / 32812] [1.78 / 1.47]]
3510 [[`auto_unlink` intrusive list] [10468 / 42031] [2.39 / 1.89]]
3511 [[Standard list] [81250 / 98125] [18.57 / 4.42]]
3512 [[Standard compact pointer list] [83750 / 94218] [19.14 / 4.24]]
3513 [[Standard disperse pointer list] [155625 / 175625] [35.57 / 7.91]]
3516 [table Back insertion + destruction times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
3517 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3518 [[`normal_link` intrusive list] [4792 / 20495] [1 / 1]]
3519 [[`safe_link` intrusive list] [7709 / 30803] [1.60 / 1.5]]
3520 [[`auto_unlink` intrusive list] [10180 / 41183] [2.12 / 2.0]]
3521 [[Standard list] [17031 / 32586] [3.55 / 1.58]]
3522 [[Standard compact pointer list] [27221 / 34823] [5.68 / 1.69]]
3523 [[Standard disperse pointer list] [102272 / 60056] [21.34 / 2.93]]
3526 The results are logical: intrusive lists just need one allocation. The destruction
3527 time of the `normal_link` intrusive container is trivial (complexity: `O(1)`),
3528 whereas `safe_link` and `auto_unlink` intrusive containers need to put the hooks of
3529 erased values in the default state (complexity: `O(NumElements)`). That's why
3530 `normal_link` intrusive list shines in this test.
3532 Non-intrusive containers need to make many more allocations and that's why they
3533 lag behind. The `disperse pointer list` needs to make `NumElements*2` allocations,
3534 so the result is not surprising.
3536 The Linux test shows that standard containers perform very well against intrusive containers
3537 with big objects. Nearly the same GCC version in MinGW performs worse, so maybe
3538 a good memory allocator is the reason for these excellent results.
3542 [section:performance_results_reversing Reversing]
3544 The next test measures the time needed to complete calls to the member function `reverse()`.
3545 Values (`test_class` and `itest_class`) and lists are created as explained in the
3548 Note that for pointer lists, `reverse` [*does not need to access `test_class` values
3549 stored in another list or vector],
3550 since this function just needs to adjust internal pointers, so in theory all tested
3551 lists need to perform the same operations.
3553 These are the results:
3555 [table Reverse times for Visual C++ 7.1 / Windows XP
3556 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3557 [[`normal_link` intrusive list] [2656 / 10625] [1 / 1.83]]
3558 [[`safe_link` intrusive list] [2812 / 10937] [1.05 / 1.89]]
3559 [[`auto_unlink` intrusive list] [2710 / 10781] [1.02 / 1.86]]
3560 [[Standard list] [5781 / 14531] [2.17 / 2.51]]
3561 [[Standard compact pointer list] [5781 / 5781] [2.17 / 1]]
3562 [[Standard disperse pointer list] [10781 / 15781] [4.05 / 2.72]]
3565 [table Reverse times for GCC 4.1.1 / MinGW over Windows XP
3566 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3567 [[`normal_link` intrusive list] [2656 / 10781] [1 / 2.22]]
3568 [[`safe_link` intrusive list] [2656 / 10781] [1 / 2.22]]
3569 [[`auto_unlink` intrusive list] [2812 / 10781] [1.02 / 2.22]]
3570 [[Standard list] [4843 / 12500] [1.82 / 2.58]]
3571 [[Standard compact pointer list] [4843 / 4843] [1.82 / 1]]
3572 [[Standard disperse pointer list] [9218 / 12968] [3.47 / 2.67]]
3575 [table Reverse times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
3576 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3577 [[`normal_link` intrusive list] [2742 / 10847] [1 / 3.41]]
3578 [[`safe_link` intrusive list] [2742 / 10847] [1 / 3.41]]
3579 [[`auto_unlink` intrusive list] [2742 / 11027] [1 / 3.47]]
3580 [[Standard list] [3184 / 10942] [1.16 / 3.44]]
3581 [[Standard compact pointer list] [3207 / 3176] [1.16 / 1]]
3582 [[Standard disperse pointer list] [5814 / 13381] [2.12 / 4.21]]
3585 For small objects the results show that the compact storage of values in intrusive
3586 containers improve locality and reversing is faster than with standard containers,
3587 whose values might be dispersed in memory because each value is independently
3588 allocated. Note that the dispersed pointer list (a list of pointers to values
3589 allocated in another list) suffers more because nodes of the pointer list
3590 might be more dispersed, since allocations from both lists are interleaved
3595 //Object list (holding `test_class`)
3598 //Pointer list (holding `test_class` pointers)
3601 for(int i = 0; i < NumElements; ++i){
3602 //Allocation from the object list
3603 objects.push_back(stdlist::value_type(i));
3604 //Allocation from the pointer list
3605 l.push_back(&objects.back());
3608 For big objects the compact pointer list wins because the reversal test doesn't need access
3609 to values stored in another container. Since all the allocations for nodes of
3610 this pointer list are likely to be close (since there is no other allocation in the
3611 process until the pointer list is created) locality is better than with intrusive
3612 containers. The dispersed pointer list, as with small values, has poor locality.
3616 [section:performance_results_sorting Sorting]
3618 The next test measures the time needed to complete calls to the member function
3619 `sort(Pred pred)`. Values (`test_class` and `itest_class`) and lists are created as explained in the
3620 first section. The values will be sorted in ascending and descending order each
3621 iteration. For example, if ['l] is a list:
3625 for(int i = 0; i < NumIter; ++i){
3627 l.sort(std::greater<stdlist::value_type>());
3629 l.sort(std::less<stdlist::value_type>());
3632 For a pointer list, the function object will be adapted using `func_ptr_adaptor`:
3636 for(int i = 0; i < NumIter; ++i){
3638 l.sort(func_ptr_adaptor<std::greater<stdlist::value_type> >());
3640 l.sort(func_ptr_adaptor<std::less<stdlist::value_type> >());
3643 Note that for pointer lists, `sort` will take a function object that [*will access
3644 `test_class` values stored in another list or vector], so pointer lists will suffer
3645 an extra indirection: they will need to access the `test_class` values stored in
3646 another container to compare two elements.
3648 These are the results:
3650 [table Sort times for Visual C++ 7.1 / Windows XP
3651 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3652 [[`normal_link` intrusive list] [16093 / 38906] [1 / 1]]
3653 [[`safe_link` intrusive list] [16093 / 39062] [1 / 1]]
3654 [[`auto_unlink` intrusive list] [16093 / 38906] [1 / 1]]
3655 [[Standard list] [32343 / 56406] [2.0 / 1.44]]
3656 [[Standard compact pointer list] [33593 / 46093] [2.08 / 1.18]]
3657 [[Standard disperse pointer list] [46875 / 68593] [2.91 / 1.76]]
3660 [table Sort times for GCC 4.1.1 / MinGW over Windows XP
3661 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3662 [[`normal_link` intrusive list] [15000 / 39218] [1 / 1]]
3663 [[`safe_link` intrusive list] [15156 / 39531] [1.01 / 1.01]]
3664 [[`auto_unlink` intrusive list] [15156 / 39531] [1.01 / 1.01]]
3665 [[Standard list] [34218 / 56875] [2.28 / 1.45]]
3666 [[Standard compact pointer list] [35468 / 49218] [2.36 / 1.25]]
3667 [[Standard disperse pointer list] [47656 / 70156] [3.17 / 1.78]]
3670 [table Sort times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
3671 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3672 [[`normal_link` intrusive list] [18003 / 40795] [1 / 1]]
3673 [[`safe_link` intrusive list] [18003 / 41017] [1 / 1]]
3674 [[`auto_unlink` intrusive list] [18230 / 40941] [1.01 / 1]]
3675 [[Standard list] [26273 / 49643] [1.45 / 1.21]]
3676 [[Standard compact pointer list] [28540 / 43172] [1.58 / 1.05]]
3677 [[Standard disperse pointer list] [35077 / 57638] [1.94 / 1.41]]
3680 The results show that intrusive containers are faster than standard
3681 containers. We can see that the pointer
3682 list holding pointers to values stored in a vector is quite fast, so the extra
3683 indirection that is needed to access the value is minimized because all the values
3684 are tightly stored, improving caching. The disperse list, on the other hand, is
3685 slower because the indirection to access values stored in the object list is
3686 more expensive than accessing values stored in a vector.
3690 [section:performance_results_write_access Write access]
3692 The next test measures the time needed to iterate through all the elements of a list, and
3693 increment the value of the internal `i_` member:
3697 stdlist::iterator it(l.begin()), end(l.end());
3698 for(; it != end; ++it)
3701 Values (`test_class` and `itest_class`) and lists are created as explained in
3702 the first section. Note that for pointer lists, the iteration will suffer
3703 an extra indirection: they will need to access the `test_class` values stored in
3708 stdptrlist::iterator it(l.begin()), end(l.end());
3709 for(; it != end; ++it)
3712 These are the results:
3714 [table Write access times for Visual C++ 7.1 / Windows XP
3715 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3716 [[`normal_link` intrusive list] [2031 / 8125] [1 / 1]]
3717 [[`safe_link` intrusive list] [2031 / 8281] [1 / 1.01]]
3718 [[`auto_unlink` intrusive list] [2031 / 8281] [1 / 1.01]]
3719 [[Standard list] [4218 / 10000] [2.07 / 1.23]]
3720 [[Standard compact pointer list] [4062 / 8437] [2.0 / 1.03]]
3721 [[Standard disperse pointer list] [8593 / 13125] [4.23 / 1.61]]
3724 [table Write access times for GCC 4.1.1 / MinGW over Windows XP
3725 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3726 [[`normal_link` intrusive list] [2343 / 8281] [1 / 1]]
3727 [[`safe_link` intrusive list] [2500 / 8281] [1.06 / 1]]
3728 [[`auto_unlink` intrusive list] [2500 / 8281] [1.06 / 1]]
3729 [[Standard list] [4218 / 10781] [1.8 / 1.3]]
3730 [[Standard compact pointer list] [3906 / 8281] [1.66 / 1]]
3731 [[Standard disperse pointer list] [8281 / 13750] [3.53 / 1.66]]
3734 [table Write access times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
3735 [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
3736 [[`normal_link` intrusive list] [2286 / 8468] [1 / 1.1]]
3737 [[`safe_link` intrusive list] [2381 / 8412] [1.04 / 1.09]]
3738 [[`auto_unlink` intrusive list] [2301 / 8437] [1.01 / 1.1]]
3739 [[Standard list] [3044 / 9061] [1.33 / 1.18]]
3740 [[Standard compact pointer list] [2755 / 7660] [1.20 / 1]]
3741 [[Standard disperse pointer list] [6118 / 12453] [2.67 / 1.62]]
3744 As with the read access test, the results show that intrusive containers outperform
3745 all other containers if the values are tightly packed in a vector.
3746 The disperse list is again the slowest.
3750 [section:performance_results_conclusions Conclusions]
3752 Intrusive containers can offer performance benefits that cannot be achieved with
3753 equivalent non-intrusive containers. Memory locality improvements are noticeable
3754 when the objects to be inserted are small. Minimizing memory allocation/deallocation calls is also
3755 an important factor and intrusive containers make this simple if all objects
3756 to be inserted in intrusive containers are allocated using `std::vector` or `std::deque`.
3762 [section:release_notes Release Notes]
3764 [section:release_notes_boost_1_57_00 Boost 1.57 Release]
3766 * Experimental version of node checkers, contributed by Matei David. Many thanks!
3767 * Implemented [@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf N3644: Null Forward Iterators] from C++14.
3769 * [@https://github.com/boostorg/intrusive/pull/12 GitHub Pull #12: ['Fix MSVC14 warning C4456: declaration of 'x_parent_right' hides previous local declaration]]
3770 * [@https://svn.boost.org/trac/boost/ticket/10520 Boost Trac #10520: ['Conversion warning in intrusive/detail/utilities.hpp]]
3771 * [@https://svn.boost.org/trac/boost/ticket/10469 Boost Trac #10469: ['Erasing from intrusive unordered_multiset with optimize_multikey goes into an infinite loop]]
3775 [section:release_notes_boost_1_56_00 Boost 1.56 Release]
3777 * Improved Doxygen generated reference and updated and fixed forward-declaration header.
3779 * [*ABI breaking]: Fixed ABI regression introduced in Boost 1.55 version, mainly noticeable on MSVC compilers.
3781 * [*Source breaking]: Removed previously deprecated `xxx_dont_splay` functions from splay containers,
3782 `splay_set_base_hook` and `splay_set_member_hook`from splay containers and `bool splay = true`
3783 extra parameter in `splaytree_algorithms` functions.
3786 * [@https://svn.boost.org/trac/boost/ticket/8468 #8468: Compile error on visual studio 2010/2012 using vector with custom allocator and aligned types]
3787 * [@https://svn.boost.org/trac/boost/ticket/9332 #9332: ['"has_member_function_callable_with.hpp compile error on msvc-12.0"]].
3788 * [@https://svn.boost.org/trac/boost/ticket/9650 #9650: ['"intrusive list with stateful value traits"]].
3789 * [@https://svn.boost.org/trac/boost/ticket/9746 #9746: Modern Sun CC compiler detects error in intrusive library header]
3790 * [@https://svn.boost.org/trac/boost/ticket/9940 #9940: bad bug in intrusive list with safe_link (or auto_unlink) hooks]
3791 * [@https://svn.boost.org/trac/boost/ticket/9948 #9948: remove use of const_cast in intrusive containers]
3792 * [@https://svn.boost.org/trac/boost/ticket/9949 #9949: clear header node hooks upon intrusive container destruction]
3793 * [@https://svn.boost.org/trac/boost/ticket/9961 #9961: tests for hooks not derived frorm generic_hook]
3795 * Optimized tree rebalancing code to avoid redundant assignments.
3797 * Added 64 bit prime values for `suggested_upper_bucket_count`/`suggested_lower_bucket_count` in 64 bit platforms.
3799 * Deleted workarounds for old SUN_CC compilers, those are now unsupported as modern SunPro compilers are standard-corforming enough.
3803 [section:release_notes_boost_1_55_00 Boost 1.55 Release]
3805 * [*Source breaking]: Deprecated `xxx_dont_splay` functions from splay containers.
3806 Deprecated `splay_set_base_hook` and `splay_set_member_hook`from splay containers, use
3807 `bs_set_base_hook` or `bs_set_member_hook` instead.
3808 Both will be removed in Boost 1.56.
3810 * [*ABI breaking]: Hash containers' end iterator was implemented pointing to one-past the end of the bucket array
3811 (see [@https://svn.boost.org/trac/boost/ticket/8698 #8698]) causing severe bugs when values to be inserted
3812 where allocated next to the bucket array. End iterator implementation was changed to point to the beginning
3813 of the bucket array.
3815 * Big refactoring in order to reduce template and debug symbol bloat. Test object files have been slashed
3816 to half in MSVC compilers in Debug mode. Toolchains without Identical COMDAT Folding (ICF) should notice size improvements.
3818 * Implemented [link intrusive.scary_iterators SCARY iterators].
3822 [section:release_notes_boost_1_54_00 Boost 1.54 Release]
3824 * Added `BOOST_NO_EXCEPTIONS` support (bug [@https://svn.boost.org/trac/boost/ticket/7849 #7849]).
3828 [section:release_notes_boost_1_53_00 Boost 1.53 Release]
3831 [@https://svn.boost.org/trac/boost/ticket/7174 #7174],
3832 [@https://svn.boost.org/trac/boost/ticket/7529 #7529],
3833 [@https://svn.boost.org/trac/boost/ticket/7815 #7815].
3834 * Fixed GCC -Wshadow warnings.
3835 * Added missing `explicit` keyword in several intrusive container constructors.
3836 * Replaced deprecated BOOST_NO_XXXX with newer BOOST_NO_CXX11_XXX macros.
3837 * Small documentation fixes.
3841 [section:release_notes_boost_1_51_00 Boost 1.51 Release]
3844 [@https://svn.boost.org/trac/boost/ticket/6841 #6841],
3845 [@https://svn.boost.org/trac/boost/ticket/6907 #6907],
3846 [@https://svn.boost.org/trac/boost/ticket/6922 #6922],
3847 [@https://svn.boost.org/trac/boost/ticket/7033 #7033],
3849 * Added `bounded_range` function to trees.
3853 [section:release_notes_boost_1_49_00 Boost 1.49 Release]
3856 [@https://svn.boost.org/trac/boost/ticket/6347 #6347],
3857 [@https://svn.boost.org/trac/boost/ticket/6223 #6223],
3858 [@https://svn.boost.org/trac/boost/ticket/6153 #6153].
3863 [section:release_notes_boost_1_48_00 Boost 1.48 Release]
3866 [@https://svn.boost.org/trac/boost/ticket/4797 #4797],
3867 [@https://svn.boost.org/trac/boost/ticket/5165 #5165],
3868 [@https://svn.boost.org/trac/boost/ticket/5183 #5183],
3869 [@https://svn.boost.org/trac/boost/ticket/5191 #5191].
3873 [section:release_notes_boost_1_46_00 Boost 1.46 Release]
3876 [@https://svn.boost.org/trac/boost/ticket/4980 #4980],
3880 [section:release_notes_boost_1_45_00 Boost 1.45 Release]
3882 * Added `function_hook` option.
3884 [@https://svn.boost.org/trac/boost/ticket/2611 #2611],
3885 [@https://svn.boost.org/trac/boost/ticket/3288 #3288],
3886 [@https://svn.boost.org/trac/boost/ticket/3304 #3304],
3887 [@https://svn.boost.org/trac/boost/ticket/3489 #3489],
3888 [@https://svn.boost.org/trac/boost/ticket/3668 #3668],
3889 [@https://svn.boost.org/trac/boost/ticket/3339 #3688],
3890 [@https://svn.boost.org/trac/boost/ticket/3698 #3698],
3891 [@https://svn.boost.org/trac/boost/ticket/3706 #3706],
3892 [@https://svn.boost.org/trac/boost/ticket/3721 #3721].
3893 [@https://svn.boost.org/trac/boost/ticket/3729 #3729],
3894 [@https://svn.boost.org/trac/boost/ticket/3746 #3746],
3895 [@https://svn.boost.org/trac/boost/ticket/3781 #3781],
3896 [@https://svn.boost.org/trac/boost/ticket/3840 #3840],
3897 [@https://svn.boost.org/trac/boost/ticket/3849 #3849],
3898 [@https://svn.boost.org/trac/boost/ticket/3339 #3339],
3899 [@https://svn.boost.org/trac/boost/ticket/3419 #3419],
3900 [@https://svn.boost.org/trac/boost/ticket/3431 #3431],
3901 [@https://svn.boost.org/trac/boost/ticket/4021 #4021].
3906 [section:release_notes_boost_1_40_00 Boost 1.40 Release]
3908 * Code cleanup in bstree_algorithms.hpp and avl_tree_algorithms.hpp
3910 [@https://svn.boost.org/trac/boost/ticket/3164 #3164].
3915 [section:release_notes_boost_1_39_00 Boost 1.39 Release]
3917 * Optimized `list::merge` and `slist::merge`
3918 * `list::sort` and `slist::sort` are now stable.
3920 [@https://svn.boost.org/trac/boost/ticket/2689 #2689],
3921 [@https://svn.boost.org/trac/boost/ticket/2755 #2755],
3922 [@https://svn.boost.org/trac/boost/ticket/2786 #2786],
3923 [@https://svn.boost.org/trac/boost/ticket/2807 #2807],
3924 [@https://svn.boost.org/trac/boost/ticket/2810 #2810],
3925 [@https://svn.boost.org/trac/boost/ticket/2862 #2862].
3929 [section:release_notes_boost_1_38_00 Boost 1.38 Release]
3931 * New treap-based containers: treap, treap_set, treap_multiset.
3932 * Corrected compilation bug for Windows-based 64 bit compilers.
3933 * Corrected exception-safety bugs in container constructors.
3934 * Updated documentation to show rvalue-references functions instead of emulation functions.
3938 [section:release_notes_boost_1_37_00 Boost 1.37 Release]
3940 * Intrusive now takes advantage of compilers with variadic templates.
3941 * `clone_from` functions now copy predicates and hash functions of associative containers.
3942 * Added incremental hashing to unordered containers via `incremental<>` option.
3943 * Update some function parameters from `iterator` to `const_iterator` in containers
3944 to keep up with the draft of the next standard.
3945 * Added an option to specify include files for intrusive configurable assertion macros.
3949 [section:release_notes_boost_1_36_00 Boost 1.36 Release]
3951 * Added `linear<>` and `cache_last<>` options to singly linked lists.
3952 * Added `optimize_multikey<>` option to unordered container hooks.
3953 * Optimized unordered containers when `store_hash` option is used in the hook.
3954 * Implementation changed to be exception agnostic so that it can be used
3955 in environments without exceptions.
3956 * Added `container_from_iterator` function to tree-based containers.
3962 [section:tested_compilers Tested compilers]
3964 [*Boost.Intrusive] has been tested on the following compilers/platforms:
3972 [section:references References]
3974 * SGI's [@http://www.sgi.com/tech/stl/ STL Programmer's Guide].
3975 [*Boost.Intrusive] is based on STL concepts and interfaces.
3977 * Dr. Dobb's, September 1, 2005: [@http://www.ddj.com/architect/184402007 ['Implementing Splay Trees in C++] ].
3978 [*Boost.Intrusive] splay containers code is based on this article.
3980 * Olaf's original intrusive container library: [@http://freenet-homepage.de/turtle++/intrusive.html ['STL-like intrusive containers] ].
3984 [section:acknowledgements Acknowledgements]
3986 [*Olaf Krzikalla] would like to thank:
3988 * [*Markus Schaaf] for pointing out the possibility and the advantages of the derivation
3991 * [*Udo Steinbach] for encouragements to present this work for boost, a lot of fixes and
3992 helpful discussions.
3994 * [*Jaap Suter] for the initial hint, which eventually lead to the member value_traits.
3996 [*Ion Gaztanaga] would like to thank:
3998 * [*Olaf Krzikalla] for the permission to continue his great work.
4000 * [*Joaquin M. Lopez Munoz] for his thorough review, help, and ideas.
4002 * [*Cory Nelson], [*Daniel James], [*Dave Harris], [*Guillaume Melquiond],
4003 [*Henri Bavestrello], [*Hervé Bronnimann], [*Kai Bruning], [*Kevin Sopp],
4004 [*Paul Rose], [*Pavel Vozelinek], [*Howard Hinnant], [*Olaf Krzikalla],
4005 [*Samuel Debionne], [*Stjepan Rajko], [*Thorsten Ottosen], [*Tobias Schwinger],
4006 [*Tom Brinkman] and [*Steven Watanabe]
4007 for their comments and reviews in the Boost.Intrusive formal review.
4009 * Thanks to [*Julienne Walker] and [*The EC Team] ([@http://eternallyconfuzzled.com])
4010 for their great algorithms.
4012 * Thanks to [*Daniel K. O.] for his AVL tree rebalancing code.
4014 * Thanks to [*Ralf Mattethat] for his splay tree article and code.
4016 * Special thanks to [*Steven Watanabe] and [*Tobias Schwinger] for their
4017 invaluable suggestions and improvements.
4021 [include auto_index_helpers.qbk]
4023 [section:index Indexes]
4025 [named_index class_name Class Index]
4026 [named_index typedef_name Typedef Index]
4027 [named_index function_name Function Index]
4028 [named_index macro_name Macro Index]
4033 [xinclude autodoc.xml]