Lines Matching refs:intrusive
12 [id intrusive]
13 [dirname intrusive]
26 [*Boost.Intrusive] is a library presenting some intrusive containers to
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
35 While intrusive containers were and are widely used in C, they
37 containers which don't support intrusive techniques.[*Boost.Intrusive] wants to
38 push intrusive containers usage encapsulating the implementation in
65 [section:intrusive_vs_nontrusive Intrusive and non-intrusive containers]
67 [section:differences_intrusive_vs_nontrusive Differences between intrusive and non-intrusive contai…
69 The main difference between intrusive containers and non-intrusive containers is
70 that in C++ non-intrusive containers store [*copies] of values passed by the user.
106 On the other hand, an intrusive container does not store copies of passed objects,
109 in an intrusive container that implements a linked list, `MyClass` must contain the
134 an easy task. [*Boost.Intrusive] offers several intrusive containers and an easy
142 holding pointers to objects. That is, if you have an intrusive list holding
147 A non-intrusive container has some limitations:
158 * Before C++11, only copies of objects could be stored in non-intrusive containers. Still
169 * Operating with intrusive containers doesn't invoke any memory management at all.
178 * Intrusive containers offer better exception guarantees than non-intrusive containers.
179 In some situations intrusive containers offer a no-throw guarantee that can't be
180 achieved with non-intrusive containers.
187 …memory management is done with intrusive containers. Memory management usually is not a predictable
188 operation so complexity guarantees from non-intrusive containers are looser than the guarantees
189 offered by intrusive containers.
193 * Each type stored in an intrusive container needs additional memory holding the
195 be stored in an intrusive container [*you have to change the definition of that type]
199 * In intrusive containers you don't store a copy of an object, [*but rather the original object
201 …operators to be stored in intrusive containers. But you have to take care of possible side effects,
209 iterator invalid] without touching the intrusive container directly, because the object
212 * [*Boost.Intrusive] containers are [*non-copyable and non-assignable]. Since intrusive
217 [link intrusive.clone_from Cloning Boost.Intrusive containers] section for more information.
219 * Analyzing the thread safety of a program that uses containers is harder with intrusive container…
222 [table Summary of intrusive containers advantages and disadvantages
223 … [Intrusive] [Non-intrusive]]
240 For a performance comparison between Intrusive and Non-intrusive containers see
241 [link intrusive.performance Performance] section.
249 If you plan to insert a class in an intrusive container, you have to make some decisions
250 influencing the class definition itself. Each class that will be used in an intrusive
252 container. We will take a simple intrusive container, the intrusive list
253 ([classref boost::intrusive::list boost::intrusive::list]), for the following
255 the example using [classref boost::intrusive::list boost::intrusive::list],
260 #include <boost/intrusive/list.hpp>
262 Every class to be inserted in an intrusive container, needs to contain a hook that
267 [link intrusive.function_hooks Using function hooks], but usually base or member
272 For [classref boost::intrusive::list list], you can publicly derive from
273 [classref boost::intrusive::list_base_hook list_base_hook].
284 [classref boost::intrusive::list_base_hook list_base_hook] and hence put an object in
285 multiple intrusive lists at the same time. An incomplete type can serve as a tag.
294 [link intrusive.safe_hook Safe hooks] and [link intrusive.auto_unlink_hooks Auto-unlink hooks].
300 [link intrusive.using_smart_pointers Using smart pointers with Boost.Intrusive containers].
307 #include <boost/intrusive/list.hpp>
309 using namespace boost::intrusive;
316 After that, we can define the intrusive list:
331 [link intrusive.value_traits Containers with custom ValueTraits] section.
338 function is demanded for the container. This will instruct the intrusive
344 and the type stored in the intrusive container if `constant_time_size<true>`
352 Example of a constant-time size intrusive list that will store Foo objects, using
359 Example of an intrusive list with non constant-time size that will store Foo objects:
372 #include <boost/intrusive/list.hpp>
374 using namespace boost::intrusive;
419 #include <boost/intrusive/list.hpp>
463 You can insert the same object in several intrusive containers at the same time,
473 Even if the interface of [classref boost::intrusive::list list] is similar to
475 you directly store objects in intrusive containers, not copies. The lifetime of a
514 for an intrusive list. Indeed, dereferencing an iterator from an intrusive list is performed in
518 It's also possible to use intrusive containers when the objects to be stored can
525 Due to certain properties of intrusive containers
527 should avoid them in public interfaces of libraries. Classes to be stored in intrusive
544 …d as a base class or as a member to make the user class compatible with intrusive containers. A Ho…
546 [[Semi-Intrusive Container][Similar to an intrusive container but a semi-intrusive container needs …
554 [*Boost.Intrusive] offers a wide range of intrusive containers:
556 * [*slist]: An intrusive singly linked list. The size overhead is very small
560 * [*list]: A `std::list` like intrusive linked list. The size overhead is quite
564 * [*set/multiset/rbtree]: `std::set/std::multiset` like intrusive associative containers
569 * [*avl_set/avl_multiset/avltree]: A `std::set/std::multiset` like intrusive associative
574 * [*splay_set/splay_multiset/splaytree]: `std::set/std::multiset` like intrusive associative
580 * [*sg_set/sg_multiset/sgtree]: A `std::set/std::multiset` like intrusive associative
586 [*Boost.Intrusive] also offers semi-intrusive containers:
589 like intrusive unordered associative containers.
593 Most of these intrusive containers can be configured with constant or linear time
596 * [*Linear time size]: The intrusive container doesn't hold a size member that is
602 * [*Constant time size]: The intrusive container holds a size member that is updated
607 To make user classes compatible with these intrusive containers [*Boost.Intrusive]
617 safe state and intrusive containers check that state before inserting a value in the
630 transmitted to the containers, so all the internal pointers used by intrusive containers
634 to allow shared memory intrusive containers.
659 * Every time an object is inserted in the intrusive container, the container
663 * Every time an object is being erased from the intrusive container, the container
682 want to redefine intrusive safe-mode assertions without modifying the global
686 used in insertion functions of the intrusive containers to check that
720 [link intrusive.presenting_containers non-constant time size containers].
741 * Every time an object is inserted in the intrusive container, the container
745 * Every time an object is erased from an intrusive container, the container
767 #include <boost/intrusive/list.hpp>
769 using boost::intrusive;
806 [classref boost::intrusive::slist slist] is the simplest intrusive container of
809 [classref boost::intrusive::slist slist] is the size of 1 pointer. This
812 [classref boost::intrusive::slist::swap swap]. [classref boost::intrusive::slist slist]
824 [classref boost::intrusive::slist slist] has two hook types:
831 * [classref boost::intrusive::slist_base_hook slist_base_hook]:
833 [classref boost::intrusive::slist_base_hook slist_base_hook] to make
834 it [classref boost::intrusive::slist slist]-compatible.
841 * [classref boost::intrusive::slist_member_hook slist_member_hook]:
843 [classref boost::intrusive::slist_member_hook slist_member_hook] to make
844 it [classref boost::intrusive::slist slist]-compatible.
846 [classref boost::intrusive::slist_base_hook slist_base_hook] and
847 [classref boost::intrusive::slist_member_hook slist_member_hook]
849 the section [link intrusive.usage How to use Boost.Intrusive]:
871 [classref boost::intrusive::slist slist] receives the options explained in
872 the section [link intrusive.usage How to use Boost.Intrusive]:
877 [link intrusive.value_traits Containers with custom ValueTraits].)
885 [classref boost::intrusive::slist slist] can receive additional options:
916 [classref boost::intrusive::list list] is a doubly linked list. The memory overhead
917 it imposes is 2 pointers per node. An empty, non constant-time size [classref boost::intrusive::lis…
918 also has the size of 2 pointers. [classref boost::intrusive::list list]
919 has many more constant-time operations than [classref boost::intrusive::slist slist]
921 [classref boost::intrusive::list list] instead of
922 [classref boost::intrusive::slist slist] if the size overhead is acceptable:
927 [classref boost::intrusive::list list] has two hook types:
934 * [classref boost::intrusive::list_base_hook list_base_hook]: the user class
935 derives publicly from [classref boost::intrusive::list_base_hook list_base_hook]
936 to make it [classref boost::intrusive::list list]-compatible.
943 * [classref boost::intrusive::list_member_hook list_member_hook]:
945 [classref boost::intrusive::list_member_hook list_member_hook] to make
946 it [classref boost::intrusive::list list]-compatible.
948 [classref boost::intrusive::list_base_hook list_base_hook] and
949 [classref boost::intrusive::list_member_hook list_member_hook] receive
951 [link intrusive.usage How to use Boost.Intrusive]:
973 [classref boost::intrusive::list list] receives the same options explained in
974 the section [link intrusive.usage How to use Boost.Intrusive]:
979 [link intrusive.value_traits Containers with custom ValueTraits].)
1013 An empty, non constant-time size [classref boost::intrusive::set set],
1014 [classref boost::intrusive::multiset multiset] or
1015 [classref boost::intrusive::rbtree rbtree]
1019 searches, insertions, erasures, etc. [classref boost::intrusive::set set] and
1020 [classref boost::intrusive::multiset multiset] are the
1021 intrusive equivalents of standard `std::set` and `std::multiset` containers.
1023 [classref boost::intrusive::rbtree rbtree] is a superset of
1024 [classref boost::intrusive::set set] and
1025 [classref boost::intrusive::multiset multiset] containers that offers
1030 [classref boost::intrusive::set set],
1031 [classref boost::intrusive::multiset multiset] and
1032 [classref boost::intrusive::rbtree rbtree] share the same hooks.
1034 user type can be inserted first in a [classref boost::intrusive::multiset multiset]
1035 and after that in [classref boost::intrusive::set set] without
1043 * [classref boost::intrusive::set_base_hook set_base_hook]:
1045 [classref boost::intrusive::set_base_hook set_base_hook] to make
1046 … it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.
1053 * [classref boost::intrusive::set_member_hook set_member_hook]:
1055 [classref boost::intrusive::set_member_hook set_member_hook] to make
1056 … it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.
1058 [classref boost::intrusive::set_base_hook set_base_hook] and
1059 [classref boost::intrusive::set_member_hook set_member_hook] receive
1061 [link intrusive.usage How to use Boost.Intrusive] plus a size optimization option:
1098 [link intrusive.usage How to use Boost.Intrusive]:
1103 [link intrusive.value_traits Containers with custom ValueTraits].)
1119 [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
1139 ([classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered…
1140 are semi-intrusive containers: they need additional memory apart from the hook
1145 the contents of these semi-intrusive containers are not rehashed to maintain a
1146 load factor: that would require memory management and intrusive containers don't
1169 An empty, non constant-time size [classref boost::intrusive::unordered_set unordered_set] or
1170 [classref boost::intrusive::unordered_multiset unordered_multiset]
1175 [classref boost::intrusive::unordered_set unordered_set] or
1176 [classref boost::intrusive::unordered_multiset unordered_multiset] for complexity guarantees
1186 [classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_…
1187 … first in a [classref boost::intrusive::unordered_multiset unordered_multiset] and after that in […
1195 * [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook]:
1197 [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] to make
1198 …it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_…
1205 * [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook]:
1207 [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] to make
1208 …it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_…
1210 [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] and
1211 [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] receive
1213 [link intrusive.usage How to use Boost.Intrusive]:
1262 #include <boost/intrusive/unordered_set.hpp>
1264 using namespace boost::intrusive;
1285 [classref boost::intrusive::unordered_set unordered_set] and
1286 [classref boost::intrusive::unordered_multiset unordered_multiset]
1288 [link intrusive.usage How to use Boost.Intrusive]:
1293 [link intrusive.value_traits Containers with custom ValueTraits].)
1335 [classref boost::intrusive::unordered_multiset unordered_multiset] and
1349 [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
1381 [classref boost::intrusive::unordered_bucket unordered_bucket] and
1382 [classref boost::intrusive::unordered_bucket_ptr unordered_bucket_ptr]
1395 Implementing map-like intrusive containers is not a trivial task as
1398 it shall require that objects stored in the intrusive containers contain that `std::pair` member wi…
1400 is limiting and also not very useful in practice. Any intrusive associative container can be used l…
1401 a map using [link intrusive.advanced_lookups_insertions advanced lookup and insertions] and the user
1408 The option is called [classref boost::intrusive::key_of_value].
1410 If a user specifies that option when defining a `set/multiset` intrusive container, it specifies a …
1437 [classref boost::intrusive::avl_set avl_set],
1438 [classref boost::intrusive::avl_multiset avl_multiset] and
1439 [classref boost::intrusive::avltree avltree]. The first two are similar to
1440 [classref boost::intrusive::set set] or
1441 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1449 An empty, non constant-time size [classref boost::intrusive::avl_set avl_set],
1450 [classref boost::intrusive::avl_multiset avl_multiset] or
1451 [classref boost::intrusive::avltree avltree]
1456 [classref boost::intrusive::avl_set avl_set],
1457 [classref boost::intrusive::avl_multiset avl_multiset] and
1458 [classref boost::intrusive::avltree avltree]
1466 * [classref boost::intrusive::avl_set_base_hook avl_set_base_hook]:
1475 * [classref boost::intrusive::set_member_hook set_member_hook]:
1479 [classref boost::intrusive::avl_set_base_hook avl_set_base_hook] and
1480 [classref boost::intrusive::avl_set_member_hook avl_set_member_hook] receive
1482 [link intrusive.usage How to use Boost.Intrusive] plus an option to optimize
1520 [link intrusive.usage How to use Boost.Intrusive]:
1525 [link intrusive.value_traits Containers with custom ValueTraits].)
1541 [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
1549 [classref boost::intrusive::avl_set avl_set]/
1550 [classref boost::intrusive::avl_multiset avl_multiset]
1572 [classref boost::intrusive::splay_set splay_set],
1573 [classref boost::intrusive::splay_multiset splay_multiset] and
1574 [classref boost::intrusive::splaytree splaytree]. The first two are similar to
1575 [classref boost::intrusive::set set] or
1576 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1584 Splay tree based intrusive containers have logarithmic complexity in many
1594 replacements of [classref boost::intrusive::set set]/
1595 [classref boost::intrusive::multiset multiset], specially for const search functions,
1603 See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] se…
1622 [link intrusive.usage How to use Boost.Intrusive]:
1627 [link intrusive.value_traits Containers with custom ValueTraits].)
1643 [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
1651 [classref boost::intrusive::splay_set splay_set]/
1652 [classref boost::intrusive::splay_multiset splay_multiset]
1702 [classref boost::intrusive::sg_set sg_set],
1703 [classref boost::intrusive::sg_multiset sg_multiset] and
1704 [classref boost::intrusive::sgtree sgtree]. The first two are similar to
1705 [classref boost::intrusive::set set] or
1706 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1712 An empty, [classref boost::intrusive::sg_set sg_set],
1713 [classref boost::intrusive::sg_multiset sg_multiset] or
1714 [classref boost::intrusive::sgtree sgtree]
1719 See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] se…
1736 [link intrusive.usage How to use Boost.Intrusive]:
1741 [link intrusive.value_traits Containers with custom ValueTraits].)
1761 [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
1769 [classref boost::intrusive::sg_set sg_set]/
1770 [classref boost::intrusive::sg_multiset sg_multiset]
1798 stored in the intrusive container. This means that the priority can be stored in the value to be in…
1802 [classref boost::intrusive::treap_set treap_set],
1803 [classref boost::intrusive::treap_multiset treap_multiset] and
1804 [classref boost::intrusive::treap treap]. The first two are similar to
1805 [classref boost::intrusive::set set] or
1806 [classref boost::intrusive::multiset multiset] and the latter is a generalization
1812 An empty, [classref boost::intrusive::treap_set treap_set],
1813 [classref boost::intrusive::treap_multiset treap_multiset] or
1814 [classref boost::intrusive::treap treap]
1819 See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] se…
1836 [link intrusive.usage How to use Boost.Intrusive]:
1841 [link intrusive.value_traits Containers with custom ValueTraits].)
1866 [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
1896 [section:treap_set_exceptions Exception safety of treap-based intrusive containers]
1898 In general, intrusive containers offer strong safety guarantees, but treap containers must deal
1901 this issue degrades usual `erase(const_iterator)` no-throw guarantee. However, intrusive offers
1914 [classref boost::intrusive::treap_set treap_set]/
1915 [classref boost::intrusive::treap_multiset treap_multiset]
1937 * [classref boost::intrusive::bs_set_base_hook bs_set_base_hook]:
1946 * [classref boost::intrusive::bs_set_member_hook bs_set_member_hook]:
1950 [classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
1951 [classref boost::intrusive::bs_set_member_hook bs_set_member_hook] receive
1953 [link intrusive.usage How to use Boost.Intrusive]:
2042 [classref boost::intrusive::set set] and [classref boost::intrusive::unordered_set unordered_set]-l…
2067 See [classref boost::intrusive::set set]
2068 and [classref boost::intrusive::unordered_set unordered_set]-like containers' reference
2072 ([classref boost::intrusive::multiset multiset] and
2073 [classref boost::intrusive::unordered_multiset unordered_multiset]) there is
2099 typical usage of these functions is when intrusive associative containers are used
2100 to build non-intrusive containers and the programmer wants to speed up assignments
2118 [classref boost::intrusive::set set],
2119 [classref boost::intrusive::multiset multiset],
2120 [classref boost::intrusive::unordered_set unordered_set] and
2121 [classref boost::intrusive::unordered_multiset unordered_multiset] references).
2127 One of the most tedious tasks when using intrusive containers is the management of the erased eleme…
2129 intrusive containers, the user must explicitly destroy the object after erasing an element from the…
2131 For example, let's take the function `remove_if` from [classref boost::intrusive::list list]:
2141 [classref boost::intrusive::list list] offers:
2150 will call the "disposer" function object for every removed element. [classref boost::intrusive::lis…
2171 intrusive containers don't allocate memory at all. To implement a copy-constructor or assignment op…
2172 … clone one by one all the elements of the container and insert them in another intrusive container.
2180 `clone_from` member function of [classref boost::intrusive::list list]:
2215 [*Boost.Intrusive] has an easy option to allow such cases: [classref boost::intrusive::function_hoo…
2217 This option is similar to [classref boost::intrusive::member_hook member_hook] or
2218 [classref boost::intrusive::base_hook base_hook], but the programmer can specify a function
2244 [funcref boost::intrusive::get_parent_from_member get_parent_from_member],
2247 [classref boost::intrusive::function_hook function_hook]:
2321 Any intrusive list constructed using this hook will be ready for shared memory,
2322 because the intrusive list will also use offset pointers internally. For example,
2323 we can create an intrusive list in shared memory combining [*Boost.Interprocess]
2333 …requirements. [*Boost.Intrusive] uses its own [classref boost::intrusive::pointer_traits pointer_t…
2366 ([classref boost::intrusive::list list],
2367 [classref boost::intrusive::slist slist],
2368 [classref boost::intrusive::set set],
2369 [classref boost::intrusive::multiset multiset]) we have an alternative
2373 ([classref boost::intrusive::unordered_set unordered_set],
2374 [classref boost::intrusive::multiset multiset]),
2380 explained in the [link intrusive.value_traits.stateful_value_traits Stateful value traits] section;
2394 Sometimes, a class programmer wants to place a class in several intrusive
2405 ([classref boost::intrusive::any_base_hook any_base_hook] and
2406 [classref boost::intrusive::any_member_hook any_member_hook]).
2517 class to make that class insertable in an intrusive container. Usually the hook
2544 //To make MyClass compatible with an intrusive singly linked list
2557 user objects. An intrusive container can be templatized to store different
2558 value types that use different hooks. An intrusive container is also more elaborate
2561 For example, an [classref boost::intrusive::slist slist] container
2562 (intrusive singly linked list) should
2565 to implement its operations, and an intrusive container is configured using
2568 For example, this a possible [classref boost::intrusive::slist slist] implementation:
2592 * [*Semi-Intrusive Container]: A semi-intrusive container is similar to an
2593 intrusive container, but apart from the values to be inserted in the container,
2596 * [*Value Traits]: As we can see, to make our classes intrusive-friendly we add
2600 hand, an intrusive container needs to know how to obtain a node from a user class,
2634 As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive]
2637 Sometimes, the use of intrusive containers is expensive for some environments
2651 members of the [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms] cla…
2659 to itself. [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms]
2687 [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms reference].
2694 members of the [classref boost::intrusive::circular_list_algorithms circular_list_algorithms] class:
2702 to itself. [classref boost::intrusive::circular_list_algorithms circular_list_algorithms]
2736 [classref boost::intrusive::circular_list_algorithms circular_list_algorithms reference].
2743 members of the [classref boost::intrusive::rbtree_algorithms rbtree_algorithms] class:
2753 [classref boost::intrusive::rbtree_algorithms rbtree_algorithms]
2807 [classref boost::intrusive::rbtree_algorithms rbtree_algorithms reference].
2814 members of the [classref boost::intrusive::splaytree_algorithms splaytree_algorithms] class:
2824 [classref boost::intrusive::splaytree_algorithms splaytree_algorithms]
2864 [classref boost::intrusive::splaytree_algorithms splaytree_algorithms reference].
2870 [classref boost::intrusive::avltree_algorithms avltree_algorithms] have the same
2871 interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
2878 [classref boost::intrusive::avltree_algorithms avltree_algorithms]
2935 [classref boost::intrusive::avltree_algorithms avltree_algorithms reference].
2942 [classref boost::intrusive::treap_algorithms treap_algorithms] have the same
2943 interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
2950 [classref boost::intrusive::treap_algorithms treap_algorithms]
2990 [classref boost::intrusive::treap_algorithms treap_algorithms reference].
3000 /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms] have the same
3001 /interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
3008 /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms]
3048 /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms reference].
3057 As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive]
3082 #include <boost/intrusive/pointer_traits.hpp>
3083 #include <boost/intrusive/link_mode.hpp>
3091 typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
3093 typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
3108 described in the previous chapter: [link intrusive.node_algorithms Node Algorithms].
3110 * If my_value_traits is meant to be used with [classref boost::intrusive::slist slist],
3112 …the interface needed by [classref boost::intrusive::circular_slist_algorithms circular_slist_algor…
3114 * If my_value_traits is meant to be used with [classref boost::intrusive::list list],
3116 …the interface needed by [classref boost::intrusive::circular_list_algorithms circular_list_algorit…
3118 …lue_traits is meant to be used with [classref boost::intrusive::set set]/[classref boost::intrusiv…
3120 the interface needed by [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
3122 …* If my_value_traits is meant to be used with [classref boost::intrusive::unordered_set unordered…
3123 [classref boost::intrusive::unordered_multiset unordered_multiset], `node_traits`
3124 …should follow the interface needed by [classref boost::intrusive::circular_slist_algorithms circul…
3138 …This can be generically achieved using `boost::intrusive::pointer_traits` (portable implementation…
3200 intrusive containers, so [*Boost.Intrusive] offers a templatized
3201 [classref boost::intrusive::trivial_value_traits trivial_value_traits] class
3231 Now we'll define two different types that will be inserted in intrusive lists and
3243 all possible [classref boost::intrusive::list list] containers
3252 [classref boost::intrusive::derivation_value_traits derivation_value_traits]
3260 classes and use [classref boost::intrusive::member_value_traits member_value_traits]
3296 [*A heavy node <-> value transformation will hurt intrusive containers' performance].
3299 * [*Static functions]: Some static functions offered by intrusive containers are not
3335 than with non-intrusive containers.
3429 #include <boost/intrusive/list.hpp>
3431 using namespace boost::intrusive;
3451 #include <boost/intrusive/list.hpp>
3453 using namespace boost::intrusive;
3455 #include <boost/intrusive/list.hpp>
3457 using namespace boost::intrusive;
3492 and intrusive containers to avoid instantiating node algorithms for each
3514 functions come in handy when implementing non-intrusive containers
3515 (for example, STL-like containers) on top of intrusive containers.
3535 [*Boost.Intrusive] containers offer speed improvements compared to non-intrusive containers
3542 `boost::intrusive::list` and `std::list`:
3547 memory representation that can be achieved with intrusive containers.
3548 * The `sort` and `write access` tests will show the advantage of intrusive containers
3551 Given an object of type `T`, [classref boost::intrusive::list boost::intrusive::list<T>]
3558 * 3 intrusive lists holding a class named `itest_class`,
3563 but without the intrusive hook.
3581 is just a class that has a base hook ([classref boost::intrusive::list_base_hook list_base_hook])
3588 [@../../libs/intrusive/perf/perf_list.cpp perf_list.cpp] source file.
3592 The first test will measure the benefits we can obtain with intrusive containers
3594 inserted in intrusive containers are allocated in a single allocation call,
3602 For intrusive containers, all the values are created in a vector and after that
3603 inserted in the intrusive list.
3623 [[`normal_link` intrusive list] [5000 / 22500] [1 / 1]]
3624 [[`safe_link` intrusive list] [7812 / 32187] [1.56 / 1.43]]
3625 [[`auto_unlink` intrusive list] [10156 / 41562] [2.03 / 1.84]]
3633 [[`normal_link` intrusive list] [4375 / 22187] [1 / 1]]
3634 [[`safe_link` intrusive list] [7812 / 32812] [1.78 / 1.47]]
3635 [[`auto_unlink` intrusive list] [10468 / 42031] [2.39 / 1.89]]
3643 [[`normal_link` intrusive list] [4792 / 20495] [1 / 1]]
3644 [[`safe_link` intrusive list] [7709 / 30803] [1.60 / 1.5]]
3645 [[`auto_unlink` intrusive list] [10180 / 41183] [2.12 / 2.0]]
3651 The results are logical: intrusive lists just need one allocation. The destruction
3652 time of the `normal_link` intrusive container is trivial (complexity: `O(1)`),
3653 whereas `safe_link` and `auto_unlink` intrusive containers need to put the hooks of
3655 `normal_link` intrusive list shines in this test.
3657 Non-intrusive containers need to make many more allocations and that's why they
3661 The Linux test shows that standard containers perform very well against intrusive containers
3682 [[`normal_link` intrusive list] [2656 / 10625] [1 / 1.83]]
3683 [[`safe_link` intrusive list] [2812 / 10937] [1.05 / 1.89]]
3684 [[`auto_unlink` intrusive list] [2710 / 10781] [1.02 / 1.86]]
3692 [[`normal_link` intrusive list] [2656 / 10781] [1 / 2.22]]
3693 [[`safe_link` intrusive list] [2656 / 10781] [1 / 2.22]]
3694 [[`auto_unlink` intrusive list] [2812 / 10781] [1.02 / 2.22]]
3702 [[`normal_link` intrusive list] [2742 / 10847] [1 / 3.41]]
3703 [[`safe_link` intrusive list] [2742 / 10847] [1 / 3.41]]
3704 [[`auto_unlink` intrusive list] [2742 / 11027] [1 / 3.47]]
3710 For small objects the results show that the compact storage of values in intrusive
3736 process until the pointer list is created) locality is better than with intrusive
3777 [[`normal_link` intrusive list] [16093 / 38906] [1 / 1]]
3778 [[`safe_link` intrusive list] [16093 / 39062] [1 / 1]]
3779 [[`auto_unlink` intrusive list] [16093 / 38906] [1 / 1]]
3787 [[`normal_link` intrusive list] [15000 / 39218] [1 / 1]]
3788 [[`safe_link` intrusive list] [15156 / 39531] [1.01 / 1.01]]
3789 [[`auto_unlink` intrusive list] [15156 / 39531] [1.01 / 1.01]]
3797 [[`normal_link` intrusive list] [18003 / 40795] [1 / 1]]
3798 [[`safe_link` intrusive list] [18003 / 41017] [1 / 1]]
3799 [[`auto_unlink` intrusive list] [18230 / 40941] [1.01 / 1]]
3805 The results show that intrusive containers are faster than standard
3841 [[`normal_link` intrusive list] [2031 / 8125] [1 / 1]]
3842 [[`safe_link` intrusive list] [2031 / 8281] [1 / 1.01]]
3843 [[`auto_unlink` intrusive list] [2031 / 8281] [1 / 1.01]]
3851 [[`normal_link` intrusive list] [2343 / 8281] [1 / 1]]
3852 [[`safe_link` intrusive list] [2500 / 8281] [1.06 / 1]]
3853 [[`auto_unlink` intrusive list] [2500 / 8281] [1.06 / 1]]
3861 [[`normal_link` intrusive list] [2286 / 8468] [1 / 1.1]]
3862 [[`safe_link` intrusive list] [2381 / 8412] [1.04 / 1.09]]
3863 [[`auto_unlink` intrusive list] [2301 / 8437] [1.01 / 1.1]]
3869 As with the read access test, the results show that intrusive containers outperform
3878 equivalent non-intrusive containers. Memory locality improvements are noticeable
3880 an important factor and intrusive containers make this simple if all objects
3881 to be inserted in intrusive containers are allocated using `std::vector` or `std::deque`.
3892 …* [@https://github.com/boostorg/intrusive/issues/46 GitHub #46: ['UB due to union based type pun…
3899 …* [@https://github.com/boostorg/intrusive/pull/42 GitHub #42: ['Documentation does not describe …
3900 …* [@https://github.com/boostorg/intrusive/pull/43 GitHub #43: ['Fix tests with BOOST_INTRUSIVE_V…
3901 …* [@https://github.com/boostorg/intrusive/pull/45 GitHub #45: ['Disable variadic templates for M…
3908 …* [@https://github.com/boostorg/intrusive/pull/33 GitHub Pull #33: ['Fix compilation in case if k…
3909 …* [@https://github.com/boostorg/intrusive/issues/34 GitHub Issue #34: ['-Wdeprecated-copy on gcc9…
3910 …* [@https://github.com/boostorg/intrusive/issues/35 GitHub Issue #35: ['key_of_value on treap_set…
3911 …* [@https://github.com/boostorg/intrusive/issues/38 GitHub Issue #38: ['treap: Same type for prio…
3912 …* [@https://github.com/boostorg/intrusive/pull/39 GitHub Pull #39: ['Fix -Wextra-semi clang warni…
3919 …* [@https://github.com/boostorg/intrusive/issues/29 GitHub Issues #29: ['Uninitialized variable w…
3928 …* [@https://github.com/boostorg/intrusive/pull/23 GitHub Pull #23: ['Conditionally replace deprec…
3929 …* [@https://github.com/boostorg/intrusive/pull/24 GitHub Pull #24: ['Adds support for MSVC ARM64 …
3937 …* [@https://svn.boost.org/trac/boost/ticket/12761 Boost Trac #12761: ['intrusive::set::swap doesn…
3952 …* [@https://svn.boost.org/trac/boost/ticket/11994 Boost Trac #11994: ['Support intrusive containe…
3955 …* [@https://svn.boost.org/trac/boost/ticket/12229 Boost Trac #12229: ['intrusive::unordered_set<T…
3967 …vn.boost.org/trac/boost/ticket/11832 Boost Trac #11832: ['clang-cl + boost intrusive = miscompile]]
3970 …* [@https://github.com/boostorg/intrusive/pull/19 GitHub Pull #19: ['ebo_functor_holder: compile …
3976 * [link intrusive.advanced_lookups_insertions Advanced lookup and insertions] in ordered associati…
3980 …t.org/trac/boost/ticket/11701 Boost Trac #11701: ['Regression in boost::intrusive::set::equal_rang…
3987 * Implemented [link intrusive.map_multimap map and multimap-like interfaces].
3990 …* [@https://svn.boost.org/trac/boost/ticket/11222 Boost Trac #11222: ['intrusive/pointer_traits.h…
3998 …* [@https://svn.boost.org/trac/boost/ticket/6720 Boost Trac #6720: ['intrusive::unordered_set::c…
4010 …* [@https://github.com/boostorg/intrusive/pull/12 GitHub Pull #12: ['Fix MSVC14 warning C4456: de…
4011 ….org/trac/boost/ticket/10520 Boost Trac #10520: ['Conversion warning in intrusive/detail/utilities…
4012 …* [@https://svn.boost.org/trac/boost/ticket/10469 Boost Trac #10469: ['Erasing from intrusive uno…
4029 …* [@https://svn.boost.org/trac/boost/ticket/9650 #9650: ['"intrusive list with stateful value tra…
4030 …org/trac/boost/ticket/9746 #9746: Modern Sun CC compiler detects error in intrusive library header]
4031 …* [@https://svn.boost.org/trac/boost/ticket/9940 #9940: bad bug in intrusive list with safe_link …
4032 …* [@https://svn.boost.org/trac/boost/ticket/9948 #9948: remove use of const_cast in intrusive con…
4033 …* [@https://svn.boost.org/trac/boost/ticket/9949 #9949: clear header node hooks upon intrusive co…
4059 * Implemented [link intrusive.scary_iterators SCARY iterators].
4076 * Added missing `explicit` keyword in several intrusive container constructors.
4186 * Added an option to specify include files for intrusive configurable assertion macros.
4211 * Olaf's original intrusive container library: [@http://freenet-homepage.de/turtle++/intrusive.html…