]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/ |
2 | / Copyright (c) 2006-2013 Ion Gaztanaga | |
3 | / | |
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) | |
6 | /] | |
7 | ||
8 | [library Boost.Intrusive | |
9 | [quickbook 1.6] | |
10 | [authors [Krzikalla, Olaf], [Gaztanaga, Ion]] | |
11 | [copyright 2005 Olaf Krzikalla, 2006-2015 Ion Gaztanaga] | |
12 | [id intrusive] | |
13 | [dirname intrusive] | |
14 | [purpose Intrusive containers] | |
15 | [license | |
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]) | |
19 | ] | |
20 | ] | |
21 | ||
22 | [section:introduction Introduction] | |
23 | ||
24 | [section:introduction_presenting Presenting Boost.Intrusive] | |
25 | ||
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). | |
30 | ||
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. | |
34 | ||
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 | |
40 | [*Boost.Intrusive]. | |
41 | ||
42 | [endsect] | |
43 | ||
44 | [section:introduction_building_intrusive Building Boost.Intrusive] | |
45 | ||
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. | |
49 | ||
50 | [endsect] | |
51 | ||
52 | [endsect] | |
53 | ||
54 | [section:intrusive_vs_nontrusive Intrusive and non-intrusive containers] | |
55 | ||
56 | [section:differences_intrusive_vs_nontrusive Differences between intrusive and non-intrusive containers] | |
57 | ||
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: | |
61 | ||
62 | [c++] | |
63 | ||
64 | #include <list> | |
65 | #include <assert.h> | |
66 | ||
67 | int main() | |
68 | { | |
69 | std::list<MyClass> myclass_list; | |
70 | ||
71 | MyClass myclass(...); | |
72 | myclass_list.push_back(myclass); | |
73 | ||
74 | //The stored object is different from the original object | |
75 | assert(&myclass != &myclass_list.front()); | |
76 | return 0; | |
77 | } | |
78 | ||
79 | ||
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: | |
83 | ||
84 | [c++] | |
85 | ||
86 | //A possible implementation of a std::list<MyClass> node | |
87 | class list_node | |
88 | { | |
89 | list_node *next; | |
90 | list_node *previous; | |
91 | MyClass value; | |
92 | }; | |
93 | ||
94 | ||
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: | |
100 | ||
101 | [c++] | |
102 | ||
103 | class MyClass | |
104 | { | |
105 | MyClass *next; | |
106 | MyClass *previous; | |
107 | //Other members... | |
108 | }; | |
109 | ||
110 | int main() | |
111 | { | |
112 | acme_intrusive_list<MyClass> list; | |
113 | ||
114 | MyClass myclass; | |
115 | list.push_back(myclass); | |
116 | ||
117 | //"myclass" object is stored in the list | |
118 | assert(&myclass == &list.front()); | |
119 | return 0; | |
120 | } | |
121 | ||
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. | |
125 | ||
126 | [endsect] | |
127 | ||
128 | [section:properties_of_intrusive Properties of Boost.Intrusive containers] | |
129 | ||
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). | |
135 | ||
136 | A non-intrusive container has some limitations: | |
137 | ||
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*>`. | |
141 | ||
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. | |
146 | ||
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. | |
150 | ||
151 | * It's not possible to store a derived object in a STL-container while | |
152 | retaining its original type. | |
153 | ||
154 | Intrusive containers have some important advantages: | |
155 | ||
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. | |
158 | ||
159 | * Iterating an Intrusive container needs less memory accesses than the semantically | |
160 | equivalent container of pointers: iteration is faster. | |
161 | ||
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. | |
165 | ||
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 | |
168 | linear complexity). | |
169 | ||
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. | |
174 | ||
175 | Intrusive containers have also downsides: | |
176 | ||
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. | |
182 | ||
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). | |
188 | ||
189 | * The user [*has to manage the lifetime of inserted objects] independently from the | |
190 | containers. | |
191 | ||
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. | |
195 | ||
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. | |
202 | ||
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. | |
205 | ||
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]] | |
222 | ] | |
223 | ||
224 | For a performance comparison between Intrusive and Non-intrusive containers see | |
225 | [link intrusive.performance Performance] section. | |
226 | ||
227 | [endsect] | |
228 | ||
229 | [endsect] | |
230 | ||
231 | [section:usage How to use Boost.Intrusive] | |
232 | ||
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], | |
240 | just include: | |
241 | ||
242 | [c++] | |
243 | ||
244 | #include <boost/intrusive/list.hpp> | |
245 | ||
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. | |
253 | ||
254 | [section:usage_base_hook Using base hooks] | |
255 | ||
256 | For [classref boost::intrusive::list list], you can publicly derive from | |
257 | [classref boost::intrusive::list_base_hook list_base_hook]. | |
258 | ||
259 | [c++] | |
260 | ||
261 | template <class ...Options> | |
262 | class list_base_hook; | |
263 | ||
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: | |
266 | ||
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). | |
273 | ||
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> >` | |
280 | ||
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> >` | |
286 | ||
287 | For the following examples, let's forget the options and use the default values: | |
288 | ||
289 | [c++] | |
290 | ||
291 | #include <boost/intrusive/list.hpp> | |
292 | ||
293 | using namespace boost::intrusive; | |
294 | ||
295 | class Foo | |
296 | //Base hook with default tag, raw pointers and safe_link mode | |
297 | : public list_base_hook<> | |
298 | { /**/ }; | |
299 | ||
300 | After that, we can define the intrusive list: | |
301 | ||
302 | [c++] | |
303 | ||
304 | template <class T, class ...Options> | |
305 | class list; | |
306 | ||
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: | |
309 | ||
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. | |
320 | ||
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. | |
325 | ||
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>` | |
329 | is requested. | |
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`. | |
335 | ||
336 | Example of a constant-time size intrusive list that will store Foo objects, using | |
337 | the base hook with the default tag: | |
338 | ||
339 | [c++] | |
340 | ||
341 | typedef list<Foo> FooList; | |
342 | ||
343 | Example of an intrusive list with non constant-time size that will store Foo objects: | |
344 | ||
345 | [c++] | |
346 | ||
347 | typedef list<Foo, constant_time_size<false> > FooList; | |
348 | ||
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 | |
352 | using: | |
353 | ||
354 | [c++] | |
355 | ||
356 | #include <boost/intrusive/list.hpp> | |
357 | ||
358 | using namespace boost::intrusive; | |
359 | ||
360 | struct my_tag1; | |
361 | struct my_tag2; | |
362 | ||
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 | |
366 | { /**/ }; | |
367 | ||
368 | typedef list< Foo, base_hook<BaseHook> > FooList; | |
369 | typedef list< Foo, base_hook<BaseHook2> > FooList2; | |
370 | ||
371 | Once the list is defined, we can use it: | |
372 | ||
373 | [c++] | |
374 | ||
375 | //An object to be inserted in the list | |
376 | Foo foo_object; | |
377 | FooList list; | |
378 | ||
379 | list.push_back(object); | |
380 | ||
381 | assert(&list.front() == &foo_object); | |
382 | ||
383 | [endsect] | |
384 | ||
385 | [section:usage_member_hook Using member hooks] | |
386 | ||
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`: | |
393 | ||
394 | [c++] | |
395 | ||
396 | template <class ...Options> | |
397 | class list_member_hook; | |
398 | ||
399 | Example: | |
400 | ||
401 | [c++] | |
402 | ||
403 | #include <boost/intrusive/list.hpp> | |
404 | ||
405 | class Foo | |
406 | { | |
407 | public: | |
408 | list_member_hook<> hook_; | |
409 | //... | |
410 | }; | |
411 | ||
412 | When member hooks are used, the `member_hook` option is used to configure the | |
413 | list: | |
414 | ||
415 | [c++] | |
416 | ||
417 | //This option will configure "list" to use the member hook | |
418 | typedef member_hook<Foo, list_member_hook<>, &Foo::hook_> MemberHookOption; | |
419 | ||
420 | //This list will use the member hook | |
421 | typedef list<Foo, MemberHookOption> FooList; | |
422 | ||
423 | Now we can use the container: | |
424 | ||
425 | [c++] | |
426 | ||
427 | //An object to be inserted in the list | |
428 | Foo foo_object; | |
429 | FooList list; | |
430 | ||
431 | list.push_back(object); | |
432 | ||
433 | assert(&list.front() == &foo_object); | |
434 | ||
435 | [endsect] | |
436 | ||
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. | |
444 | ||
445 | [section:usage_both_hooks Using both hooks] | |
446 | ||
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: | |
449 | ||
450 | [import ../example/doc_how_to_use.cpp] | |
451 | [doc_how_to_use_code] | |
452 | ||
453 | [endsect] | |
454 | ||
455 | [section:usage_lifetime Object lifetime] | |
456 | ||
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: | |
461 | ||
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. | |
464 | ||
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. | |
467 | ||
468 | [endsect] | |
469 | ||
470 | ||
471 | [endsect] | |
472 | ||
473 | [section:usage_when When to use?] | |
474 | ||
475 | Intrusive containers can be used for highly optimized algorithms, where speed is a crucial | |
476 | issue and: | |
477 | ||
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. | |
485 | ||
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: | |
490 | ||
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. | |
493 | ||
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. | |
501 | ||
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: | |
505 | ||
506 | [import ../example/doc_window.cpp] | |
507 | [doc_window_code] | |
508 | ||
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. | |
514 | ||
515 | [endsect] | |
516 | ||
517 | [section:concepts_summary Concept summary] | |
518 | ||
519 | Here is a small summary of the basic concepts that will be used in the following | |
520 | chapters: | |
521 | ||
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.]] | |
532 | ] | |
533 | ||
534 | [endsect] | |
535 | ||
536 | [section:presenting_containers Presenting Boost.Intrusive containers] | |
537 | ||
538 | [*Boost.Intrusive] offers a wide range of intrusive containers: | |
539 | ||
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. | |
543 | ||
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. | |
547 | ||
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. | |
552 | ||
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. | |
557 | ||
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. | |
563 | ||
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. | |
569 | ||
570 | [*Boost.Intrusive] also offers semi-intrusive containers: | |
571 | ||
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. | |
576 | ||
577 | Most of these intrusive containers can be configured with constant or linear time | |
578 | size: | |
579 | ||
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. | |
585 | ||
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. | |
590 | ||
591 | To make user classes compatible with these intrusive containers [*Boost.Intrusive] | |
592 | offers two types of hooks for each container type: | |
593 | ||
594 | * [*Base hook]: The hook is stored as a public base class of the user class. | |
595 | ||
596 | * [*Member hook]: The hook is stored as a public member of the user class. | |
597 | ||
598 | Apart from that, [*Boost.Intrusive] offers additional features: | |
599 | ||
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. | |
606 | ||
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. | |
610 | ||
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. | |
619 | ||
620 | [endsect] | |
621 | ||
622 | [section:safe_hook Safe hooks] | |
623 | ||
624 | [section:features Features of the safe mode] | |
625 | ||
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: | |
628 | ||
629 | [c++] | |
630 | ||
631 | //Configuring the safe mode explicitly | |
632 | class Foo : public list_base_hook< link_mode<safe_link> > | |
633 | {}; | |
634 | ||
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: | |
637 | ||
638 | * Hook's constructor puts the hook in a well-known default state. | |
639 | ||
640 | * Hook's destructor checks if the hook is in the well-known default state. If not, | |
641 | an assertion is raised. | |
642 | ||
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. | |
646 | ||
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. | |
649 | ||
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. | |
655 | ||
656 | [endsect] | |
657 | ||
658 | [section:configuring Configuring safe-mode assertions] | |
659 | ||
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`. | |
664 | ||
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: | |
668 | ||
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. | |
674 | ||
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: | |
680 | ||
681 | [c++] | |
682 | ||
683 | #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT MYASSERT | |
684 | #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE <myassert.h> | |
685 | ||
686 | [endsect] | |
687 | ||
688 | [endsect] | |
689 | ||
690 | [section:auto_unlink_hooks Auto-unlink hooks] | |
691 | ||
692 | [section:auto_unlink_hooks_what What's an auto-unlink hook?] | |
693 | ||
694 | [*Boost.Intrusive] offers additional hooks with unique features: | |
695 | ||
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. | |
701 | ||
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: | |
706 | ||
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. | |
710 | ||
711 | This auto-unlink feature is useful in certain applications | |
712 | but it must be used [*very carefully]: | |
713 | ||
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 | |
716 | thread-unsafe. | |
717 | ||
718 | * Container contents change silently without modifying the container directly. | |
719 | This can lead to surprising effects. | |
720 | ||
721 | These auto-unlink hooks have also safe-mode properties: | |
722 | ||
723 | * Hooks' constructors put the hook in a well-known default state. | |
724 | ||
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. | |
728 | ||
729 | * Every time an object is erased from an intrusive container, the container | |
730 | puts the erased object in the well-known default state. | |
731 | ||
732 | [endsect] | |
733 | ||
734 | [section:auto_unlink_hooks_example Auto-unlink hook example] | |
735 | ||
736 | Let's see an example of an auto-unlink hook: | |
737 | ||
738 | [import ../example/doc_auto_unlink.cpp] | |
739 | [doc_auto_unlink_code] | |
740 | ||
741 | [endsect] | |
742 | ||
743 | [section:auto_unlink_and_constant_time Auto-unlink hooks and containers with constant-time `size()`] | |
744 | ||
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: | |
748 | ||
749 | [c++] | |
750 | ||
751 | #include <boost/intrusive/list.hpp> | |
752 | ||
753 | using boost::intrusive; | |
754 | ||
755 | struct MyTag; | |
756 | ||
757 | class MyClass : public list_base_hook< link_mode<auto_unlink> > | |
758 | {/**/}; | |
759 | ||
760 | list <MyClass, constant_time_size<true> > bad_list; | |
761 | ||
762 | int main() | |
763 | { | |
764 | bad_list list; | |
765 | return 0; | |
766 | } | |
767 | ||
768 | leads to an error similar to: | |
769 | ||
770 | [pre | |
771 | error : use of undefined type 'boost::STATIC_ASSERTION_FAILURE<false>' | |
772 | ] | |
773 | ||
774 | Pointing to code like this: | |
775 | ||
776 | [c++] | |
777 | ||
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))); | |
780 | ||
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. | |
783 | ||
784 | [endsect] | |
785 | ||
786 | [endsect] | |
787 | ||
788 | [section:slist Intrusive singly linked list: slist] | |
789 | ||
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. | |
798 | ||
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. | |
804 | ||
805 | [section:slist_hooks slist hooks] | |
806 | ||
807 | Like the rest of [*Boost.Intrusive] containers, | |
808 | [classref boost::intrusive::slist slist] has two hook types: | |
809 | ||
810 | [c++] | |
811 | ||
812 | template <class ...Options> | |
813 | class slist_base_hook; | |
814 | ||
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. | |
819 | ||
820 | [c++] | |
821 | ||
822 | template <class ...Options> | |
823 | class slist_member_hook; | |
824 | ||
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. | |
829 | ||
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]: | |
834 | ||
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>`. | |
838 | ||
839 | * [*`link_mode<link_mode_type LinkMode>`]: The linking policy. | |
840 | Default: `link_mode<safe_link>`. | |
841 | ||
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*>`. | |
845 | ||
846 | [endsect] | |
847 | ||
848 | [section:slist_container slist container] | |
849 | ||
850 | [c++] | |
851 | ||
852 | template <class T, class ...Options> | |
853 | class slist; | |
854 | ||
855 | [classref boost::intrusive::slist slist] receives the options explained in | |
856 | the section [link intrusive.usage How to use Boost.Intrusive]: | |
857 | ||
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].) | |
862 | ||
863 | * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation. | |
864 | Default: `constant_time_size<true>` | |
865 | ||
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>`. | |
868 | ||
869 | [classref boost::intrusive::slist slist] can receive additional options: | |
870 | ||
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. | |
880 | ||
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. | |
884 | ||
885 | [endsect] | |
886 | ||
887 | [section:slist_example Example] | |
888 | ||
889 | Now let's see a small example using both hooks: | |
890 | ||
891 | [import ../example/doc_slist.cpp] | |
892 | [doc_slist_code] | |
893 | ||
894 | [endsect] | |
895 | ||
896 | [endsect] | |
897 | ||
898 | [section:list Intrusive doubly linked list: list] | |
899 | ||
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: | |
907 | ||
908 | [section:list_hooks list hooks] | |
909 | ||
910 | Like the rest of [*Boost.Intrusive] containers, | |
911 | [classref boost::intrusive::list list] has two hook types: | |
912 | ||
913 | [c++] | |
914 | ||
915 | template <class ...Options> | |
916 | class list_base_hook; | |
917 | ||
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. | |
921 | ||
922 | [c++] | |
923 | ||
924 | template <class ...Options> | |
925 | class list_member_hook; | |
926 | ||
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. | |
931 | ||
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]: | |
936 | ||
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>`. | |
940 | ||
941 | * [*`link_mode<link_mode_type LinkMode>`]: The linking policy. | |
942 | Default: `link_mode<safe_link>`. | |
943 | ||
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*>`. | |
947 | ||
948 | [endsect] | |
949 | ||
950 | [section:list_container list container] | |
951 | ||
952 | [c++] | |
953 | ||
954 | template <class T, class ...Options> | |
955 | class list; | |
956 | ||
957 | [classref boost::intrusive::list list] receives the same options explained in | |
958 | the section [link intrusive.usage How to use Boost.Intrusive]: | |
959 | ||
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].) | |
964 | ||
965 | * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation. | |
966 | Default: `constant_time_size<true>` | |
967 | ||
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>` | |
970 | ||
971 | [endsect] | |
972 | ||
973 | [section:list_example Example] | |
974 | ||
975 | Now let's see a small example using both hooks: | |
976 | ||
977 | [import ../example/doc_list.cpp] | |
978 | [doc_list_code] | |
979 | ||
980 | [endsect] | |
981 | ||
982 | [endsect] | |
983 | ||
984 | [section:set_multiset Intrusive associative containers: set, multiset, rbtree] | |
985 | ||
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 | |
990 | red-black trees. | |
991 | ||
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). | |
996 | ||
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 | |
1002 | operations like | |
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. | |
1006 | ||
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. | |
1011 | ||
1012 | [section:set_multiset_hooks set, multiset and rbtree hooks] | |
1013 | ||
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. | |
1021 | ||
1022 | [c++] | |
1023 | ||
1024 | template <class ...Options> | |
1025 | class set_base_hook; | |
1026 | ||
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. | |
1031 | ||
1032 | [c++] | |
1033 | ||
1034 | template <class ...Options> | |
1035 | class set_member_hook; | |
1036 | ||
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. | |
1041 | ||
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: | |
1046 | ||
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>`. | |
1050 | ||
1051 | * [*`link_mode<link_mode_type LinkMode>`]: The linking policy. | |
1052 | Default: `link_mode<safe_link>`. | |
1053 | ||
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*>`. | |
1057 | ||
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>`. | |
1065 | ||
1066 | [endsect] | |
1067 | ||
1068 | [section:set_multiset_containers set, multiset and rbtree containers] | |
1069 | ||
1070 | [c++] | |
1071 | ||
1072 | template <class T, class ...Options> | |
1073 | class set; | |
1074 | ||
1075 | template <class T, class ...Options> | |
1076 | class multiset; | |
1077 | ||
1078 | template <class T, class ...Options> | |
1079 | class rbtree; | |
1080 | ||
1081 | These containers receive the same options explained in the section | |
1082 | [link intrusive.usage How to use Boost.Intrusive]: | |
1083 | ||
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].) | |
1088 | ||
1089 | * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation. | |
1090 | Default: `constant_time_size<true>` | |
1091 | ||
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>` | |
1094 | ||
1095 | And they also can receive an additional option: | |
1096 | ||
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<key_type> >` | |
1100 | ||
1101 | * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will | |
1102 | define the `key_type` of the value type to be stored. This type will allow a map-like interface. See | |
1103 | [link intrusive.map_multimap Map and multimap-like interface with set and multiset] | |
1104 | for details. Default: `key_type` is equal to `value_type` (set-like interface). | |
1105 | ||
1106 | [endsect] | |
1107 | ||
1108 | [section:set_multiset_example Example] | |
1109 | ||
1110 | Now let's see a small example using both hooks and both containers: | |
1111 | ||
1112 | [import ../example/doc_set.cpp] | |
1113 | [doc_set_code] | |
1114 | ||
1115 | [endsect] | |
1116 | ||
1117 | [endsect] | |
1118 | ||
1119 | [section:unordered_set_unordered_multiset Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset] | |
1120 | ||
1121 | [*Boost.Intrusive] also offers hashed containers that can be very useful to implement | |
1122 | fast-lookup containers. These containers | |
1123 | ([classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_multiset unordered_multiset]) | |
1124 | are semi-intrusive containers: they need additional memory apart from the hook | |
1125 | stored in the `value_type`. This additional | |
1126 | memory must be passed in the constructor of the container. | |
1127 | ||
1128 | Unlike C++ TR1 unordered associative containers (which are also hashed containers), | |
1129 | the contents of these semi-intrusive containers are not rehashed to maintain a | |
1130 | load factor: that would require memory management and intrusive containers don't | |
1131 | implement any memory management at all. However, the user can request an explicit | |
1132 | rehashing passing a new bucket array. | |
1133 | This also offers an additional guarantee over TR1 unordered associative containers: | |
1134 | [*iterators are not invalidated when inserting an element] in the container. | |
1135 | ||
1136 | As with TR1 unordered associative containers, rehashing invalidates iterators, | |
1137 | changes ordering between elements and changes which buckets elements appear in, | |
1138 | but does not invalidate pointers or references to elements. | |
1139 | ||
1140 | Apart from expected hash and equality function objects, [*Boost.Intrusive] unordered | |
1141 | associative containers' constructors take an argument specifying an auxiliary | |
1142 | bucket vector to be used by the container. | |
1143 | ||
1144 | [section:unordered_set_unordered_multiset_performance unordered_set and unordered_multiset performance notes] | |
1145 | ||
1146 | The size overhead for a hashed container is moderate: 1 pointer per value plus | |
1147 | a bucket array per container. The size of an element of the bucket array | |
1148 | is usually one pointer. To obtain a good performance hashed container, | |
1149 | the bucket length is usually the same as the number of elements that the | |
1150 | container contains, so a well-balanced hashed container (`bucket_count()` is | |
1151 | equal to `size()` ) will have an equivalent overhead of two pointers per element. | |
1152 | ||
1153 | An empty, non constant-time size [classref boost::intrusive::unordered_set unordered_set] or | |
1154 | [classref boost::intrusive::unordered_multiset unordered_multiset] | |
1155 | has also the size of `bucket_count()` pointers. | |
1156 | ||
1157 | Insertions, erasures, and searches, have amortized constant-time complexity in | |
1158 | hashed containers. However, some worst-case guarantees are linear. See | |
1159 | [classref boost::intrusive::unordered_set unordered_set] or | |
1160 | [classref boost::intrusive::unordered_multiset unordered_multiset] for complexity guarantees | |
1161 | of each operation. | |
1162 | ||
1163 | [*Be careful with non constant-time size hashed containers]: some operations, like | |
1164 | `empty()`, have linear complexity, unlike other [*Boost.Intrusive] containers. | |
1165 | ||
1166 | [endsect] | |
1167 | ||
1168 | [section:unordered_set_unordered_multiset_hooks unordered_set and unordered_multiset hooks] | |
1169 | ||
1170 | [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 | |
1171 | 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 | |
1172 | changing the definition of the user class. | |
1173 | ||
1174 | [c++] | |
1175 | ||
1176 | template <class ...Options> | |
1177 | class unordered_set_base_hook; | |
1178 | ||
1179 | * [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook]: | |
1180 | the user class derives publicly from | |
1181 | [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] to make | |
1182 | it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible. | |
1183 | ||
1184 | [c++] | |
1185 | ||
1186 | template <class ...Options> | |
1187 | class unordered_set_member_hook; | |
1188 | ||
1189 | * [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook]: | |
1190 | the user class contains a public | |
1191 | [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] to make | |
1192 | it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible. | |
1193 | ||
1194 | [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] and | |
1195 | [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] receive | |
1196 | the same options explained in the section | |
1197 | [link intrusive.usage How to use Boost.Intrusive]: | |
1198 | ||
1199 | * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag, | |
1200 | so you can derive from more than one base hook. | |
1201 | Default: `tag<default_tag>`. | |
1202 | ||
1203 | * [*`link_mode<link_mode_type LinkMode>`]: The linking policy. | |
1204 | Default: `link_mode<safe_link>`. | |
1205 | ||
1206 | * [*`void_pointer<class VoidPointer>`]: The pointer type to be used | |
1207 | internally in the hook and propagated to the container. | |
1208 | Default: `void_pointer<void*>`. | |
1209 | ||
1210 | Apart from them, these hooks offer additional options: | |
1211 | ||
1212 | * [*`store_hash<bool Enabled>`]: This option reserves additional space in | |
1213 | the hook to store the hash value of the object once it's introduced in the | |
1214 | container. When this option is used, the unordered container will store | |
1215 | the calculated hash value in the hook and rehashing operations won't need | |
1216 | to recalculate the hash of the value. | |
1217 | This option will improve the performance of unordered containers when | |
1218 | rehashing is frequent or hashing the value is a slow operation. | |
1219 | Default: `store_hash<false>`. | |
1220 | ||
1221 | * [*`optimize_multikey<bool Enabled>`]: This option reserves additional space in | |
1222 | the hook that will be used to group equal elements in unordered multisets, | |
1223 | improving significantly the performance when many equal values are inserted | |
1224 | in these containers. Default: `optimize_multikey<false>`. | |
1225 | ||
1226 | [endsect] | |
1227 | ||
1228 | [section:unordered_set_unordered_multiset_containers unordered_set and unordered_multiset containers] | |
1229 | ||
1230 | [c++] | |
1231 | ||
1232 | template<class T, class ...Options> | |
1233 | class unordered_set; | |
1234 | ||
1235 | template<class T, class ...Options> | |
1236 | class unordered_multiset; | |
1237 | ||
1238 | As mentioned, unordered containers need an auxiliary array to work. [*Boost.Intrusive] | |
1239 | unordered containers receive this auxiliary array packed in a type called `bucket_traits` | |
1240 | (which can be also customized by a container option). All unordered containers receive | |
1241 | a `bucket_traits` object in their constructors. The default `bucket_traits` class | |
1242 | is initialized with a pointer to an array of buckets and its size: | |
1243 | ||
1244 | [c++] | |
1245 | ||
1246 | #include <boost/intrusive/unordered_set.hpp> | |
1247 | ||
1248 | using namespace boost::intrusive; | |
1249 | ||
1250 | struct MyClass : public unordered_set_base_hook<> | |
1251 | {}; | |
1252 | ||
1253 | typedef unordered_set<MyClass>::bucket_type bucket_type; | |
1254 | typedef unordered_set<MyClass>::bucket_traits bucket_traits; | |
1255 | ||
1256 | int main() | |
1257 | { | |
1258 | bucket_type buckets[100]; | |
1259 | unordered_set<MyClass> uset(bucket_traits(buckets, 100)); | |
1260 | return 0; | |
1261 | } | |
1262 | ||
1263 | Each hashed container needs [*its own bucket traits], that is, [*its own | |
1264 | bucket vector]. Two hashed containers | |
1265 | [*can't] share the same `bucket_type` elements. The bucket array [*must] be | |
1266 | destroyed [*after] the container using it is destroyed, otherwise, the result | |
1267 | is undefined. | |
1268 | ||
1269 | [classref boost::intrusive::unordered_set unordered_set] and | |
1270 | [classref boost::intrusive::unordered_multiset unordered_multiset] | |
1271 | receive the same options explained in the section | |
1272 | [link intrusive.usage How to use Boost.Intrusive]: | |
1273 | ||
1274 | * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] / | |
1275 | [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used | |
1276 | to configure the container. (To learn about value traits go to the section | |
1277 | [link intrusive.value_traits Containers with custom ValueTraits].) | |
1278 | ||
1279 | * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation. | |
1280 | Default: `constant_time_size<true>` | |
1281 | ||
1282 | * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size | |
1283 | of the container. Default: `size_type<std::size_t>` | |
1284 | ||
1285 | And they also can receive additional options: | |
1286 | ||
1287 | * [*`equal<class Equal>`]: Equality function for the objects to be inserted | |
1288 | in containers. Default: `equal< std::equal_to<T> >` | |
1289 | ||
1290 | * [*`hash<class Hash>`]: Hash function to be used in the container. | |
1291 | Default: `hash< boost::hash<T> >` | |
1292 | ||
1293 | * [*`bucket_traits<class BucketTraits>`]: A type that wraps the bucket vector to | |
1294 | be used by the unordered container. Default: a type initialized by the address | |
1295 | and size of a bucket array and stores both variables internally. | |
1296 | ||
1297 | * [*`power_2_buckets<bool Enabled>`]: The user guarantees that only bucket arrays | |
1298 | with power of two length will be used. The container will then use masks instead of modulo | |
1299 | operations to obtain the bucket number from the hash value. Masks are faster than | |
1300 | modulo operations and for some applications modulo operations can impose | |
1301 | a considerable overhead. In debug mode an assertion will be raised if the user | |
1302 | provides a bucket length that is not power of two. | |
1303 | Default: `power_2_buckets<false>`. | |
1304 | ||
1305 | * [*`cache_begin<bool Enabled>`]: | |
1306 | [*Note: this option is not compatible with `auto_unlink` hooks]. | |
1307 | Due to its internal structure, finding the first | |
1308 | element of an unordered container (`begin()` operation) is | |
1309 | amortized constant-time. It's possible to speed up `begin()` and other operations | |
1310 | related to it (like `clear()`) if the container caches internally the position | |
1311 | of the first element. This imposes the overhead of one pointer to the size | |
1312 | of the container. Default: `cache_begin<false>`. | |
1313 | ||
1314 | * [*`compare_hash<bool Enabled>`]: | |
1315 | [*Note: this option requires `store_hash<true>` option in the hook]. | |
1316 | When the comparison function is expensive, | |
1317 | (e.g. strings with a long common predicate) sometimes (specially when the | |
1318 | load factor is high or we have many equivalent elements in an | |
1319 | [classref boost::intrusive::unordered_multiset unordered_multiset] and | |
1320 | no `optimize_multikey<>` is activated in the hook) | |
1321 | the equality function is a performance problem. Two equal values must have | |
1322 | equal hashes, so comparing the hash values of two elements before using the | |
1323 | comparison functor can speed up some implementations. | |
1324 | ||
1325 | * [*`incremental<bool Enabled>`]: Activates incremental hashing (also known as Linear Hashing). | |
1326 | This option implies `power_2_buckets<true>` and the container will require power of two buckets. | |
1327 | For more information on incremental hashing, see | |
1328 | [@http://en.wikipedia.org/wiki/Linear_hashing `Linear hash` on Wikipedia] | |
1329 | Default: `incremental<false>` | |
1330 | ||
1331 | * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will | |
1332 | define the `key_type` of the value type to be stored. This type will allow a map-like interface. See | |
1333 | [link intrusive.map_multimap Map and multimap-like interface with set and multiset] | |
1334 | for details. Default: `key_type` is equal to `value_type` (set-like interface). | |
1335 | ||
1336 | [endsect] | |
1337 | ||
1338 | [section:unordered_set_unordered_multiset_example Example] | |
1339 | ||
1340 | Now let's see a small example using both hooks and both containers: | |
1341 | ||
1342 | [import ../example/doc_unordered_set.cpp] | |
1343 | [doc_unordered_set_code] | |
1344 | ||
1345 | [endsect] | |
1346 | ||
1347 | [section:custom_bucket_traits Custom bucket traits] | |
1348 | ||
1349 | Instead of using the default `bucket_traits` class to store the bucket array, a user | |
1350 | can define his own class to store the bucket array using the [*['bucket_traits<>]] | |
1351 | option. A user-defined bucket-traits must fulfill the following interface: | |
1352 | ||
1353 | [c++] | |
1354 | ||
1355 | class my_bucket_traits | |
1356 | { | |
1357 | bucket_ptr bucket_begin(); | |
1358 | const_bucket_ptr bucket_begin() const; | |
1359 | std::size_t bucket_count() const; | |
1360 | }; | |
1361 | ||
1362 | ||
1363 | The following bucket traits just stores a pointer to the bucket | |
1364 | array but the size is a compile-time constant. Note the use of the auxiliary | |
1365 | [classref boost::intrusive::unordered_bucket unordered_bucket] and | |
1366 | [classref boost::intrusive::unordered_bucket_ptr unordered_bucket_ptr] | |
1367 | utilities to obtain the type of the bucket and its pointer before defining | |
1368 | the unordered container: | |
1369 | ||
1370 | [import ../example/doc_bucket_traits.cpp] | |
1371 | [doc_bucket_traits] | |
1372 | ||
1373 | [endsect] | |
1374 | ||
1375 | [endsect] | |
1376 | ||
1377 | [section:map_multimap Map and multimap-like interface for associative containers] | |
1378 | ||
1379 | Implementing map-like intrusive containers is not a trivial task as | |
1380 | STL's `std::map` and `std::multimap` containers store copies of a `value_type` which is defined | |
1381 | as `std::pair<const key_type, mapped_type>`. In order to reproduce this interface in [*Boost.Intrusive] | |
1382 | it shall require that objects stored in the intrusive containers contain that `std::pair` member with | |
1383 | `pair.first` hardcoded as the key part and `pair.second` hardcoded as the `mapped_type`, which | |
1384 | is limiting and also not very useful in practice. Any intrusive associative container can be used like | |
1385 | a map using [link intrusive.advanced_lookups_insertions advanced lookup and insertions] and the user | |
1386 | can change the key type in each lookup/insertion check call. | |
1387 | ||
1388 | On the other hand, in many cases containers are indexed by a well-known key type, and the user is forced | |
1389 | to write some repetitive code using advanced lookup and insertions. [*Boost.Intrusive] | |
1390 | associative containers offer an alternative to build a useful map-like lookup interfaces | |
1391 | without forcing users to define `value_type`s containing `std::pair`-like classes. | |
1392 | The option is called [classref boost::intrusive::key_of_value]. | |
1393 | ||
1394 | If a user specifies that option when defining a `set/multiset` intrusive container, it specifies a function object | |
1395 | that will tell the container which is the type of the ['key] that `value_type` holds and how to obtain it. This | |
1396 | function object must be lightweight, `DefaultConstructible`, it shall define a `type` member that defines the type | |
1397 | of the key and a member function to obtain a const reference to the key stored inside a `value_type`. Let's | |
1398 | see an example of how a set can be configured as a map indexed by an integer stored in the `value_type`. | |
1399 | ||
1400 | [import ../example/doc_map.cpp] | |
1401 | [doc_map_code] | |
1402 | ||
1403 | [endsect] | |
1404 | ||
1405 | [section:avl_set_multiset Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree] | |
1406 | ||
1407 | Similar to red-black trees, AVL trees are balanced binary trees. | |
1408 | AVL trees are often compared with red-black trees because they support the same set of operations | |
1409 | and because both take O(log n) time for basic operations. | |
1410 | AVL trees are more rigidly balanced than Red-Black trees, leading to slower insertion and | |
1411 | removal but faster retrieval, so AVL trees perform better | |
1412 | than red-black trees for lookup-intensive applications. | |
1413 | ||
1414 | [*Boost.Intrusive] offers 3 containers based on avl trees: | |
1415 | [classref boost::intrusive::avl_set avl_set], | |
1416 | [classref boost::intrusive::avl_multiset avl_multiset] and | |
1417 | [classref boost::intrusive::avltree avltree]. The first two are similar to | |
1418 | [classref boost::intrusive::set set] or | |
1419 | [classref boost::intrusive::multiset multiset] and the latter is a generalization | |
1420 | that offers functions both to insert unique and multiple keys. | |
1421 | ||
1422 | The memory overhead of these containers with Boost.Intrusive hooks is usually 3 | |
1423 | pointers and 2 bits (due to alignment, this usually means 3 pointers plus an integer). | |
1424 | This size can be reduced to 3 pointers if pointers have 4 byte alignment | |
1425 | (which is usually true in 32 bit systems). | |
1426 | ||
1427 | An empty, non constant-time size [classref boost::intrusive::avl_set avl_set], | |
1428 | [classref boost::intrusive::avl_multiset avl_multiset] or | |
1429 | [classref boost::intrusive::avltree avltree] | |
1430 | also has a size of 3 pointers and an integer (3 pointers when optimized for size). | |
1431 | ||
1432 | [section:avl_set_multiset_hooks avl_set, avl_multiset and avltree hooks] | |
1433 | ||
1434 | [classref boost::intrusive::avl_set avl_set], | |
1435 | [classref boost::intrusive::avl_multiset avl_multiset] and | |
1436 | [classref boost::intrusive::avltree avltree] | |
1437 | share the same hooks. | |
1438 | ||
1439 | [c++] | |
1440 | ||
1441 | template <class ...Options> | |
1442 | class avl_set_base_hook; | |
1443 | ||
1444 | * [classref boost::intrusive::avl_set_base_hook avl_set_base_hook]: | |
1445 | the user class derives publicly from this class to make | |
1446 | it compatible with avl tree based containers. | |
1447 | ||
1448 | [c++] | |
1449 | ||
1450 | template <class ...Options> | |
1451 | class avl_set_member_hook; | |
1452 | ||
1453 | * [classref boost::intrusive::set_member_hook set_member_hook]: | |
1454 | the user class contains a public member of this class to make | |
1455 | it compatible with avl tree based containers. | |
1456 | ||
1457 | [classref boost::intrusive::avl_set_base_hook avl_set_base_hook] and | |
1458 | [classref boost::intrusive::avl_set_member_hook avl_set_member_hook] receive | |
1459 | the same options explained in the section | |
1460 | [link intrusive.usage How to use Boost.Intrusive] plus an option to optimize | |
1461 | the size of the node: | |
1462 | ||
1463 | * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag, | |
1464 | so you can derive from more than one base hook. | |
1465 | Default: `tag<default_tag>`. | |
1466 | ||
1467 | * [*`link_mode<link_mode_type LinkMode>`]: The linking policy. | |
1468 | Default: `link_mode<safe_link>`. | |
1469 | ||
1470 | * [*`void_pointer<class VoidPointer>`]: The pointer type to be used | |
1471 | internally in the hook and propagated to the container. | |
1472 | Default: `void_pointer<void*>`. | |
1473 | ||
1474 | * [*`optimize_size<bool Enable>`]: The hook will be optimized for size | |
1475 | instead of speed. The hook will embed the balance bits of the AVL | |
1476 | tree node in the parent pointer if pointer alignment is multiple of 4. | |
1477 | In some platforms, optimizing the size might reduce speed performance a bit | |
1478 | since masking operations will be needed to access parent pointer and balance factor attributes, | |
1479 | in other platforms this option improves performance due to improved memory locality. | |
1480 | Default: `optimize_size<false>`. | |
1481 | ||
1482 | [endsect] | |
1483 | ||
1484 | [section:set_multiset_containers avl_set, avl_multiset and avltree containers] | |
1485 | ||
1486 | [c++] | |
1487 | ||
1488 | template <class T, class ...Options> | |
1489 | class avl_set; | |
1490 | ||
1491 | template <class T, class ...Options> | |
1492 | class avl_multiset; | |
1493 | ||
1494 | template <class T, class ...Options> | |
1495 | class avltree; | |
1496 | ||
1497 | These containers receive the same options explained in the section | |
1498 | [link intrusive.usage How to use Boost.Intrusive]: | |
1499 | ||
1500 | * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] / | |
1501 | [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used | |
1502 | to configure the container. (To learn about value traits go to the section | |
1503 | [link intrusive.value_traits Containers with custom ValueTraits].) | |
1504 | ||
1505 | * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation. | |
1506 | Default: `constant_time_size<true>` | |
1507 | ||
1508 | * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size | |
1509 | of the container. Default: `size_type<std::size_t>` | |
1510 | ||
1511 | And they also can receive an additional option: | |
1512 | ||
1513 | * [*`compare<class Compare>`]: Comparison function for the objects to be inserted | |
1514 | in containers. The comparison functor must induce a strict weak ordering. | |
1515 | Default: `compare< std::less<key_type> >` | |
1516 | ||
1517 | * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will | |
1518 | define the `key_type` of the value type to be stored. This type will allow a map-like interface. See | |
1519 | [link intrusive.map_multimap Map and multimap-like interface with set and multiset] | |
1520 | for details. Default: `key_type` is equal to `value_type` (set-like interface). | |
1521 | ||
1522 | [endsect] | |
1523 | ||
1524 | [section:avl_set_multiset_example Example] | |
1525 | ||
1526 | Now let's see a small example using both hooks and | |
1527 | [classref boost::intrusive::avl_set avl_set]/ | |
1528 | [classref boost::intrusive::avl_multiset avl_multiset] | |
1529 | containers: | |
1530 | ||
1531 | [import ../example/doc_avl_set.cpp] | |
1532 | [doc_avl_set_code] | |
1533 | ||
1534 | [endsect] | |
1535 | ||
1536 | [endsect] | |
1537 | ||
1538 | [section:splay_set_multiset Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree] | |
1539 | ||
1540 | C++ associative containers are usually based on red-black tree implementations (e.g.: STL, | |
1541 | Boost.Intrusive associative containers). However, there are other interesting data | |
1542 | structures that offer some advantages (and also disadvantages). | |
1543 | ||
1544 | Splay trees are self-adjusting binary search trees used typically in caches, memory | |
1545 | allocators and other applications, because splay trees have a "caching effect": recently | |
1546 | accessed elements have better access times than elements accessed less frequently. | |
1547 | For more information on splay trees see [@http://en.wikipedia.org/wiki/Splay_tree the corresponding Wikipedia entry]. | |
1548 | ||
1549 | [*Boost.Intrusive] offers 3 containers based on splay trees: | |
1550 | [classref boost::intrusive::splay_set splay_set], | |
1551 | [classref boost::intrusive::splay_multiset splay_multiset] and | |
1552 | [classref boost::intrusive::splaytree splaytree]. The first two are similar to | |
1553 | [classref boost::intrusive::set set] or | |
1554 | [classref boost::intrusive::multiset multiset] and the latter is a generalization | |
1555 | that offers functions both to insert unique and multiple keys. | |
1556 | ||
1557 | The memory overhead of these containers with Boost.Intrusive hooks is usually 3 pointers. | |
1558 | An empty, non constant-time size splay container has also a size of 3 pointers. | |
1559 | ||
1560 | [section:splay_set_multiset_disadvantages Advantages and disadvantages of splay tree based containers] | |
1561 | ||
1562 | Splay tree based intrusive containers have logarithmic complexity in many | |
1563 | operations like searches, insertions, erasures, etc., but if some elements are | |
1564 | more frequently accessed than others, splay trees perform faster searches than equivalent | |
1565 | balanced binary trees (such as red-black trees). | |
1566 | ||
1567 | The caching effect offered by splay trees comes with a cost: the tree must be | |
1568 | rebalanced when an element is searched. To maintain const-correctness and thread-safety | |
1569 | guarantees, this caching effect is not updated when const versions of | |
1570 | search functions like `find()`, `lower_bound()`, `upper_bound()`, `equal_range()`, | |
1571 | `count()`... are called. This means that using splay-tree based associative containers as drop-in | |
1572 | replacements of [classref boost::intrusive::set set]/ | |
1573 | [classref boost::intrusive::multiset multiset], specially for const search functions, | |
1574 | might not result in desired performance improvements. | |
1575 | ||
1576 | If element searches are randomized, the tree will be continuously srebalanced | |
1577 | without taking advantage of the cache effect, so splay trees can offer worse | |
1578 | performance than other balanced trees for several search patterns. | |
1579 | ||
1580 | [*Boost.Intrusive] splay associative containers don't use their own hook types but plain Binary search tree hooks. | |
1581 | See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more | |
1582 | information about these hooks. | |
1583 | ||
1584 | [endsect] | |
1585 | ||
1586 | [section:set_multiset_containers splay_set, splay_multiset and splaytree containers] | |
1587 | ||
1588 | [c++] | |
1589 | ||
1590 | template <class T, class ...Options> | |
1591 | class splay_set; | |
1592 | ||
1593 | template <class T, class ...Options> | |
1594 | class splay_multiset; | |
1595 | ||
1596 | template <class T, class ...Options> | |
1597 | class splaytree; | |
1598 | ||
1599 | These containers receive the same options explained in the section | |
1600 | [link intrusive.usage How to use Boost.Intrusive]: | |
1601 | ||
1602 | * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] / | |
1603 | [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used | |
1604 | to configure the container. (To learn about value traits go to the section | |
1605 | [link intrusive.value_traits Containers with custom ValueTraits].) | |
1606 | ||
1607 | * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation. | |
1608 | Default: `constant_time_size<true>` | |
1609 | ||
1610 | * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size | |
1611 | of the container. Default: `size_type<std::size_t>` | |
1612 | ||
1613 | And they also can receive an additional option: | |
1614 | ||
1615 | * [*`compare<class Compare>`]: Comparison function for the objects to be inserted | |
1616 | in containers. The comparison functor must induce a strict weak ordering. | |
1617 | Default: `compare< std::less<key_type> >` | |
1618 | ||
1619 | * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will | |
1620 | define the `key_type` of the value type to be stored. This type will allow a map-like interface. See | |
1621 | [link intrusive.map_multimap Map and multimap-like interface with set and multiset] | |
1622 | for details. Default: `key_type` is equal to `value_type` (set-like interface). | |
1623 | ||
1624 | [endsect] | |
1625 | ||
1626 | [section:splay_set_multiset_example Example] | |
1627 | ||
1628 | Now let's see a small example using | |
1629 | [classref boost::intrusive::splay_set splay_set]/ | |
1630 | [classref boost::intrusive::splay_multiset splay_multiset] | |
1631 | containers: | |
1632 | ||
1633 | [import ../example/doc_splay_set.cpp] | |
1634 | [doc_splay_set_code] | |
1635 | ||
1636 | [endsect] | |
1637 | ||
1638 | [endsect] | |
1639 | ||
1640 | ||
1641 | [section:sg_set_multiset Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree] | |
1642 | ||
1643 | A scapegoat tree is a self-balancing binary search tree, that provides worst-case O(log n) | |
1644 | lookup time, and O(log n) amortized insertion and deletion time. | |
1645 | Unlike other self-balancing binary search trees that provide worst case O(log n) lookup | |
1646 | time, scapegoat trees have no additional per-node overhead compared to a regular binary | |
1647 | search tree. | |
1648 | ||
1649 | A binary search tree is said to be weight balanced if half the nodes are on the left | |
1650 | of the root, and half on the right. An a-height-balanced tree is defined with defined | |
1651 | with the following equation: | |
1652 | ||
1653 | [*['height(tree) <= log1/a(tree.size())]] | |
1654 | ||
1655 | * [*['a == 1]]: A tree forming a linked list is considered balanced. | |
1656 | * [*['a == 0.5]]: Only a perfectly balanced binary is considered balanced. | |
1657 | ||
1658 | Scapegoat trees are loosely ['a-height-balanced] so: | |
1659 | ||
1660 | [*['height(tree) <= log1/a(tree.size()) + 1]] | |
1661 | ||
1662 | Scapegoat trees support any a between 0.5 and 1. If a is higher, the tree is rebalanced | |
1663 | less often, obtaining quicker insertions but slower searches. Lower | |
1664 | a values improve search times. Scapegoat-trees implemented in [*Boost.Intrusive] offer the possibility of | |
1665 | [*changing a at run-time] taking advantage of the flexibility of scapegoat trees. | |
1666 | For more information on scapegoat trees see [@http://en.wikipedia.org/wiki/Scapegoat_tree Wikipedia entry]. | |
1667 | ||
1668 | Scapegoat trees also have downsides: | |
1669 | ||
1670 | * They need additional storage of data on the | |
1671 | root (the size of the tree, for example) to achieve logarithmic complexity operations | |
1672 | so it's not possible to offer `auto_unlink` hooks. The size of an empty scapegoat | |
1673 | tree is also considerably increased. | |
1674 | ||
1675 | * The operations needed to determine if the tree is unbalanced require floating-point | |
1676 | operations like ['log1/a]. If the system has no floating point operations (like some | |
1677 | embedded systems), scapegoat tree operations might become slow. | |
1678 | ||
1679 | [*Boost.Intrusive] offers 3 containers based on scapegoat trees: | |
1680 | [classref boost::intrusive::sg_set sg_set], | |
1681 | [classref boost::intrusive::sg_multiset sg_multiset] and | |
1682 | [classref boost::intrusive::sgtree sgtree]. The first two are similar to | |
1683 | [classref boost::intrusive::set set] or | |
1684 | [classref boost::intrusive::multiset multiset] and the latter is a generalization | |
1685 | that offers functions both to insert unique and multiple keys. | |
1686 | ||
1687 | The memory overhead of these containers with Boost.Intrusive hooks is 3 | |
1688 | pointers. | |
1689 | ||
1690 | An empty, [classref boost::intrusive::sg_set sg_set], | |
1691 | [classref boost::intrusive::sg_multiset sg_multiset] or | |
1692 | [classref boost::intrusive::sgtree sgtree] | |
1693 | has also the size of 3 pointers, two integers and two floating point values | |
1694 | (equivalent to the size of 7 pointers on most systems). | |
1695 | ||
1696 | [*Boost.Intrusive] scapegoat associative containers don't use their own hook types but plain Binary search tree hooks. | |
1697 | See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more | |
1698 | information about these hooks. | |
1699 | ||
1700 | [section:sg_set_multiset_containers sg_set, sg_multiset and sgtree containers] | |
1701 | ||
1702 | [c++] | |
1703 | ||
1704 | template <class T, class ...Options> | |
1705 | class sg_set; | |
1706 | ||
1707 | template <class T, class ...Options> | |
1708 | class sg_multiset; | |
1709 | ||
1710 | template <class T, class ...Options> | |
1711 | class sgtree; | |
1712 | ||
1713 | These containers receive the same options explained in the section | |
1714 | [link intrusive.usage How to use Boost.Intrusive]: | |
1715 | ||
1716 | * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] / | |
1717 | [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used | |
1718 | to configure the container. (To learn about value traits go to the section | |
1719 | [link intrusive.value_traits Containers with custom ValueTraits].) | |
1720 | ||
1721 | * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size | |
1722 | of the container. Default: `size_type<std::size_t>` | |
1723 | ||
1724 | And they also can receive additional options: | |
1725 | ||
1726 | * [*`compare<class Compare>`]: Comparison function for the objects to be inserted | |
1727 | in containers. The comparison functor must induce a strict weak ordering. | |
1728 | Default: `compare< std::less<key_type> >` | |
1729 | ||
1730 | * [*`floating_point<bool Enable>`]: | |
1731 | When this option is deactivated, the scapegoat tree loses the ability to change | |
1732 | the balance factor a at run-time, but the size of an empty container is reduced | |
1733 | and no floating point operations are performed, normally increasing container | |
1734 | performance. The fixed a factor that is used when this option is activated | |
1735 | is ['1/sqrt(2) ~ 0,70711]. Default: `floating_point<true>` | |
1736 | ||
1737 | * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will | |
1738 | define the `key_type` of the value type to be stored. This type will allow a map-like interface. See | |
1739 | [link intrusive.map_multimap Map and multimap-like interface with set and multiset] | |
1740 | for details. Default: `key_type` is equal to `value_type` (set-like interface). | |
1741 | ||
1742 | [endsect] | |
1743 | ||
1744 | [section:sg_set_multiset_example Example] | |
1745 | ||
1746 | Now let's see a small example using binary search tree hooks and | |
1747 | [classref boost::intrusive::sg_set sg_set]/ | |
1748 | [classref boost::intrusive::sg_multiset sg_multiset] | |
1749 | containers: | |
1750 | ||
1751 | [import ../example/doc_sg_set.cpp] | |
1752 | [doc_sg_set_code] | |
1753 | ||
1754 | [endsect] | |
1755 | ||
1756 | [endsect] | |
1757 | ||
1758 | ||
1759 | [section:treap_set_multiset Intrusive treap based associative containers: treap_set, treap_multiset and treap] | |
1760 | ||
1761 | The name ['treap] is a mixture of ['tree] and ['heap] indicating that Treaps exhibit the properties of both | |
1762 | binary search trees and heaps. A treap is a binary search tree that orders the nodes | |
1763 | by a key but also by a priority attribute. The nodes are ordered so that the keys form a binary search tree and | |
1764 | the priorities obey the max heap order property. | |
1765 | ||
1766 | * If v is a left descendant of u, then key[v] < key[u]; | |
1767 | * If v is a right descendant of u, then key[v] > key[u]; | |
1768 | * If v is a child of u, then priority[v] <= priority[u]; | |
1769 | ||
1770 | If priorities are non-random, the tree will usually be unbalanced; this worse theoretical average-case | |
1771 | behavior may be outweighed by better expected-case behavior, as the most important items will be near the root. | |
1772 | This means most important objects will be retrieved faster than less important items and for items keys with equal keys | |
1773 | most important objects will be found first. These properties are important for some applications. | |
1774 | ||
1775 | The priority comparison will be provided just like the key comparison, via a function object that will be | |
1776 | stored in the intrusive container. This means that the priority can be stored in the value to be introduced | |
1777 | in the treap or computed on flight (via hashing or similar). | |
1778 | ||
1779 | [*Boost.Intrusive] offers 3 containers based on treaps: | |
1780 | [classref boost::intrusive::treap_set treap_set], | |
1781 | [classref boost::intrusive::treap_multiset treap_multiset] and | |
1782 | [classref boost::intrusive::treap treap]. The first two are similar to | |
1783 | [classref boost::intrusive::set set] or | |
1784 | [classref boost::intrusive::multiset multiset] and the latter is a generalization | |
1785 | that offers functions both to insert unique and multiple keys. | |
1786 | ||
1787 | The memory overhead of these containers with Boost.Intrusive hooks is 3 | |
1788 | pointers. | |
1789 | ||
1790 | An empty, [classref boost::intrusive::treap_set treap_set], | |
1791 | [classref boost::intrusive::treap_multiset treap_multiset] or | |
1792 | [classref boost::intrusive::treap treap] | |
1793 | has also the size of 3 pointers and an integer (supposing empty function objects for key and priority | |
1794 | comparison and constant-time size). | |
1795 | ||
1796 | [*Boost.Intrusive] treap associative containers don't use their own hook types but plain Binary search tree hooks. | |
1797 | See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more | |
1798 | information about these hooks. | |
1799 | ||
1800 | [section:treap_set_multiset_containers treap_set, treap_multiset and treap containers] | |
1801 | ||
1802 | [c++] | |
1803 | ||
1804 | template <class T, class ...Options> | |
1805 | class treap_set; | |
1806 | ||
1807 | template <class T, class ...Options> | |
1808 | class treap_multiset; | |
1809 | ||
1810 | template <class T, class ...Options> | |
1811 | class treap; | |
1812 | ||
1813 | These containers receive the same options explained in the section | |
1814 | [link intrusive.usage How to use Boost.Intrusive]: | |
1815 | ||
1816 | * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] / | |
1817 | [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used | |
1818 | to configure the container. (To learn about value traits go to the section | |
1819 | [link intrusive.value_traits Containers with custom ValueTraits].) | |
1820 | ||
1821 | * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation. | |
1822 | Default: `constant_time_size<true>` | |
1823 | ||
1824 | * [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size | |
1825 | of the container. Default: `size_type<std::size_t>` | |
1826 | ||
1827 | And they also can receive additional options: | |
1828 | ||
1829 | * [*`compare<class Compare>`]: Comparison function for the objects to be inserted | |
1830 | in containers. The comparison functor must induce a strict weak ordering. | |
1831 | Default: `compare< std::less<key_type> >` | |
1832 | ||
1833 | * [*`priority<class PriorityCompare>`]: Priority Comparison function for the objects to be inserted | |
1834 | in containers. The comparison functor must induce a strict weak ordering. | |
1835 | Default: `priority< priority_compare<key_type> >` | |
1836 | ||
1837 | * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will | |
1838 | define the `key_type` of the value type to be stored. This type will allow a map-like interface. See | |
1839 | [link intrusive.map_multimap Map and multimap-like interface with set and multiset] | |
1840 | for details. Default: `key_type` is equal to `value_type` (set-like interface). | |
1841 | ||
1842 | The default `priority_compare<T>` object function will call an unqualified function `priority_order` | |
1843 | passing two constant `T` references as arguments and should return true if the first argument has | |
1844 | higher priority (it will be searched faster), inducing strict weak ordering. | |
1845 | The function will be found using ADL lookup so that | |
1846 | the user just needs to define a `priority_order` function in the same namespace as the class: | |
1847 | ||
1848 | [c++] | |
1849 | ||
1850 | struct MyType | |
1851 | { | |
1852 | friend bool priority_order(const MyType &a, const MyType &b) | |
1853 | {...} | |
1854 | }; | |
1855 | ||
1856 | or | |
1857 | ||
1858 | namespace mytype { | |
1859 | ||
1860 | struct MyType{ ... }; | |
1861 | ||
1862 | bool priority_order(const MyType &a, const MyType &b) | |
1863 | {...} | |
1864 | ||
1865 | } //namespace mytype { | |
1866 | ||
1867 | [endsect] | |
1868 | ||
1869 | [section:treap_set_exceptions Exception safety of treap-based intrusive containers] | |
1870 | ||
1871 | In general, intrusive containers offer strong safety guarantees, but treap containers must deal | |
1872 | with two possibly throwing functors (one for value ordering, another for priority ordering). | |
1873 | Moreover, treap erasure operations require rotations based on the priority order function and | |
1874 | this issue degrades usual `erase(const_iterator)` no-throw guarantee. However, intrusive offers | |
1875 | the strongest possible behaviour in these situations. In summary: | |
1876 | ||
1877 | * If the priority order functor does not throw, treap-based containers, offer exactly the same | |
1878 | guarantees as other tree-based containers. | |
1879 | ||
1880 | * If the priority order functor throws, treap-based containers offer strong guarantee. | |
1881 | ||
1882 | [endsect] | |
1883 | ||
1884 | [section:treap_set_multiset_example Example] | |
1885 | ||
1886 | Now let's see a small example using binary search tree hooks and | |
1887 | [classref boost::intrusive::treap_set treap_set]/ | |
1888 | [classref boost::intrusive::treap_multiset treap_multiset] | |
1889 | containers: | |
1890 | ||
1891 | [import ../example/doc_treap_set.cpp] | |
1892 | [doc_treap_set_code] | |
1893 | ||
1894 | [endsect] | |
1895 | ||
1896 | [endsect] | |
1897 | ||
1898 | [section:bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] | |
1899 | ||
1900 | Binary search tree hooks can be used with several tree-like containers that don't | |
1901 | need any additional metadata for rebalancing operations. This has many advantages | |
1902 | since binary search tree hooks can also be used to insert values in | |
1903 | plain binary search tree, splay tree, scapegoat tree, and treap containers. | |
1904 | ||
1905 | [c++] | |
1906 | ||
1907 | template <class ...Options> | |
1908 | class bs_set_base_hook; | |
1909 | ||
1910 | * [classref boost::intrusive::bs_set_base_hook bs_set_base_hook]: | |
1911 | the user class derives publicly from this class to make | |
1912 | it compatible with the mentioned tree based containers. | |
1913 | ||
1914 | [c++] | |
1915 | ||
1916 | template <class ...Options> | |
1917 | class bs_set_member_hook; | |
1918 | ||
1919 | * [classref boost::intrusive::bs_set_member_hook bs_set_member_hook]: | |
1920 | the user class contains a public member of this class to make | |
1921 | it compatible with the mentioned tree based containers. | |
1922 | ||
1923 | [classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and | |
1924 | [classref boost::intrusive::bs_set_member_hook bs_set_member_hook] receive | |
1925 | the same options explained in the section | |
1926 | [link intrusive.usage How to use Boost.Intrusive]: | |
1927 | ||
1928 | * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag, | |
1929 | so you can derive from more than one base hook. | |
1930 | Default: `tag<default_tag>`. | |
1931 | ||
1932 | * [*`link_mode<link_mode_type LinkMode>`]: The linking policy. | |
1933 | Default: `link_mode<safe_link>`. | |
1934 | ||
1935 | * [*`void_pointer<class VoidPointer>`]: The pointer type to be used | |
1936 | internally in the hook and propagated to the container. | |
1937 | Default: `void_pointer<void*>`. | |
1938 | ||
1939 | [endsect] | |
1940 | ||
1941 | [section:advanced_lookups_insertions Advanced lookup and insertion functions for associative containers] | |
1942 | ||
1943 | [section:advanced_lookups Advanced lookups] | |
1944 | ||
1945 | [*Boost.Intrusive] associative containers offer an interface similar to STL associative | |
1946 | containers. However, STL's ordered and unordered simple associative containers | |
1947 | (`std::set`, `std::multiset`, `std::unordered_set` and `std::unordered_multiset`) | |
1948 | have some inefficiencies caused by the interface in several search, insertion or erasure functions | |
1949 | (`equal_range`, `lower_bound`, `upper_bound`, `find`, `insert`, `erase`...): the user can only operate | |
1950 | with `value_type` objects or (starting from C++11), | |
1951 | [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3657.htm heterogeneous comparison lookups] | |
1952 | which are not flexible enough as `key_compare` shall support the comparison between the provided | |
1953 | key and `value_type`, which precludes the use of user-defined comparison objects that can partition the | |
1954 | search in a compatible but advanced way. | |
1955 | ||
1956 | To solve these problems, [*Boost.Intrusive] containers offers functions where a key type different | |
1957 | from `key_type` and a comparison object are provided by the user. This applies to: | |
1958 | * equal_range | |
1959 | * lower_bound | |
1960 | * upper_bound | |
1961 | * count | |
1962 | * find | |
1963 | * erase | |
1964 | ||
1965 | Requirements for such functions are: | |
1966 | ||
1967 | * For unordered container the provided comparison and hashing | |
1968 | function with the given key shall induce the same hash and equivalence as `key_compare` and `hasher`. | |
1969 | ||
1970 | * For ordered associative containers, lookup and erasure functions, the container to be searched shall | |
1971 | be partitioned in regards to the supplied comparison object and key. | |
1972 | ||
1973 | For more details, see [*Requires] clauses of such functions in the reference. | |
1974 | ||
1975 | [section:advanced_lookups_example Example] | |
1976 | ||
1977 | Imagine that the object to be searched is quite expensive to construct (called `Expensive` in the example): | |
1978 | ||
1979 | [import ../example/doc_assoc_optimized_code.cpp] | |
1980 | [doc_assoc_optimized_code_normal_find] | |
1981 | ||
1982 | If "key" c-string is quite long | |
1983 | `Expensive` has to construct a `std::string` using heap memory. Like | |
1984 | `Expensive`, many times the only member taking part in ordering issues is just | |
1985 | a small part of the class. E.g.: with `Expensive`, only the internal | |
1986 | `std::string` is needed to compare the object. | |
1987 | ||
1988 | In both containers, if we call `get_from_set/get_from_unordered_set` in a loop, we might get a performance penalty, | |
1989 | because we are forced to create a whole `Expensive` object to be able to find an | |
1990 | equivalent one. | |
1991 | ||
1992 | Sometimes the problem is not only performance-related, as | |
1993 | we [*might not have enough information to construct the object] but we might | |
1994 | [*have enough information to find the object]. In this case, a name is enough | |
1995 | to search `Expensive` objects in the container but constructing an `Expensive` | |
1996 | object might require more information that the searcher might not have. | |
1997 | ||
1998 | To solve this, we can use the functions that take any type comparable with the value and a | |
1999 | the 'compatible' comparison object (and hash, when the associative container is unordered) | |
2000 | Let's see optimized search function: | |
2001 | ||
2002 | [doc_assoc_optimized_code_optimized_find] | |
2003 | ||
2004 | [endsect] | |
2005 | ||
2006 | [endsect] | |
2007 | ||
2008 | [section:advanced_insertions Advanced insertions] | |
2009 | ||
2010 | A similar issue happens with insertions in simple ordered and unordered associative | |
2011 | containers with unique keys (`std::set` and `std::unordered_set`). In these containers, | |
2012 | if a value is already present, the value to be inserted is discarded. With expensive | |
2013 | values, if the value is already present, we can suffer efficiency problems. | |
2014 | ||
2015 | [classref boost::intrusive::set set] and [classref boost::intrusive::unordered_set unordered_set]-like | |
2016 | containers have insertion functions (`insert_check`, `insert_unique_check`,...) to check efficiently, without | |
2017 | constructing the value, if a value is present or not and if it's not present, a | |
2018 | function to insert it immediately (`insert_commit`) without any further lookup. Requirements for functions | |
2019 | that check the existence of such value are: | |
2020 | ||
2021 | * For unordered container the provided comparison and hashing | |
2022 | function with the given key shall induce the same hash and equivalence as `key_compare` and `hasher`. | |
2023 | ||
2024 | * For ordered associative containers, the provided comparison function with the given key, shall induce the same | |
2025 | strict weak order as `key_compare`. | |
2026 | ||
2027 | To sum up, `insert_check` is similar to a normal `insert` but: | |
2028 | ||
2029 | * `insert_check` can be used with arbitrary keys | |
2030 | * if the insertion is possible (there is no equivalent value) `insert_check` collects all the needed information | |
2031 | in an `insert_commit_data` structure, so that `insert_commit`: | |
2032 | * [*does not execute] further comparisons | |
2033 | * can be executed with [*constant-time complexity] | |
2034 | * has [*no-throw guarantee]. | |
2035 | ||
2036 | These functions must be used with care, | |
2037 | no other insertion or erasure must be executed between an `insert_check` and an `insert_commit` | |
2038 | pair. Otherwise, the behaviour is undefined. | |
2039 | ||
2040 | See [classref boost::intrusive::set set] | |
2041 | and [classref boost::intrusive::unordered_set unordered_set]-like containers' reference | |
2042 | for more information about `insert_check` and `insert_commit`. | |
2043 | ||
2044 | With multiple ordered and unordered associative containers | |
2045 | ([classref boost::intrusive::multiset multiset] and | |
2046 | [classref boost::intrusive::unordered_multiset unordered_multiset]) there is | |
2047 | no need for these advanced insertion functions, since insertions are always successful. | |
2048 | ||
2049 | [section:advanced_insertions_example Example] | |
2050 | ||
2051 | For example, using the same `Expensive` class, | |
2052 | this function can be inefficient: | |
2053 | ||
2054 | [doc_assoc_optimized_code_normal_insert] | |
2055 | ||
2056 | If the object is already present, we are constructing an `Expensive` that | |
2057 | will be discarded, and this is a waste of resources. Instead of that, let's use | |
2058 | `insert_check` and `insert_commit` functions: | |
2059 | ||
2060 | [doc_assoc_optimized_code_optimized_insert] | |
2061 | ||
2062 | [endsect] | |
2063 | ||
2064 | [endsect] | |
2065 | ||
2066 | [section:positional_insertions Positional insertions] | |
2067 | ||
2068 | Some ordered associative containers offer low-level functions to bypass ordering | |
2069 | checks and insert nodes directly in desired tree positions. These functions are | |
2070 | provided for performance reasons when values to be inserted in the container are | |
2071 | known to fulfill order (sets and multisets) and uniqueness (sets) invariants. A | |
2072 | typical usage of these functions is when intrusive associative containers are used | |
2073 | to build non-intrusive containers and the programmer wants to speed up assignments | |
2074 | from other associative containers: if the ordering and uniqueness properties are the same, | |
2075 | there is no need to waste time checking the position of each source value, because values | |
2076 | are already ordered: back insertions will be much more efficient. | |
2077 | ||
2078 | [*Note:] These functions [*don't check preconditions] so they must used with care. They | |
2079 | are low-level operations that [*will break container invariants if | |
2080 | ordering and uniqueness preconditions are not assured by the caller.] | |
2081 | ||
2082 | Let's see an example: | |
2083 | ||
2084 | [import ../example/doc_positional_insertion.cpp] | |
2085 | [doc_positional_insertion] | |
2086 | ||
2087 | [endsect] | |
2088 | ||
2089 | For more information about advanced lookup and insertion functions see | |
2090 | associative containers' documentation (e.g. | |
2091 | [classref boost::intrusive::set set], | |
2092 | [classref boost::intrusive::multiset multiset], | |
2093 | [classref boost::intrusive::unordered_set unordered_set] and | |
2094 | [classref boost::intrusive::unordered_multiset unordered_multiset] references). | |
2095 | ||
2096 | [endsect] | |
2097 | ||
2098 | [section:erasing_and_disposing Erasing and disposing values from Boost.Intrusive containers] | |
2099 | ||
2100 | One of the most tedious tasks when using intrusive containers is the management of the erased elements. | |
2101 | When using STL containers, the container itself unlinks and destroys the contained elements, but with | |
2102 | intrusive containers, the user must explicitly destroy the object after erasing an element from the container. | |
2103 | This makes STL-like functions erasing multiple objects unhelpful: the user can't destroy every erased element. | |
2104 | For example, let's take the function `remove_if` from [classref boost::intrusive::list list]: | |
2105 | ||
2106 | [c++] | |
2107 | ||
2108 | template<class Pred> | |
2109 | void remove_if(Pred pred); | |
2110 | ||
2111 | How can the user destroy the elements (say, using `operator delete`) that will be erased according | |
2112 | to the predicate? [*Boost.Intrusive] containers offer additional functions that take a function | |
2113 | object that will be called after the element has been erased from the container. For example, | |
2114 | [classref boost::intrusive::list list] offers: | |
2115 | ||
2116 | [c++] | |
2117 | ||
2118 | template<class Pred, class Disposer> | |
2119 | void remove_and_dispose_if(Pred pred, Disposer disposer) | |
2120 | ||
2121 | With this function the user can efficiently remove and destroy elements if the disposer | |
2122 | function destroys an object: `remove_and_dispose_if` | |
2123 | will call the "disposer" function object for every removed element. [classref boost::intrusive::list list] offers | |
2124 | more functions taking a disposer function object as argument, like `erase_and_dispose`, `clear_and_dispose`, | |
2125 | `remove_and_dispose`, etc. | |
2126 | ||
2127 | Note that the disposing function does not need to just destroy the object. It can | |
2128 | implement any other operation like inserting the remove object in another container. | |
2129 | Let's see a small example: | |
2130 | ||
2131 | [import ../example/doc_erasing_and_disposing.cpp] | |
2132 | [doc_erasing_and_disposing] | |
2133 | ||
2134 | All [*Boost.Intrusive] containers offer these "erase + dispose" additional members for all functions | |
2135 | that erase an element from the container. | |
2136 | ||
2137 | ||
2138 | ||
2139 | [endsect] | |
2140 | ||
2141 | [section:clone_from Cloning Boost.Intrusive containers] | |
2142 | ||
2143 | As previously mentioned, [*Boost.Intrusive] containers are [*non-copyable and non-assignable], because | |
2144 | intrusive containers don't allocate memory at all. To implement a copy-constructor or assignment operator, | |
2145 | the user must clone one by one all the elements of the container and insert them in another intrusive container. | |
2146 | However, cloning by hand is usually more inefficient than a member cloning function and a specialized cloning | |
2147 | function can offer more guarantees than the manual cloning (better exception safety guarantees, for example). | |
2148 | ||
2149 | To ease the implementation of copy constructors and assignment operators of classes containing [*Boost.Intrusive] | |
2150 | containers, all [*Boost.Intrusive] containers offer a special cloning function called `clone_from`. | |
2151 | ||
2152 | Apart from the container to be cloned, `clone_from` takes two function objects as arguments. For example, consider the | |
2153 | `clone_from` member function of [classref boost::intrusive::list list]: | |
2154 | ||
2155 | [c++] | |
2156 | ||
2157 | template <class Cloner, class Disposer> | |
2158 | void clone_from(const list &src, Cloner cloner, Disposer disposer); | |
2159 | ||
2160 | This function will make `*this` a clone of `src`. Let's explain the arguments: | |
2161 | ||
2162 | * The first parameter is the list to be cloned. | |
2163 | * The second parameter is a function object that will clone `value_type` objects and | |
2164 | return a pointer to the clone. It must implement the following function: | |
2165 | `pointer operator()(const value_type &)`. | |
2166 | * The second parameter is a function object that will dispose `value_type` objects. It's used first | |
2167 | to empty the container before cloning and to dispose the elements if an exception is thrown. | |
2168 | ||
2169 | The cloning function works as follows: | |
2170 | ||
2171 | * First it clears and disposes all the elements from *this using the disposer function object. | |
2172 | * After that it starts cloning all the elements of the source container using the cloner function object. | |
2173 | * If any operation in the cloning function (for example, the cloner function object) throws, | |
2174 | all the constructed elements are disposed using the disposer function object. | |
2175 | ||
2176 | ||
2177 | Here is an example of `clone_from`: | |
2178 | ||
2179 | [import ../example/doc_clone_from.cpp] | |
2180 | [doc_clone_from] | |
2181 | ||
2182 | [endsect] | |
2183 | ||
2184 | [section:function_hooks Using function hooks] | |
2185 | ||
2186 | A programmer might find that base or member hooks are not flexible enough in some situations. | |
2187 | In some applications it would be optimal to put a hook deep inside a member of a class or just outside the class. | |
2188 | [*Boost.Intrusive] has an easy option to allow such cases: [classref boost::intrusive::function_hook function_hook]. | |
2189 | ||
2190 | This option is similar to [classref boost::intrusive::member_hook member_hook] or | |
2191 | [classref boost::intrusive::base_hook base_hook], but the programmer can specify a function | |
2192 | object that tells the container how to obtain a hook from a value and vice versa. | |
2193 | The programmer just needs to define the following function object: | |
2194 | ||
2195 | [c++] | |
2196 | ||
2197 | //This functor converts between value_type and a hook_type | |
2198 | struct Functor | |
2199 | { | |
2200 | //Required types | |
2201 | typedef /*impl-defined*/ hook_type; | |
2202 | typedef /*impl-defined*/ hook_ptr; | |
2203 | typedef /*impl-defined*/ const_hook_ptr; | |
2204 | typedef /*impl-defined*/ value_type; | |
2205 | typedef /*impl-defined*/ pointer; | |
2206 | typedef /*impl-defined*/ const_pointer; | |
2207 | //Required static functions | |
2208 | static hook_ptr to_hook_ptr (value_type &value); | |
2209 | static const_hook_ptr to_hook_ptr(const value_type &value); | |
2210 | static pointer to_value_ptr(hook_ptr n); | |
2211 | static const_pointer to_value_ptr(const_hook_ptr n); | |
2212 | }; | |
2213 | ||
2214 | Converting from values to hooks is generally easy, since most hooks are | |
2215 | in practice members or base classes of class data members. The inverse operation | |
2216 | is a bit more complicated, but [*Boost.Intrusive] offers a bit of help with the function | |
2217 | [funcref boost::intrusive::get_parent_from_member get_parent_from_member], | |
2218 | which allows easy conversions from the address of a data member to the address of | |
2219 | the parent holding that member. Let's see a little example of | |
2220 | [classref boost::intrusive::function_hook function_hook]: | |
2221 | ||
2222 | [import ../example/doc_function_hooks.cpp] | |
2223 | [doc_function_hooks] | |
2224 | ||
2225 | [endsect] | |
2226 | ||
2227 | ||
2228 | [section:recursive Recursive Boost.Intrusive containers] | |
2229 | ||
2230 | [*Boost.Intrusive] containers can be used to define recursive structures very easily, | |
2231 | allowing complex data structures with very low overhead. Let's see an example: | |
2232 | ||
2233 | [import ../example/doc_recursive.cpp] | |
2234 | [doc_recursive] | |
2235 | ||
2236 | Recursive data structures using [*Boost.Intrusive] containers must avoid using hook deduction to avoid early type | |
2237 | instantiation: | |
2238 | ||
2239 | [c++] | |
2240 | ||
2241 | //This leads to compilation error (Recursive is instantiated by | |
2242 | //'list' to deduce hook properties (pointer type, tag, safe-mode...) | |
2243 | class Recursive | |
2244 | { //... | |
2245 | ||
2246 | list< Recursive > l; | |
2247 | //... | |
2248 | }; | |
2249 | ||
2250 | //Ok, programmer must specify the hook type to avoid early Recursive instantiation | |
2251 | class Recursive | |
2252 | { //... | |
2253 | list< Recursive, base_hook<BaseHook> > l; | |
2254 | //... | |
2255 | }; | |
2256 | ||
2257 | ||
2258 | Member hooks are not suitable for recursive structures: | |
2259 | ||
2260 | [c++] | |
2261 | ||
2262 | class Recursive | |
2263 | { | |
2264 | private: | |
2265 | Recursive(const Recursive&); | |
2266 | Recursive & operator=(const Recursive&); | |
2267 | ||
2268 | public: | |
2269 | list_member_hook<> memhook; | |
2270 | list< Recursive, member_hook<Recursive, list_member_hook<>, &Recursive::memhook> > children; | |
2271 | }; | |
2272 | ||
2273 | Specifying `&Recursive::memhook` (that is, the offset between memhook and Recursive) provokes an early | |
2274 | instantiation of `Recursive`. To define recursive structures using member hooks, a programmer should use | |
2275 | [classref ::boost::interprocess::function_hook function_hook]: | |
2276 | ||
2277 | [import ../example/doc_recursive_member.cpp] | |
2278 | [doc_recursive_member] | |
2279 | ||
2280 | [endsect] | |
2281 | ||
2282 | ||
2283 | [section:using_smart_pointers Using smart pointers with Boost.Intrusive containers] | |
2284 | ||
2285 | [*Boost.Intrusive] hooks can be configured to use other pointers than raw pointers. | |
2286 | When a [*Boost.Intrusive] hook is configured with a smart pointer as an argument, | |
2287 | this pointer configuration is passed to the containers. For example, if the following | |
2288 | hook is configured with a smart pointer (for example, an offset pointer from | |
2289 | [*Boost.Interprocess]): | |
2290 | ||
2291 | [import ../example/doc_offset_ptr.cpp] | |
2292 | [doc_offset_ptr_0] | |
2293 | ||
2294 | Any intrusive list constructed using this hook will be ready for shared memory, | |
2295 | because the intrusive list will also use offset pointers internally. For example, | |
2296 | we can create an intrusive list in shared memory combining [*Boost.Interprocess] | |
2297 | and [*Boost.Intrusive]: | |
2298 | ||
2299 | [doc_offset_ptr_1] | |
2300 | ||
2301 | [section:smart_pointers_requirements Requirements for smart pointers compatible with Boost.Intrusive] | |
2302 | ||
2303 | Not every smart pointer is compatible with [*Boost.Intrusive]: | |
2304 | ||
2305 | * It must be compatible with C++11 [@http://en.cppreference.com/w/cpp/memory/pointer_traits `std::pointer_traits`] | |
2306 | requirements. [*Boost.Intrusive] uses its own [classref boost::intrusive::pointer_traits pointer_traits] | |
2307 | class to implement those features in both C++11 and C++03 compilers. | |
2308 | * It must have the same ownership semantics as a raw pointer. This means that | |
2309 | resource management smart pointers (like `boost::shared_ptr`) can't be used. | |
2310 | ||
2311 | The conversion from the smart pointer to a raw pointer will be implemented as a recursive call to | |
2312 | `operator->()` until the function returns a raw pointer. | |
2313 | ||
2314 | [endsect] | |
2315 | ||
2316 | [endsect] | |
2317 | ||
2318 | [section:obtaining_iterators_from_values Obtaining iterators from values] | |
2319 | ||
2320 | [*Boost.Intrusive] offers another useful feature that's not present in STL | |
2321 | containers: it's possible to obtain an iterator to a value from the value itself. | |
2322 | This feature is implemented in [*Boost.Intrusive] containers by a | |
2323 | function called `iterator_to`: | |
2324 | ||
2325 | [c++] | |
2326 | ||
2327 | iterator iterator_to(reference value); | |
2328 | const_iterator iterator_to(const_reference value); | |
2329 | ||
2330 | For [*Boost.Intrusive] containers that have local iterators, like unordered | |
2331 | associative containers, we can also obtain local iterators: | |
2332 | ||
2333 | [c++] | |
2334 | ||
2335 | local_iterator local_iterator_to(reference value); | |
2336 | const_local_iterator local_iterator_to(const_reference value) const; | |
2337 | ||
2338 | For most [*Boost.Intrusive] containers | |
2339 | ([classref boost::intrusive::list list], | |
2340 | [classref boost::intrusive::slist slist], | |
2341 | [classref boost::intrusive::set set], | |
2342 | [classref boost::intrusive::multiset multiset]) we have an alternative | |
2343 | static `s_iterator_to` function. | |
2344 | ||
2345 | For unordered associative containers | |
2346 | ([classref boost::intrusive::unordered_set unordered_set], | |
2347 | [classref boost::intrusive::multiset multiset]), | |
2348 | `iterator_to` has no static alternative function. | |
2349 | On the other hand, `local_iterator_to` functions | |
2350 | have their `s_local_iterator_to` static alternatives. | |
2351 | ||
2352 | Alternative static functions are available under certain circumstances | |
2353 | explained in the [link intrusive.value_traits.stateful_value_traits Stateful value traits] section; | |
2354 | if the programmer uses hooks provided by [*Boost.Intrusive], those functions | |
2355 | will be available. | |
2356 | ||
2357 | Let's see a small function that shows the use of `iterator_to` and | |
2358 | `local_iterator_to`: | |
2359 | ||
2360 | [import ../example/doc_iterator_from_value.cpp] | |
2361 | [doc_iterator_from_value] | |
2362 | ||
2363 | [endsect] | |
2364 | ||
2365 | [section:any_hooks Any Hooks: A single hook for any Intrusive container] | |
2366 | ||
2367 | Sometimes, a class programmer wants to place a class in several intrusive | |
2368 | containers but no at the same time. In this case, the programmer might | |
2369 | decide to insert two hooks in the same class. | |
2370 | ||
2371 | [c++] | |
2372 | ||
2373 | class MyClass | |
2374 | : public list_base_hook<>, public slist_base_hook<> //... | |
2375 | {}; | |
2376 | ||
2377 | However, there is a more size-efficient alternative in [*Boost.Intrusive]: "any" hooks | |
2378 | ([classref boost::intrusive::any_base_hook any_base_hook] and | |
2379 | [classref boost::intrusive::any_member_hook any_member_hook]). | |
2380 | These hooks can be used to store a type in several containers | |
2381 | offered by [*Boost.Intrusive] minimizing the size of the class. | |
2382 | ||
2383 | These hooks support these options: | |
2384 | ||
2385 | * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag, | |
2386 | so you can derive from more than one slist hook. | |
2387 | Default: `tag<default_tag>`. | |
2388 | ||
2389 | * [*`link_mode<link_mode_type LinkMode>`]: The linking policy. | |
2390 | `link_mode<auto_unlink>` is [*not] supported and `link_mode<safe_mode>` | |
2391 | might offer weaker error detection in any hooks than in other hooks. | |
2392 | Default: `link_mode<safe_link>`. | |
2393 | ||
2394 | * [*`void_pointer<class VoidPointer>`]: The pointer type to be used | |
2395 | internally in the hook and propagated to the container. | |
2396 | Default: `void_pointer<void*>`. | |
2397 | ||
2398 | `auto_unlink` can't be supported because the hook does not know in which type of | |
2399 | container might be currently inserted. Additionally, these hooks don't support `unlink()` and | |
2400 | `swap_nodes()` operations for the same reason. | |
2401 | ||
2402 | Here is an example that creates a class with two any hooks, and uses one to insert the | |
2403 | class in a [classref slist] and the other one in a [classref list]. | |
2404 | ||
2405 | [import ../example/doc_any_hook.cpp] | |
2406 | [doc_any_hook] | |
2407 | ||
2408 | [endsect] | |
2409 | ||
2410 | [section:concepts Concepts explained] | |
2411 | ||
2412 | This section will expand the explanation of previously presented basic concepts | |
2413 | before explaining the customization options of [*Boost.Intrusive]. | |
2414 | ||
2415 | * [*Node Algorithms]: A set of static functions that implement basic operations | |
2416 | on a group of nodes: initialize a node, link_mode_type a node to a group of nodes, | |
2417 | unlink a node from another group of nodes, etc. For example, a circular | |
2418 | singly linked list is a group of nodes, where each node has a pointer to the | |
2419 | next node. [*Node Algorithms] just require a [*NodeTraits] | |
2420 | template parameter and they can work with any [*NodeTraits] class that fulfills | |
2421 | the needed interface. As an example, here is a class that implements operations | |
2422 | to manage a group of nodes forming a circular singly linked list: | |
2423 | ||
2424 | [c++] | |
2425 | ||
2426 | template<class NodeTraits> | |
2427 | struct my_slist_algorithms | |
2428 | { | |
2429 | typedef typename NodeTraits::node_ptr node_ptr; | |
2430 | typedef typename NodeTraits::const_node_ptr const_node_ptr; | |
2431 | ||
2432 | //Get the previous node of "this_node" | |
2433 | static node_ptr get_prev_node(node_ptr this_node) | |
2434 | { | |
2435 | node_ptr p = this_node; | |
2436 | while (this_node != NodeTraits::get_next(p)) | |
2437 | p = NodeTraits::get_next(p); | |
2438 | return p; | |
2439 | } | |
2440 | ||
2441 | // number of elements in the group of nodes containing "this_node" | |
2442 | static std::size_t count(const_node_ptr this_node) | |
2443 | { | |
2444 | std::size_t result = 0; | |
2445 | const_node_ptr p = this_node; | |
2446 | do{ | |
2447 | p = NodeTraits::get_next(p); | |
2448 | ++result; | |
2449 | } while (p != this_node); | |
2450 | return result; | |
2451 | } | |
2452 | ||
2453 | // More operations | |
2454 | // ... | |
2455 | }; | |
2456 | ||
2457 | * [*Node Traits]: A class that encapsulates the basic information and | |
2458 | operations on a node within a group of nodes: | |
2459 | the type of the node, a function to obtain the pointer to the next node, etc. | |
2460 | [*Node Traits] specify the configuration information [*Node Algorithms] | |
2461 | need. Each type of [*Node Algorithm] expects an interface that compatible | |
2462 | [*Node Traits] classes must implement. | |
2463 | As an example, this is the definition of a [*Node Traits] class that | |
2464 | is compatible with the previously presented `my_slist_algorithms`: | |
2465 | ||
2466 | [c++] | |
2467 | ||
2468 | struct my_slist_node_traits | |
2469 | { | |
2470 | //The type of the node | |
2471 | struct node | |
2472 | { | |
2473 | node *next_; | |
2474 | }; | |
2475 | ||
2476 | typedef node * node_ptr; | |
2477 | typedef const node * const_node_ptr; | |
2478 | ||
2479 | //A function to obtain a pointer to the next node | |
2480 | static node_ptr get_next(const_node_ptr n) | |
2481 | { return n->next_; } | |
2482 | ||
2483 | //A function to set the pointer to the next node | |
2484 | static void set_next(node_ptr n, node_ptr next) | |
2485 | { n->next_ = next; } | |
2486 | }; | |
2487 | ||
2488 | ||
2489 | * [*Hook]: A class that the user must add as a base class or as a member to his own | |
2490 | class to make that class insertable in an intrusive container. Usually the hook | |
2491 | contains a node object that will be used to form the group of nodes: | |
2492 | For example, the following class is a [*Hook] that the user can add as a base class, | |
2493 | to make the user class compatible with a singly linked list container: | |
2494 | ||
2495 | [c++] | |
2496 | ||
2497 | class my_slist_base_hook | |
2498 | //This hook contains a node, that will be used | |
2499 | //to link the user object in the group of nodes | |
2500 | : private my_slist_node_traits::node | |
2501 | { | |
2502 | typedef my_slist_node_traits::node_ptr node_ptr; | |
2503 | typedef my_slist_node_traits::const_node_ptr const_node_ptr; | |
2504 | ||
2505 | //Converts the generic node to the hook | |
2506 | static my_slist_base_hook *to_hook_ptr(node_ptr p) | |
2507 | { return static_cast<my_slist_base_hook*>(p); } | |
2508 | ||
2509 | //Returns the generic node stored by this hook | |
2510 | node_ptr to_node_ptr() | |
2511 | { return static_cast<node *const>(this); } | |
2512 | ||
2513 | // More operations | |
2514 | // ... | |
2515 | }; | |
2516 | ||
2517 | //To make MyClass compatible with an intrusive singly linked list | |
2518 | //derive our class from the hook. | |
2519 | class MyClass | |
2520 | : public my_slist_base_hook | |
2521 | { | |
2522 | void set(int value); | |
2523 | int get() const; | |
2524 | ||
2525 | private: | |
2526 | int value_; | |
2527 | }; | |
2528 | ||
2529 | * [*Intrusive Container]: A container that offers a STL-like interface to store | |
2530 | user objects. An intrusive container can be templatized to store different | |
2531 | value types that use different hooks. An intrusive container is also more elaborate | |
2532 | than a group of nodes: it can store the number of elements to achieve constant-time | |
2533 | size information, it can offer debugging facilities, etc. | |
2534 | For example, an [classref boost::intrusive::slist slist] container | |
2535 | (intrusive singly linked list) should | |
2536 | be able to hold `MyClass` objects that might have decided to store the hook | |
2537 | as a base class or as a member. Internally, the container will use [*Node Algorithms] | |
2538 | to implement its operations, and an intrusive container is configured using | |
2539 | a template parameter called [*ValueTraits]. [*ValueTraits] will contain | |
2540 | the information to convert user classes in nodes compatible with [*Node Algorithms]. | |
2541 | For example, this a possible [classref boost::intrusive::slist slist] implementation: | |
2542 | ||
2543 | [c++] | |
2544 | ||
2545 | template<class ValueTraits, ...> | |
2546 | class slist | |
2547 | { | |
2548 | public: | |
2549 | typedef typename ValueTraits::value_type value_type; | |
2550 | ||
2551 | //More typedefs and functions | |
2552 | // ... | |
2553 | ||
2554 | //Insert the value as the first element of the list | |
2555 | void push_front (reference value) | |
2556 | { | |
2557 | node_ptr to_insert(ValueTraits::to_node_ptr(value)); | |
2558 | circular_list_algorithms::link_after(to_insert, get_root_node()); | |
2559 | } | |
2560 | ||
2561 | // More operations | |
2562 | // ... | |
2563 | }; | |
2564 | ||
2565 | * [*Semi-Intrusive Container]: A semi-intrusive container is similar to an | |
2566 | intrusive container, but apart from the values to be inserted in the container, | |
2567 | it needs additional memory (for example, auxiliary arrays or indexes). | |
2568 | ||
2569 | * [*Value Traits]: As we can see, to make our classes intrusive-friendly we add | |
2570 | a simple hook as a member or base class. The hook contains a generic node | |
2571 | that will be inserted in a group of nodes. [*Node Algorithms] just work | |
2572 | with nodes and don't know anything about user classes. On the other | |
2573 | hand, an intrusive container needs to know how to obtain a node from a user class, | |
2574 | and also the inverse operation. | |
2575 | So we can define [*ValueTraits] as the glue between user classes and nodes | |
2576 | required by [*Node Algorithms]. | |
2577 | Let's see a possible implementation of a value traits class that glues MyClass | |
2578 | and the node stored in the hook: | |
2579 | ||
2580 | [c++] | |
2581 | ||
2582 | struct my_slist_derivation_value_traits | |
2583 | { | |
2584 | public: | |
2585 | typedef slist_node_traits node_traits; | |
2586 | typedef MyClass value_type; | |
2587 | typedef node_traits::node_ptr node_ptr; | |
2588 | typedef value_type* pointer; | |
2589 | //... | |
2590 | ||
2591 | //Converts user's value to a generic node | |
2592 | static node_ptr to_node_ptr(reference value) | |
2593 | { return static_cast<slist_base_hook &>(value).to_node_ptr(); } | |
2594 | ||
2595 | //Converts a generic node into user's value | |
2596 | static value_type *to_value_ptr(node_traits::node *n) | |
2597 | { static_cast<value_type*>(slist_base_hook::to_hook_ptr(n)); } | |
2598 | ||
2599 | // More operations | |
2600 | // ... | |
2601 | }; | |
2602 | ||
2603 | [endsect] | |
2604 | ||
2605 | [section:node_algorithms Node algorithms with custom NodeTraits] | |
2606 | ||
2607 | As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive] | |
2608 | containers are implemented using node algorithms that work on generic nodes. | |
2609 | ||
2610 | Sometimes, the use of intrusive containers is expensive for some environments | |
2611 | and the programmer might want to avoid all the template instantiations | |
2612 | related to [*Boost.Intrusive] containers. However, the user can still benefit | |
2613 | from [*Boost.Intrusive] using the node algorithms, because some of those algorithms, | |
2614 | like red-black tree algorithms, are not trivial to write. | |
2615 | ||
2616 | All node algorithm classes are | |
2617 | templatized by a `NodeTraits` class. This class encapsulates the needed internal | |
2618 | type declarations and operations to make a node compatible with node algorithms. | |
2619 | Each type of node algorithms has its own requirements: | |
2620 | ||
2621 | [section:circular_slist_algorithms Intrusive singly linked list algorithms] | |
2622 | ||
2623 | These algorithms are static | |
2624 | members of the [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms] class: | |
2625 | ||
2626 | [c++] | |
2627 | ||
2628 | template<class NodeTraits> | |
2629 | struct circular_slist_algorithms; | |
2630 | ||
2631 | An empty list is formed by a node whose pointer to the next node points | |
2632 | to itself. [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms] | |
2633 | is configured with a NodeTraits class, which encapsulates | |
2634 | the information about the node to be manipulated. NodeTraits must support the | |
2635 | following interface: | |
2636 | ||
2637 | [*Typedefs]: | |
2638 | ||
2639 | * `node`: The type of the node that forms the circular list | |
2640 | ||
2641 | * `node_ptr`: The type of a pointer to a node (usually node*) | |
2642 | ||
2643 | * `const_node_ptr`: The type of a pointer to a const node (usually const node*) | |
2644 | ||
2645 | [*Static functions]: | |
2646 | ||
2647 | * `static node_ptr get_next(const_node_ptr n);`: | |
2648 | Returns a pointer to the next node stored in "n". | |
2649 | ||
2650 | * `static void set_next(node_ptr n, node_ptr next);`: | |
2651 | Sets the pointer to the next node stored in "n" to "next". | |
2652 | ||
2653 | Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms | |
2654 | with our nodes: | |
2655 | ||
2656 | [import ../example/doc_slist_algorithms.cpp] | |
2657 | [doc_slist_algorithms_code] | |
2658 | ||
2659 | For a complete list of functions see | |
2660 | [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms reference]. | |
2661 | ||
2662 | [endsect] | |
2663 | ||
2664 | [section:circular_list_algorithms Intrusive doubly linked list algorithms] | |
2665 | ||
2666 | These algorithms are static | |
2667 | members of the [classref boost::intrusive::circular_list_algorithms circular_list_algorithms] class: | |
2668 | ||
2669 | [c++] | |
2670 | ||
2671 | template<class NodeTraits> | |
2672 | struct circular_list_algorithms; | |
2673 | ||
2674 | An empty list is formed by a node whose pointer to the next node points | |
2675 | to itself. [classref boost::intrusive::circular_list_algorithms circular_list_algorithms] | |
2676 | is configured with a NodeTraits class, which encapsulates | |
2677 | the information about the node to be manipulated. NodeTraits must support the | |
2678 | following interface: | |
2679 | ||
2680 | [*Typedefs]: | |
2681 | ||
2682 | * `node`: The type of the node that forms the circular list | |
2683 | ||
2684 | * `node_ptr`: The type of a pointer to a node (usually node*) | |
2685 | ||
2686 | * `const_node_ptr`: The type of a pointer to a const node (usually const node*) | |
2687 | ||
2688 | [*Static functions]: | |
2689 | ||
2690 | * `static node_ptr get_next(const_node_ptr n);`: | |
2691 | Returns a pointer to the next node stored in "n". | |
2692 | ||
2693 | * `static void set_next(node_ptr n, node_ptr next);`: | |
2694 | Sets the pointer to the next node stored in "n" to "next". | |
2695 | ||
2696 | * `static node_ptr get_previous(const_node_ptr n);`: | |
2697 | Returns a pointer to the previous node stored in "n". | |
2698 | ||
2699 | * `static void set_previous(node_ptr n, node_ptr prev);`: | |
2700 | Sets the pointer to the previous node stored in "n" to "prev". | |
2701 | ||
2702 | Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms | |
2703 | with our nodes: | |
2704 | ||
2705 | [import ../example/doc_list_algorithms.cpp] | |
2706 | [doc_list_algorithms_code] | |
2707 | ||
2708 | For a complete list of functions see | |
2709 | [classref boost::intrusive::circular_list_algorithms circular_list_algorithms reference]. | |
2710 | ||
2711 | [endsect] | |
2712 | ||
2713 | [section:rbtree_algorithms Intrusive red-black tree algorithms] | |
2714 | ||
2715 | These algorithms are static | |
2716 | members of the [classref boost::intrusive::rbtree_algorithms rbtree_algorithms] class: | |
2717 | ||
2718 | [c++] | |
2719 | ||
2720 | template<class NodeTraits> | |
2721 | struct rbtree_algorithms; | |
2722 | ||
2723 | ||
2724 | An empty tree is formed by a node whose pointer to the parent node is null, | |
2725 | the left and right node pointers point to itself, and whose color is red. | |
2726 | [classref boost::intrusive::rbtree_algorithms rbtree_algorithms] | |
2727 | is configured with a NodeTraits class, which encapsulates | |
2728 | the information about the node to be manipulated. NodeTraits must support the | |
2729 | following interface: | |
2730 | ||
2731 | [*Typedefs]: | |
2732 | ||
2733 | * `node`: The type of the node that forms the circular rbtree | |
2734 | ||
2735 | * `node_ptr`: The type of a pointer to a node (usually node*) | |
2736 | ||
2737 | * `const_node_ptr`: The type of a pointer to a const node (usually const node*) | |
2738 | ||
2739 | * `color`: The type that can store the color of a node | |
2740 | ||
2741 | [*Static functions]: | |
2742 | ||
2743 | * `static node_ptr get_parent(const_node_ptr n);`: | |
2744 | Returns a pointer to the parent node stored in "n". | |
2745 | ||
2746 | * `static void set_parent(node_ptr n, node_ptr p);`: | |
2747 | Sets the pointer to the parent node stored in "n" to "p". | |
2748 | ||
2749 | * `static node_ptr get_left(const_node_ptr n);`: | |
2750 | Returns a pointer to the left node stored in "n". | |
2751 | ||
2752 | * `static void set_left(node_ptr n, node_ptr l);`: | |
2753 | Sets the pointer to the left node stored in "n" to "l". | |
2754 | ||
2755 | * `static node_ptr get_right(const_node_ptr n);`: | |
2756 | Returns a pointer to the right node stored in "n". | |
2757 | ||
2758 | * `static void set_right(node_ptr n, node_ptr r);`: | |
2759 | Sets the pointer to the right node stored in "n" to "r". | |
2760 | ||
2761 | * `static color get_color(const_node_ptr n);`: | |
2762 | Returns the color stored in "n". | |
2763 | ||
2764 | * `static void set_color(node_ptr n, color c);`: | |
2765 | Sets the color stored in "n" to "c". | |
2766 | ||
2767 | * `static color black();`: | |
2768 | Returns a value representing the black color. | |
2769 | ||
2770 | * `static color red();`: | |
2771 | Returns a value representing the red color. | |
2772 | ||
2773 | Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms | |
2774 | with our nodes: | |
2775 | ||
2776 | [import ../example/doc_rbtree_algorithms.cpp] | |
2777 | [doc_rbtree_algorithms_code] | |
2778 | ||
2779 | For a complete list of functions see | |
2780 | [classref boost::intrusive::rbtree_algorithms rbtree_algorithms reference]. | |
2781 | ||
2782 | [endsect] | |
2783 | ||
2784 | [section:splaytree_algorithms Intrusive splay tree algorithms] | |
2785 | ||
2786 | These algorithms are static | |
2787 | members of the [classref boost::intrusive::splaytree_algorithms splaytree_algorithms] class: | |
2788 | ||
2789 | [c++] | |
2790 | ||
2791 | template<class NodeTraits> | |
2792 | struct splaytree_algorithms; | |
2793 | ||
2794 | ||
2795 | An empty tree is formed by a node whose pointer to the parent node is null, | |
2796 | and whose left and right nodes pointers point to itself. | |
2797 | [classref boost::intrusive::splaytree_algorithms splaytree_algorithms] | |
2798 | is configured with a NodeTraits class, which encapsulates | |
2799 | the information about the node to be manipulated. NodeTraits must support the | |
2800 | following interface: | |
2801 | ||
2802 | [*Typedefs]: | |
2803 | ||
2804 | * `node`: The type of the node that forms the circular splaytree | |
2805 | ||
2806 | * `node_ptr`: The type of a pointer to a node (usually node*) | |
2807 | ||
2808 | * `const_node_ptr`: The type of a pointer to a const node (usually const node*) | |
2809 | ||
2810 | [*Static functions]: | |
2811 | ||
2812 | * `static node_ptr get_parent(const_node_ptr n);`: | |
2813 | Returns a pointer to the parent node stored in "n". | |
2814 | ||
2815 | * `static void set_parent(node_ptr n, node_ptr p);`: | |
2816 | Sets the pointer to the parent node stored in "n" to "p". | |
2817 | ||
2818 | * `static node_ptr get_left(const_node_ptr n);`: | |
2819 | Returns a pointer to the left node stored in "n". | |
2820 | ||
2821 | * `static void set_left(node_ptr n, node_ptr l);`: | |
2822 | Sets the pointer to the left node stored in "n" to "l". | |
2823 | ||
2824 | * `static node_ptr get_right(const_node_ptr n);`: | |
2825 | Returns a pointer to the right node stored in "n". | |
2826 | ||
2827 | * `static void set_right(node_ptr n, node_ptr r);`: | |
2828 | Sets the pointer to the right node stored in "n" to "r". | |
2829 | ||
2830 | Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms | |
2831 | with our nodes: | |
2832 | ||
2833 | [import ../example/doc_splaytree_algorithms.cpp] | |
2834 | [doc_splaytree_algorithms_code] | |
2835 | ||
2836 | For a complete list of functions see | |
2837 | [classref boost::intrusive::splaytree_algorithms splaytree_algorithms reference]. | |
2838 | ||
2839 | [endsect] | |
2840 | ||
2841 | [section:avltree_algorithms Intrusive avl tree algorithms] | |
2842 | ||
2843 | [classref boost::intrusive::avltree_algorithms avltree_algorithms] have the same | |
2844 | interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms]. | |
2845 | ||
2846 | [c++] | |
2847 | ||
2848 | template<class NodeTraits> | |
2849 | struct avltree_algorithms; | |
2850 | ||
2851 | [classref boost::intrusive::avltree_algorithms avltree_algorithms] | |
2852 | is configured with a NodeTraits class, which encapsulates | |
2853 | the information about the node to be manipulated. NodeTraits must support the | |
2854 | following interface: | |
2855 | ||
2856 | [*Typedefs]: | |
2857 | ||
2858 | * `node`: The type of the node that forms the circular avltree | |
2859 | ||
2860 | * `node_ptr`: The type of a pointer to a node (usually node*) | |
2861 | ||
2862 | * `const_node_ptr`: The type of a pointer to a const node (usually const node*) | |
2863 | ||
2864 | * `balance`: A type that can represent 3 balance types (usually an integer) | |
2865 | ||
2866 | [*Static functions]: | |
2867 | ||
2868 | * `static node_ptr get_parent(const_node_ptr n);`: | |
2869 | Returns a pointer to the parent node stored in "n". | |
2870 | ||
2871 | * `static void set_parent(node_ptr n, node_ptr p);`: | |
2872 | Sets the pointer to the parent node stored in "n" to "p". | |
2873 | ||
2874 | * `static node_ptr get_left(const_node_ptr n);`: | |
2875 | Returns a pointer to the left node stored in "n". | |
2876 | ||
2877 | * `static void set_left(node_ptr n, node_ptr l);`: | |
2878 | Sets the pointer to the left node stored in "n" to "l". | |
2879 | ||
2880 | * `static node_ptr get_right(const_node_ptr n);`: | |
2881 | Returns a pointer to the right node stored in "n". | |
2882 | ||
2883 | * `static void set_right(node_ptr n, node_ptr r);`: | |
2884 | Sets the pointer to the right node stored in "n" to "r". | |
2885 | ||
2886 | * `static balance get_balance(const_node_ptr n);`: | |
2887 | Returns the balance factor stored in "n". | |
2888 | ||
2889 | * `static void set_balance(node_ptr n, balance b);`: | |
2890 | Sets the balance factor stored in "n" to "b". | |
2891 | ||
2892 | * `static balance negative();`: | |
2893 | Returns a value representing a negative balance factor. | |
2894 | ||
2895 | * `static balance zero();`: | |
2896 | Returns a value representing a zero balance factor. | |
2897 | ||
2898 | * `static balance positive();`: | |
2899 | Returns a value representing a positive balance factor. | |
2900 | ||
2901 | Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms | |
2902 | with our nodes: | |
2903 | ||
2904 | [import ../example/doc_avltree_algorithms.cpp] | |
2905 | [doc_avltree_algorithms_code] | |
2906 | ||
2907 | For a complete list of functions see | |
2908 | [classref boost::intrusive::avltree_algorithms avltree_algorithms reference]. | |
2909 | ||
2910 | [endsect] | |
2911 | ||
2912 | ||
2913 | [section:treap_algorithms Intrusive treap algorithms] | |
2914 | ||
2915 | [classref boost::intrusive::treap_algorithms treap_algorithms] have the same | |
2916 | interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms]. | |
2917 | ||
2918 | [c++] | |
2919 | ||
2920 | template<class NodeTraits> | |
2921 | struct treap_algorithms; | |
2922 | ||
2923 | [classref boost::intrusive::treap_algorithms treap_algorithms] | |
2924 | is configured with a NodeTraits class, which encapsulates | |
2925 | the information about the node to be manipulated. NodeTraits must support the | |
2926 | following interface: | |
2927 | ||
2928 | [*Typedefs]: | |
2929 | ||
2930 | * `node`: The type of the node that forms the circular treap | |
2931 | ||
2932 | * `node_ptr`: The type of a pointer to a node (usually node*) | |
2933 | ||
2934 | * `const_node_ptr`: The type of a pointer to a const node (usually const node*) | |
2935 | ||
2936 | [*Static functions]: | |
2937 | ||
2938 | * `static node_ptr get_parent(const_node_ptr n);`: | |
2939 | Returns a pointer to the parent node stored in "n". | |
2940 | ||
2941 | * `static void set_parent(node_ptr n, node_ptr p);`: | |
2942 | Sets the pointer to the parent node stored in "n" to "p". | |
2943 | ||
2944 | * `static node_ptr get_left(const_node_ptr n);`: | |
2945 | Returns a pointer to the left node stored in "n". | |
2946 | ||
2947 | * `static void set_left(node_ptr n, node_ptr l);`: | |
2948 | Sets the pointer to the left node stored in "n" to "l". | |
2949 | ||
2950 | * `static node_ptr get_right(const_node_ptr n);`: | |
2951 | Returns a pointer to the right node stored in "n". | |
2952 | ||
2953 | * `static void set_right(node_ptr n, node_ptr r);`: | |
2954 | Sets the pointer to the right node stored in "n" to "r". | |
2955 | ||
2956 | Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms | |
2957 | with our nodes: | |
2958 | ||
2959 | [import ../example/doc_treap_algorithms.cpp] | |
2960 | [doc_treap_algorithms_code] | |
2961 | ||
2962 | For a complete list of functions see | |
2963 | [classref boost::intrusive::treap_algorithms treap_algorithms reference]. | |
2964 | ||
2965 | [endsect] | |
2966 | ||
2967 | ||
2968 | [/ | |
2969 | / | |
2970 | /[section:sgtree_algorithms Intrusive sg tree algorithms] | |
2971 | / | |
2972 | / | |
2973 | /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms] have the same | |
2974 | /interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms]. | |
2975 | / | |
2976 | /[c++] | |
2977 | / | |
2978 | / template<class NodeTraits> | |
2979 | / struct sgtree_algorithms; | |
2980 | / | |
2981 | /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms] | |
2982 | /is configured with a NodeTraits class, which encapsulates | |
2983 | /the information about the node to be manipulated. NodeTraits must support the | |
2984 | /following interface: | |
2985 | / | |
2986 | /[*Typedefs]: | |
2987 | / | |
2988 | /* `node`: The type of the node that forms the circular sgtree | |
2989 | / | |
2990 | /* `node_ptr`: The type of a pointer to a node (usually node*) | |
2991 | / | |
2992 | /* `const_node_ptr`: The type of a pointer to a const node (usually const node*) | |
2993 | / | |
2994 | /[*Static functions]: | |
2995 | / | |
2996 | /* `static node_ptr get_parent(const_node_ptr n);`: | |
2997 | / Returns a pointer to the parent node stored in "n". | |
2998 | / | |
2999 | /* `static void set_parent(node_ptr n, node_ptr p);`: | |
3000 | / Sets the pointer to the parent node stored in "n" to "p". | |
3001 | / | |
3002 | /* `static node_ptr get_left(const_node_ptr n);`: | |
3003 | / Returns a pointer to the left node stored in "n". | |
3004 | / | |
3005 | /* `static void set_left(node_ptr n, node_ptr l);`: | |
3006 | / Sets the pointer to the left node stored in "n" to "l". | |
3007 | / | |
3008 | /* `static node_ptr get_right(const_node_ptr n);`: | |
3009 | / Returns a pointer to the right node stored in "n". | |
3010 | / | |
3011 | /* `static void set_right(node_ptr n, node_ptr r);`: | |
3012 | / Sets the pointer to the right node stored in "n" to "r". | |
3013 | / | |
3014 | /Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms | |
3015 | /with our nodes: | |
3016 | / | |
3017 | /[import ../example/doc_sgtree_algorithms.cpp] | |
3018 | /[doc_sgtree_algorithms_code] | |
3019 | / | |
3020 | /For a complete list of functions see | |
3021 | /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms reference]. | |
3022 | / | |
3023 | /[endsect] | |
3024 | /] | |
3025 | ||
3026 | [endsect] | |
3027 | ||
3028 | [section:value_traits Containers with custom ValueTraits] | |
3029 | ||
3030 | As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive] | |
3031 | containers need a `ValueTraits` class to perform transformations between nodes and | |
3032 | user values. `ValueTraits` can be explicitly configured (using the `value_traits<>` option) | |
3033 | or implicitly configured (using hooks and their `base_hook<>`/`member_hook<>` options). | |
3034 | `ValueTraits` contains | |
3035 | all the information to glue the `value_type` of the containers and the node to be | |
3036 | used in node algorithms, since these types can be different. Apart from this, | |
3037 | `ValueTraits` also stores information about the link policy of the values to be inserted. | |
3038 | ||
3039 | Instead of using [*Boost.Intrusive] predefined hooks | |
3040 | a user might want to develop customized containers, for example, using nodes that are | |
3041 | optimized for a specific | |
3042 | application or that are compatible with a legacy ABI. A user might want | |
3043 | to have only two additional pointers in his class and insert the class in a doubly | |
3044 | linked list sometimes and in a singly linked list in other situations. You can't | |
3045 | achieve this using [*Boost.Intrusive] predefined hooks. Now, instead of using | |
3046 | `base_hook<...>` or `member_hook<...>` options the user will specify the | |
3047 | `value_traits<...>` options. Let's see how we can do this: | |
3048 | ||
3049 | [section:value_traits_interface ValueTraits interface] | |
3050 | ||
3051 | `ValueTraits` has the following interface: | |
3052 | ||
3053 | [c++] | |
3054 | ||
3055 | #include <boost/intrusive/pointer_traits.hpp> | |
3056 | #include <boost/intrusive/link_mode.hpp> | |
3057 | ||
3058 | struct my_value_traits | |
3059 | { | |
3060 | typedef implementation_defined node_traits; | |
3061 | typedef implementation_defined value_type; | |
3062 | typedef node_traits::node_ptr node_ptr; | |
3063 | typedef node_traits::const_node_ptr const_node_ptr; | |
3064 | typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits | |
3065 | <value_type>::type::pointer pointer; | |
3066 | typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits | |
3067 | <const value_type>::type::pointer const_pointer; | |
3068 | ||
3069 | static const link_mode_type link_mode = some_linking_policy; | |
3070 | ||
3071 | static node_ptr to_node_ptr (value_type &value); | |
3072 | static const_node_ptr to_node_ptr (const value_type &value); | |
3073 | static pointer to_value_ptr (node_ptr n); | |
3074 | static const_pointer to_value_ptr (const_node_ptr n); | |
3075 | }; | |
3076 | ||
3077 | Let's explain each type and function: | |
3078 | ||
3079 | * [*['node_traits]]: The node configuration that is needed by node algorithms. | |
3080 | These node traits and algorithms are | |
3081 | described in the previous chapter: [link intrusive.node_algorithms Node Algorithms]. | |
3082 | ||
3083 | * If my_value_traits is meant to be used with [classref boost::intrusive::slist slist], | |
3084 | `node_traits` should follow | |
3085 | the interface needed by [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms]. | |
3086 | ||
3087 | * If my_value_traits is meant to be used with [classref boost::intrusive::list list], | |
3088 | `node_traits` should follow | |
3089 | the interface needed by [classref boost::intrusive::circular_list_algorithms circular_list_algorithms]. | |
3090 | ||
3091 | * If my_value_traits is meant to be used with [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset], | |
3092 | `node_traits` should follow | |
3093 | the interface needed by [classref boost::intrusive::rbtree_algorithms rbtree_algorithms]. | |
3094 | ||
3095 | * If my_value_traits is meant to be used with [classref boost::intrusive::unordered_set unordered_set]/ | |
3096 | [classref boost::intrusive::unordered_multiset unordered_multiset], `node_traits` | |
3097 | should follow the interface needed by [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms]. | |
3098 | ||
3099 | * [*['node_ptr]]: A typedef for `node_traits::node_ptr`. | |
3100 | ||
3101 | * [*['const_node_ptr]]: A typedef for `node_traits::const_node_ptr`. | |
3102 | ||
3103 | * [*['value_type]]: The type that the user wants to insert in the container. This type can be | |
3104 | the same as `node_traits::node` but it can be different (for example, `node_traits::node` | |
3105 | can be a member type of `value_type`). If `value_type` and `node_traits::node` are the | |
3106 | same type, the `to_node_ptr` and `to_value_ptr` functions are trivial. | |
3107 | ||
3108 | * [*['pointer]]: The type of a pointer to a `value_type`. It must be the same pointer type | |
3109 | as `node_ptr`: If `node_ptr` is `node*`, `pointer` must be `value_type*`. If | |
3110 | `node_ptr` is `smart_ptr<node_traits::node>`, `pointer` must be `smart_ptr<value_type>`. | |
3111 | This can be generically achieved using `boost::intrusive::pointer_traits` (portable implementation of C++11 | |
3112 | `std::pointer_traits`). | |
3113 | ||
3114 | * [*['const_pointer]]: The type of a pointer to a `const value_type`. It must be the same pointer type | |
3115 | as `node_ptr`: If `node_ptr` is `node*`, `const_pointer` must be `const value_type*`. If | |
3116 | `node_ptr` is `smart_ptr<node_traits::node>`, `const_pointer` must be `smart_ptr<const value_type>`. | |
3117 | ||
3118 | * [*['link_mode]]: Indicates that `value_traits` needs some additional work or checks from the | |
3119 | container. The types are enumerations defined in the `link_mode.hpp` header. | |
3120 | These are the possible types: | |
3121 | ||
3122 | * [*`normal_link`]: If this linking policy is specified in a `ValueTraits` class | |
3123 | as the link mode, containers | |
3124 | configured with such `ValueTraits` won't set the hooks | |
3125 | of the erased values to a default state. Containers also won't | |
3126 | check that the hooks of the new values are default initialized. | |
3127 | ||
3128 | * [*`safe_link`]: If this linking policy is specified as the link mode | |
3129 | in a `ValueTraits` class, containers | |
3130 | configured with this `ValueTraits` will set the hooks | |
3131 | of the erased values to a default state. Containers also will | |
3132 | check that the hooks of the new values are default initialized. | |
3133 | ||
3134 | * [*`auto_unlink`]: Same as "safe_link" but containers with | |
3135 | constant-time size features won't be | |
3136 | compatible with `ValueTraits` configured with this policy. | |
3137 | Containers also know that a value can be silently erased from | |
3138 | the container without using any function provided by the containers. | |
3139 | ||
3140 | * [*['static node_ptr to_node_ptr (value_type &value)]] and | |
3141 | [*['static const_node_ptr to_node_ptr (const value_type &value)]]: | |
3142 | These functions take a reference to a value_type and return a pointer to the node | |
3143 | to be used with node algorithms. | |
3144 | ||
3145 | * [*['static pointer to_value_ptr (node_ptr n)]] and | |
3146 | [*['static const_pointer to_value_ptr (const_node_ptr n)]]: | |
3147 | These functions take a pointer to a node and return a pointer to the value | |
3148 | that contains the node. | |
3149 | ||
3150 | [endsect] | |
3151 | ||
3152 | [section:value_traits_example Custom ValueTraits example] | |
3153 | ||
3154 | Let's define our own `value_traits` class to be able to use [*Boost.Intrusive] | |
3155 | containers with an old C structure whose definition can't be changed. | |
3156 | That legacy type has two pointers that can be used to build singly and doubly linked | |
3157 | lists: in singly linked lists we only need a pointer, whereas in doubly | |
3158 | linked lists, we need two pointers. Since we only have two pointers, we can't insert | |
3159 | the object in both a singly and a doubly linked list at the same time. | |
3160 | This is the definition of the old node: | |
3161 | ||
3162 | [import ../example/doc_value_traits.cpp] | |
3163 | [doc_value_traits_code_legacy] | |
3164 | ||
3165 | Now we have to define a NodeTraits class that will implement the functions/typedefs | |
3166 | that will make the legacy node compatible with [*Boost.Intrusive] algorithms. After that, | |
3167 | we'll define a ValueTraits class that will configure [*Boost.Intrusive] containers: | |
3168 | ||
3169 | [doc_value_traits_value_traits] | |
3170 | ||
3171 | Defining a value traits class that simply defines `value_type` as | |
3172 | `legacy_node_traits::node` is a common approach when defining customized | |
3173 | intrusive containers, so [*Boost.Intrusive] offers a templatized | |
3174 | [classref boost::intrusive::trivial_value_traits trivial_value_traits] class | |
3175 | that does exactly what we want: | |
3176 | ||
3177 | [doc_value_traits_trivial] | |
3178 | ||
3179 | Now we can just define the containers that will store the legacy abi objects and write | |
3180 | a little test: | |
3181 | ||
3182 | [doc_value_traits_test] | |
3183 | ||
3184 | As seen, several key elements of [*Boost.Intrusive] can be reused with custom user types, | |
3185 | if the user does not want to use the provided [*Boost.Intrusive] facilities. | |
3186 | ||
3187 | [endsect] | |
3188 | ||
3189 | [section:reusing_node_algorithms Reusing node algorithms for different values] | |
3190 | ||
3191 | In the previous example, `legacy_node_traits::node` type and | |
3192 | `legacy_value_traits::value_type` are the same type, but this is not necessary. It's possible | |
3193 | to have several `ValueTraits` defining the same `node_traits` type (and thus, the same `node_traits::node`). | |
3194 | This reduces the number of node algorithm instantiations, but | |
3195 | now `ValueTraits::to_node_ptr` and `ValueTraits::to_value_ptr` functions need to offer | |
3196 | conversions between both types. Let's see a small example: | |
3197 | ||
3198 | First, we'll define the node to be used in the algorithms. For a linked list, | |
3199 | we just need a node that stores two pointers: | |
3200 | ||
3201 | [import ../example/doc_advanced_value_traits.cpp] | |
3202 | [doc_advanced_value_traits_code] | |
3203 | ||
3204 | Now we'll define two different types that will be inserted in intrusive lists and | |
3205 | a templatized `ValueTraits` that will work for both types: | |
3206 | ||
3207 | [doc_advanced_value_traits_value_traits] | |
3208 | ||
3209 | Now define two containers. Both containers will instantiate the same list algorithms | |
3210 | (`circular_list_algorithms<simple_node_traits>`), | |
3211 | due to the fact that the value traits used to define the containers provide the same `node_traits` type: | |
3212 | ||
3213 | [doc_advanced_value_traits_containers] | |
3214 | ||
3215 | All [*Boost.Intrusive] containers using predefined hooks use this technique to minimize code size: | |
3216 | all possible [classref boost::intrusive::list list] containers | |
3217 | created with predefined hooks that define the same `VoidPointer` type | |
3218 | share the same list algorithms. | |
3219 | ||
3220 | [endsect] | |
3221 | ||
3222 | [section:simplifying_value_traits Simplifying value traits definition] | |
3223 | ||
3224 | The previous example can be further simplified using the | |
3225 | [classref boost::intrusive::derivation_value_traits derivation_value_traits] | |
3226 | class to define a value traits class with a value that stores the | |
3227 | `simple_node` as a base class: | |
3228 | ||
3229 | [import ../example/doc_derivation_value_traits.cpp] | |
3230 | [doc_derivation_value_traits_value_traits] | |
3231 | ||
3232 | We can even choose to store `simple_node` as a member of `value_1` and `value_2` | |
3233 | classes and use [classref boost::intrusive::member_value_traits member_value_traits] | |
3234 | to define the needed value traits classes: | |
3235 | ||
3236 | [import ../example/doc_member_value_traits.cpp] | |
3237 | [doc_member_value_traits_value_traits] | |
3238 | ||
3239 | [endsect] | |
3240 | ||
3241 | [section:stateful_value_traits Stateful value traits] | |
3242 | ||
3243 | Until now all shown custom value traits are stateless, that is, [*the transformation between nodes | |
3244 | and values is implemented in terms of static functions]. It's possible to use [*stateful] value traits | |
3245 | so that we can separate nodes and values and [*avoid modifying types to insert nodes]. | |
3246 | [*Boost.Intrusive] differentiates between stateful and stateless value traits by checking if all | |
3247 | Node <-> Value transformation functions are static or not (except for Visual 7.1, since overloaded | |
3248 | static function detection is not possible, in this case the implementation checks if the class is empty): | |
3249 | ||
3250 | * If all Node <-> Value transformation functions are static , a [*stateless] | |
3251 | value traits is assumed. transformations must be static functions. | |
3252 | * Otherwise a [*stateful] value traits is assumed. | |
3253 | ||
3254 | Using stateful value traits it's possible to create containers of non-copyable/movable objects [*without modifying] | |
3255 | the definition of the class to be inserted. This interesting property is achieved without using global variables | |
3256 | (stateless value traits could use global variables to achieve the same goal), so: | |
3257 | ||
3258 | * [*Thread-safety guarantees]: Better thread-safety guarantees can be achieved with stateful | |
3259 | value traits, since accessing global resources might require synchronization primitives that | |
3260 | can be avoided when using internal state. | |
3261 | * [*Flexibility]: A stateful value traits type can be configured at run-time. | |
3262 | * [*Run-time polymorphism]: A value traits might implement node <-> value | |
3263 | transformations as virtual functions. A single container type could be | |
3264 | configured at run-time to use different node <-> value relationships. | |
3265 | ||
3266 | Stateful value traits have many advantages but also some downsides: | |
3267 | ||
3268 | * [*Performance]: Value traits operations should be very efficient since they are basic operations used by containers. | |
3269 | [*A heavy node <-> value transformation will hurt intrusive containers' performance]. | |
3270 | * [*Exception guarantees]: The stateful ValueTraits must maintain no-throw guarantees, otherwise, the | |
3271 | container invariants won't be preserved. | |
3272 | * [*Static functions]: Some static functions offered by intrusive containers are not | |
3273 | available because node <-> value transformations are not static. | |
3274 | * [*Bigger iterators]: The size of some iterators is increased because the iterator | |
3275 | needs to store a pointer to the stateful value traits to implement node to value | |
3276 | transformations (e.g. `operator*()` and `operator->()`). | |
3277 | ||
3278 | An easy and useful example of stateful value traits is when an array of values can be indirectly introduced | |
3279 | in a list guaranteeing no additional allocation apart from the initial resource reservation: | |
3280 | ||
3281 | [import ../example/doc_stateful_value_traits.cpp] | |
3282 | [doc_stateful_value_traits] | |
3283 | ||
3284 | [endsect] | |
3285 | ||
3286 | [endsect] | |
3287 | ||
3288 | [section:thread_safety Thread safety guarantees] | |
3289 | ||
3290 | Intrusive containers have thread safety guarantees similar to STL containers. | |
3291 | ||
3292 | * Several threads having read or write access to different instances is safe as long as inserted | |
3293 | objects are different. | |
3294 | * Concurrent read-only access to the same container is safe. | |
3295 | ||
3296 | Some Intrusive hooks (auto-unlink hooks, for example) modify containers without | |
3297 | having a reference to them: this is considered a write access to the container. | |
3298 | ||
3299 | Other functions, like checking if an object is already inserted in a container using the `is_linked()` | |
3300 | member of safe hooks, constitute read access on the container without having a reference to it, so no other | |
3301 | thread should have write access (direct or indirect) to that container. | |
3302 | ||
3303 | Since the same object can be inserted in several containers at the same time using different hooks, | |
3304 | the thread safety of [*Boost.Intrusive] is related to the containers and also to the object whose lifetime | |
3305 | is manually managed by the user. | |
3306 | ||
3307 | As we can see, the analysis of the thread-safety of a program using [*Boost.Intrusive] is harder | |
3308 | than with non-intrusive containers. | |
3309 | ||
3310 | To analyze the thread safety, consider the following points: | |
3311 | ||
3312 | * The auto-unlink hook's destructor and `unlink()` functions modify the container indirectly. | |
3313 | * The safe mode and auto-unlink hooks' `is_linked()` functions are a read access to the container. | |
3314 | * Inserting an object in containers that will be modified by different threads has no thread safety | |
3315 | guarantee, although in most platforms it will be thread-safe without locking. | |
3316 | ||
3317 | [endsect] | |
3318 | ||
3319 | [section:scary_iterators Scary Iterators] | |
3320 | ||
3321 | The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf, | |
3322 | SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's | |
3323 | iterator types have no dependency on any type argument apart from the container's `value_type`, | |
3324 | `difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal, | |
3325 | the types of a standard container's iterators should not depend on the container's `key_compare`, | |
3326 | `hasher`, `key_equal`, or `allocator` types. | |
3327 | ||
3328 | That paper demonstrated that SCARY operations were crucial to the performant implementation of common | |
3329 | design patterns using STL components. It showed that implementations that support SCARY operations reduce | |
3330 | object code bloat by eliminating redundant specializations of iterator and algorithm templates. | |
3331 | ||
3332 | [*Boost.Intrusive] containers are a bit different from standard containers. In particular, they have no | |
3333 | allocator parameter and they can be configured with additional options not present in STL-like containers. | |
3334 | Thus [*Boost.Intrusive] offers its own `SCARY iterator` implementation, where iterator types don't | |
3335 | change when the container is configured with an option that does not alter the value <-> node transformation. | |
3336 | More concretely, the following options and conditions guarantee that iterator types are unchanged: | |
3337 | ||
3338 | * [*All containers]: `size_type<>`, `constant_time_size<>`, | |
3339 | * [*`slist`]: `cache_last<>`, `linear<>`, | |
3340 | * [*`unordered_[multi]set`]: `hash<>`, `equal<>`, `power_2_buckets<>`, `cache_begin<>`. | |
3341 | * [*All tree-like containers] (`[multi]set`, `avl_[multi]set`, `sg_[multi]set`, `bs_[multi]set`, | |
3342 | `splay_[multi]set`, `treap_[multi]set`): `compare<>`. | |
3343 | * [*`treap_[multi]set`]: `priority<>` | |
3344 | * [*`bs_[multi]set`, `sg_[multi]set`, `treap_[multi]set`, `splay_[multi]set`]: | |
3345 | They share the same iterator type when configured with the same options. | |
3346 | ||
3347 | [endsect] | |
3348 | ||
3349 | [section:equal_range_stability Stability and insertion with hint in ordered associative containers with equivalent keys] | |
3350 | ||
3351 | [*Boost.Intrusive] ordered associative containers with equivalent keys offer stability guarantees, following | |
3352 | [@http://open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 C++ standard library's defect #233 resolution], | |
3353 | 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]. | |
3354 | This means that: | |
3355 | ||
3356 | * A ['Insert without hint] member function always insert at the upper bound of an equal range. | |
3357 | * A ['Insert with hint] member function inserts the new value [*before the hint] if hint's and new node's keys are equivalent. | |
3358 | * Implements Andrew Koenig ['as close as possible to hint] proposal. A new element is always be inserted as close to the hint as possible. | |
3359 | So, for example, if there is a subsequence of equivalent values, `a.begin()` as the hint means that the new element should be inserted | |
3360 | before the subsequence even if `a.begin()` is far away. This allows code to always append (or prepend) an equal range with something | |
3361 | as simple as: `m.insert(m.end(), new_node);` or `m.insert(m.begin(), new_node);` | |
3362 | ||
3363 | [endsect] | |
3364 | ||
3365 | [section:obtaining_same_type_reducing_space Obtaining the same types and reducing symbol length] | |
3366 | ||
3367 | The flexible option specification mechanism used by [*Boost.Intrusive] for hooks and containers | |
3368 | has a couple of downsides: | |
3369 | ||
3370 | * If a user specifies the same options in different order or specifies some options and leaves the | |
3371 | rest as defaults, the type of the created container/hook will be different. Sometimes | |
3372 | this is annoying, because two programmers specifying the same options might end up with incompatible | |
3373 | types. For example, the following two lists, although using the same options, do not have | |
3374 | the same type: | |
3375 | ||
3376 | [c++] | |
3377 | ||
3378 | #include <boost/intrusive/list.hpp> | |
3379 | ||
3380 | using namespace boost::intrusive; | |
3381 | ||
3382 | //Explicitly specify constant-time size and size type | |
3383 | typedef list<T, constant_time_size<true>, size_type<std::size_t> List1; | |
3384 | ||
3385 | //Implicitly specify constant-time size and size type | |
3386 | typedef list<T> List2; | |
3387 | ||
3388 | * Option specifiers lead to long template symbols for classes and functions. Option specifiers themselves | |
3389 | are verbose and without variadic templates, several default template parameters are assigned for | |
3390 | non-specified options. Object and debugging information files can grow and compilation times | |
3391 | may suffer if long names are produced. | |
3392 | ||
3393 | To solve these issues [*Boost.Intrusive] offers some helper metafunctions that reduce symbol lengths | |
3394 | and create the same type if the same options (either explicitly or implicitly) are used. These also | |
3395 | improve compilation times. All containers and hooks have their respective `make_xxx` versions. | |
3396 | The previously shown example can be rewritten like this to obtain the same list type: | |
3397 | ||
3398 | [c++] | |
3399 | ||
3400 | #include <boost/intrusive/list.hpp> | |
3401 | ||
3402 | using namespace boost::intrusive; | |
3403 | ||
3404 | #include <boost/intrusive/list.hpp> | |
3405 | ||
3406 | using namespace boost::intrusive; | |
3407 | ||
3408 | //Explicitly specify constant-time size and size type | |
3409 | typedef make_list<T, constant_time_size<true>, size_type<std::size_t>::type List1; | |
3410 | ||
3411 | //Implicitly specify constant-time size and size type | |
3412 | typedef make_list<T>::type List2; | |
3413 | ||
3414 | Produced symbol lengths and compilation times will usually be shorter and object/debug files smaller. | |
3415 | If you are concerned with file sizes and compilation times, this option is your best choice. | |
3416 | ||
3417 | [endsect] | |
3418 | ||
3419 | [section:design_notes Design Notes] | |
3420 | ||
3421 | When designing [*Boost.Intrusive] the following guidelines have been taken into account: | |
3422 | ||
3423 | [section:performance_sensitive Boost.Intrusive in performance sensitive environments] | |
3424 | ||
3425 | [*Boost.Intrusive] should be a valuable tool in performance sensitive environments, | |
3426 | and following this guideline, [*Boost.Intrusive] has been designed to offer well | |
3427 | known complexity guarantees. Apart from that, some options, like optional | |
3428 | constant-time, have been designed to offer faster complexity guarantees in some | |
3429 | functions, like `slist::splice`. | |
3430 | ||
3431 | The advanced lookup and insertion functions for associative containers, taking | |
3432 | an arbitrary key type and predicates, were designed to avoid unnecessary object | |
3433 | constructions. | |
3434 | ||
3435 | [endsect] | |
3436 | ||
3437 | [section:space_constrained Boost.Intrusive in space constrained environments] | |
3438 | ||
3439 | [*Boost.Intrusive] should be useful in space constrained environments, | |
3440 | and following this guideline [*Boost.Intrusive] separates node algorithms | |
3441 | and intrusive containers to avoid instantiating node algorithms for each | |
3442 | user type. For example, a single class of red-black algorithms will be instantiated | |
3443 | to implement all set and multiset containers using raw pointers. This way, | |
3444 | [*Boost.Intrusive] seeks to avoid any code size overhead associated with templates. | |
3445 | ||
3446 | Apart from that, [*Boost.Intrusive] implements some size improvements: for example, | |
3447 | red-black trees embed the color bit in the parent pointer lower bit, if nodes | |
3448 | are two-byte aligned. The option to forgo constant-time size operations can | |
3449 | reduce container size, and this extra size optimization is noticeable | |
3450 | when the container is empty or contains few values. | |
3451 | ||
3452 | [endsect] | |
3453 | ||
3454 | [section:basic_building_block Boost.Intrusive as a basic building block] | |
3455 | ||
3456 | [*Boost.Intrusive] can be a basic building block to build more complex containers | |
3457 | and this potential has motivated many design decisions. For example, the ability | |
3458 | to have more than one hook per user type opens the opportunity to implement multi-index | |
3459 | containers on top of [*Boost.Intrusive]. | |
3460 | ||
3461 | [*Boost.Intrusive] containers implement advanced functions taking function objects | |
3462 | as arguments (`clone_from`, `erase_and_dispose`, `insert_check`, etc.). These | |
3463 | functions come in handy when implementing non-intrusive containers | |
3464 | (for example, STL-like containers) on top of intrusive containers. | |
3465 | ||
3466 | [endsect] | |
3467 | ||
3468 | [section:extending_intrusive Extending Boost.Intrusive] | |
3469 | ||
3470 | [*Boost.Intrusive] offers a wide range of containers but also allows the | |
3471 | construction of custom containers reusing [*Boost.Intrusive] elements. | |
3472 | The programmer might want to use node algorithms directly or | |
3473 | build special hooks that take advantage of an application environment. | |
3474 | ||
3475 | For example, the programmer can customize parts of [*Boost.Intrusive] | |
3476 | to manage old data structures whose definition can't be changed. | |
3477 | ||
3478 | [endsect] | |
3479 | ||
3480 | [endsect] | |
3481 | ||
3482 | [section:performance Performance] | |
3483 | ||
3484 | [*Boost.Intrusive] containers offer speed improvements compared to non-intrusive containers | |
3485 | primarily because: | |
3486 | ||
3487 | * They minimize memory allocation/deallocation calls. | |
3488 | * They obtain better memory locality. | |
3489 | ||
3490 | This section will show performance tests comparing some operations on | |
3491 | `boost::intrusive::list` and `std::list`: | |
3492 | ||
3493 | * Insertions using `push_back` and container destruction will show the | |
3494 | overhead associated with memory allocation/deallocation. | |
3495 | * The `reverse` member function will show the advantages of the compact | |
3496 | memory representation that can be achieved with intrusive containers. | |
3497 | * The `sort` and `write access` tests will show the advantage of intrusive containers | |
3498 | minimizing memory accesses compared to containers of pointers. | |
3499 | ||
3500 | Given an object of type `T`, [classref boost::intrusive::list boost::intrusive::list<T>] | |
3501 | can replace `std::list<T>` to avoid memory allocation overhead, | |
3502 | or it can replace `std::list<T*>` when the user wants containers with | |
3503 | polymorphic values or wants to share values between several containers. | |
3504 | Because of this versatility, the performance tests will be executed for 6 different | |
3505 | list types: | |
3506 | ||
3507 | * 3 intrusive lists holding a class named `itest_class`, | |
3508 | each one with a different linking policy (`normal_link`, `safe_link`, `auto_unlink`). | |
3509 | The `itest_class` objects will be tightly packed in a `std::vector<itest_class>` object. | |
3510 | ||
3511 | * `std::list<test_class>`, where `test_class` is exactly the same as `itest_class`, | |
3512 | but without the intrusive hook. | |
3513 | ||
3514 | * `std::list<test_class*>`. The list will contain pointers to `test_class` objects | |
3515 | tightly packed in a `std::vector<test_class>` object. We'll call this configuration ['compact pointer list] | |
3516 | ||
3517 | * `std::list<test_class*>`. The list will contain pointers to `test_class` objects owned by a | |
3518 | `std::list<test_class>` object. We'll call this configuration ['disperse pointer list]. | |
3519 | ||
3520 | Both `test_class` and `itest_class` are templatized classes that can be configured with | |
3521 | a boolean to increase the size of the object. This way, the tests can be executed with | |
3522 | small and big objects. Here is the first part of the testing code, which shows | |
3523 | the definitions of `test_class` and `itest_class` classes, and some other | |
3524 | utilities: | |
3525 | ||
3526 | [import ../perf/perf_list.cpp] | |
3527 | [perf_list_value_type] | |
3528 | ||
3529 | As we can see, `test_class` is a very simple class holding an `int`. `itest_class` | |
3530 | is just a class that has a base hook ([classref boost::intrusive::list_base_hook list_base_hook]) | |
3531 | and also derives from `test_class`. | |
3532 | ||
3533 | `func_ptr_adaptor` is just a functor adaptor to convert function objects taking | |
3534 | `test_list` objects to function objects taking pointers to them. | |
3535 | ||
3536 | You can find the full test code in the | |
3537 | [@../../libs/intrusive/perf/perf_list.cpp perf_list.cpp] source file. | |
3538 | ||
3539 | [section:performance_results_push_back Back insertion and destruction] | |
3540 | ||
3541 | The first test will measure the benefits we can obtain with intrusive containers | |
3542 | avoiding memory allocations and deallocations. All the objects to be | |
3543 | inserted in intrusive containers are allocated in a single allocation call, | |
3544 | whereas `std::list` will need to allocate memory for each object and deallocate it | |
3545 | for every erasure (or container destruction). | |
3546 | ||
3547 | Let's compare the code to be executed for each container type for different insertion tests: | |
3548 | ||
3549 | [perf_list_push_back_intrusive] | |
3550 | ||
3551 | For intrusive containers, all the values are created in a vector and after that | |
3552 | inserted in the intrusive list. | |
3553 | ||
3554 | [perf_list_push_back_stdlist] | |
3555 | ||
3556 | For a standard list, elements are pushed back using push_back(). | |
3557 | ||
3558 | [perf_list_push_back_stdptrlist] | |
3559 | ||
3560 | For a standard compact pointer list, elements are created in a vector and pushed back | |
3561 | in the pointer list using push_back(). | |
3562 | ||
3563 | [perf_list_push_back_disperse_stdptrlist] | |
3564 | ||
3565 | For a ['disperse pointer list], elements are created in a list and pushed back | |
3566 | in the pointer list using push_back(). | |
3567 | ||
3568 | These are the times in microseconds for each case, and the normalized time: | |
3569 | ||
3570 | [table Back insertion + destruction times for Visual C++ 7.1 / Windows XP | |
3571 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3572 | [[`normal_link` intrusive list] [5000 / 22500] [1 / 1]] | |
3573 | [[`safe_link` intrusive list] [7812 / 32187] [1.56 / 1.43]] | |
3574 | [[`auto_unlink` intrusive list] [10156 / 41562] [2.03 / 1.84]] | |
3575 | [[Standard list] [26875 / 97500] [5.37 / 4.33]] | |
3576 | [[Standard compact pointer list] [76406 / 86718] [15.28 / 3.85]] | |
3577 | [[Standard disperse pointer list] [146562 / 175625] [29.31 / 7.80]] | |
3578 | ] | |
3579 | ||
3580 | [table Back insertion + destruction times for GCC 4.1.1 / MinGW over Windows XP | |
3581 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3582 | [[`normal_link` intrusive list] [4375 / 22187] [1 / 1]] | |
3583 | [[`safe_link` intrusive list] [7812 / 32812] [1.78 / 1.47]] | |
3584 | [[`auto_unlink` intrusive list] [10468 / 42031] [2.39 / 1.89]] | |
3585 | [[Standard list] [81250 / 98125] [18.57 / 4.42]] | |
3586 | [[Standard compact pointer list] [83750 / 94218] [19.14 / 4.24]] | |
3587 | [[Standard disperse pointer list] [155625 / 175625] [35.57 / 7.91]] | |
3588 | ] | |
3589 | ||
3590 | [table Back insertion + destruction times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2) | |
3591 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3592 | [[`normal_link` intrusive list] [4792 / 20495] [1 / 1]] | |
3593 | [[`safe_link` intrusive list] [7709 / 30803] [1.60 / 1.5]] | |
3594 | [[`auto_unlink` intrusive list] [10180 / 41183] [2.12 / 2.0]] | |
3595 | [[Standard list] [17031 / 32586] [3.55 / 1.58]] | |
3596 | [[Standard compact pointer list] [27221 / 34823] [5.68 / 1.69]] | |
3597 | [[Standard disperse pointer list] [102272 / 60056] [21.34 / 2.93]] | |
3598 | ] | |
3599 | ||
3600 | The results are logical: intrusive lists just need one allocation. The destruction | |
3601 | time of the `normal_link` intrusive container is trivial (complexity: `O(1)`), | |
3602 | whereas `safe_link` and `auto_unlink` intrusive containers need to put the hooks of | |
3603 | erased values in the default state (complexity: `O(NumElements)`). That's why | |
3604 | `normal_link` intrusive list shines in this test. | |
3605 | ||
3606 | Non-intrusive containers need to make many more allocations and that's why they | |
3607 | lag behind. The `disperse pointer list` needs to make `NumElements*2` allocations, | |
3608 | so the result is not surprising. | |
3609 | ||
3610 | The Linux test shows that standard containers perform very well against intrusive containers | |
3611 | with big objects. Nearly the same GCC version in MinGW performs worse, so maybe | |
3612 | a good memory allocator is the reason for these excellent results. | |
3613 | ||
3614 | [endsect] | |
3615 | ||
3616 | [section:performance_results_reversing Reversing] | |
3617 | ||
3618 | The next test measures the time needed to complete calls to the member function `reverse()`. | |
3619 | Values (`test_class` and `itest_class`) and lists are created as explained in the | |
3620 | previous section. | |
3621 | ||
3622 | Note that for pointer lists, `reverse` [*does not need to access `test_class` values | |
3623 | stored in another list or vector], | |
3624 | since this function just needs to adjust internal pointers, so in theory all tested | |
3625 | lists need to perform the same operations. | |
3626 | ||
3627 | These are the results: | |
3628 | ||
3629 | [table Reverse times for Visual C++ 7.1 / Windows XP | |
3630 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3631 | [[`normal_link` intrusive list] [2656 / 10625] [1 / 1.83]] | |
3632 | [[`safe_link` intrusive list] [2812 / 10937] [1.05 / 1.89]] | |
3633 | [[`auto_unlink` intrusive list] [2710 / 10781] [1.02 / 1.86]] | |
3634 | [[Standard list] [5781 / 14531] [2.17 / 2.51]] | |
3635 | [[Standard compact pointer list] [5781 / 5781] [2.17 / 1]] | |
3636 | [[Standard disperse pointer list] [10781 / 15781] [4.05 / 2.72]] | |
3637 | ] | |
3638 | ||
3639 | [table Reverse times for GCC 4.1.1 / MinGW over Windows XP | |
3640 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3641 | [[`normal_link` intrusive list] [2656 / 10781] [1 / 2.22]] | |
3642 | [[`safe_link` intrusive list] [2656 / 10781] [1 / 2.22]] | |
3643 | [[`auto_unlink` intrusive list] [2812 / 10781] [1.02 / 2.22]] | |
3644 | [[Standard list] [4843 / 12500] [1.82 / 2.58]] | |
3645 | [[Standard compact pointer list] [4843 / 4843] [1.82 / 1]] | |
3646 | [[Standard disperse pointer list] [9218 / 12968] [3.47 / 2.67]] | |
3647 | ] | |
3648 | ||
3649 | [table Reverse times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2) | |
3650 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3651 | [[`normal_link` intrusive list] [2742 / 10847] [1 / 3.41]] | |
3652 | [[`safe_link` intrusive list] [2742 / 10847] [1 / 3.41]] | |
3653 | [[`auto_unlink` intrusive list] [2742 / 11027] [1 / 3.47]] | |
3654 | [[Standard list] [3184 / 10942] [1.16 / 3.44]] | |
3655 | [[Standard compact pointer list] [3207 / 3176] [1.16 / 1]] | |
3656 | [[Standard disperse pointer list] [5814 / 13381] [2.12 / 4.21]] | |
3657 | ] | |
3658 | ||
3659 | For small objects the results show that the compact storage of values in intrusive | |
3660 | containers improve locality and reversing is faster than with standard containers, | |
3661 | whose values might be dispersed in memory because each value is independently | |
3662 | allocated. Note that the dispersed pointer list (a list of pointers to values | |
3663 | allocated in another list) suffers more because nodes of the pointer list | |
3664 | might be more dispersed, since allocations from both lists are interleaved | |
3665 | in the code: | |
3666 | ||
3667 | [c++] | |
3668 | ||
3669 | //Object list (holding `test_class`) | |
3670 | stdlist objects; | |
3671 | ||
3672 | //Pointer list (holding `test_class` pointers) | |
3673 | stdptrlist l; | |
3674 | ||
3675 | for(int i = 0; i < NumElements; ++i){ | |
3676 | //Allocation from the object list | |
3677 | objects.push_back(stdlist::value_type(i)); | |
3678 | //Allocation from the pointer list | |
3679 | l.push_back(&objects.back()); | |
3680 | } | |
3681 | ||
3682 | For big objects the compact pointer list wins because the reversal test doesn't need access | |
3683 | to values stored in another container. Since all the allocations for nodes of | |
3684 | this pointer list are likely to be close (since there is no other allocation in the | |
3685 | process until the pointer list is created) locality is better than with intrusive | |
3686 | containers. The dispersed pointer list, as with small values, has poor locality. | |
3687 | ||
3688 | [endsect] | |
3689 | ||
3690 | [section:performance_results_sorting Sorting] | |
3691 | ||
3692 | The next test measures the time needed to complete calls to the member function | |
3693 | `sort(Pred pred)`. Values (`test_class` and `itest_class`) and lists are created as explained in the | |
3694 | first section. The values will be sorted in ascending and descending order each | |
3695 | iteration. For example, if ['l] is a list: | |
3696 | ||
3697 | [c++] | |
3698 | ||
3699 | for(int i = 0; i < NumIter; ++i){ | |
3700 | if(!(i % 2)) | |
3701 | l.sort(std::greater<stdlist::value_type>()); | |
3702 | else | |
3703 | l.sort(std::less<stdlist::value_type>()); | |
3704 | } | |
3705 | ||
3706 | For a pointer list, the function object will be adapted using `func_ptr_adaptor`: | |
3707 | ||
3708 | [c++] | |
3709 | ||
3710 | for(int i = 0; i < NumIter; ++i){ | |
3711 | if(!(i % 2)) | |
3712 | l.sort(func_ptr_adaptor<std::greater<stdlist::value_type> >()); | |
3713 | else | |
3714 | l.sort(func_ptr_adaptor<std::less<stdlist::value_type> >()); | |
3715 | } | |
3716 | ||
3717 | Note that for pointer lists, `sort` will take a function object that [*will access | |
3718 | `test_class` values stored in another list or vector], so pointer lists will suffer | |
3719 | an extra indirection: they will need to access the `test_class` values stored in | |
3720 | another container to compare two elements. | |
3721 | ||
3722 | These are the results: | |
3723 | ||
3724 | [table Sort times for Visual C++ 7.1 / Windows XP | |
3725 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3726 | [[`normal_link` intrusive list] [16093 / 38906] [1 / 1]] | |
3727 | [[`safe_link` intrusive list] [16093 / 39062] [1 / 1]] | |
3728 | [[`auto_unlink` intrusive list] [16093 / 38906] [1 / 1]] | |
3729 | [[Standard list] [32343 / 56406] [2.0 / 1.44]] | |
3730 | [[Standard compact pointer list] [33593 / 46093] [2.08 / 1.18]] | |
3731 | [[Standard disperse pointer list] [46875 / 68593] [2.91 / 1.76]] | |
3732 | ] | |
3733 | ||
3734 | [table Sort times for GCC 4.1.1 / MinGW over Windows XP | |
3735 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3736 | [[`normal_link` intrusive list] [15000 / 39218] [1 / 1]] | |
3737 | [[`safe_link` intrusive list] [15156 / 39531] [1.01 / 1.01]] | |
3738 | [[`auto_unlink` intrusive list] [15156 / 39531] [1.01 / 1.01]] | |
3739 | [[Standard list] [34218 / 56875] [2.28 / 1.45]] | |
3740 | [[Standard compact pointer list] [35468 / 49218] [2.36 / 1.25]] | |
3741 | [[Standard disperse pointer list] [47656 / 70156] [3.17 / 1.78]] | |
3742 | ] | |
3743 | ||
3744 | [table Sort times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2) | |
3745 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3746 | [[`normal_link` intrusive list] [18003 / 40795] [1 / 1]] | |
3747 | [[`safe_link` intrusive list] [18003 / 41017] [1 / 1]] | |
3748 | [[`auto_unlink` intrusive list] [18230 / 40941] [1.01 / 1]] | |
3749 | [[Standard list] [26273 / 49643] [1.45 / 1.21]] | |
3750 | [[Standard compact pointer list] [28540 / 43172] [1.58 / 1.05]] | |
3751 | [[Standard disperse pointer list] [35077 / 57638] [1.94 / 1.41]] | |
3752 | ] | |
3753 | ||
3754 | The results show that intrusive containers are faster than standard | |
3755 | containers. We can see that the pointer | |
3756 | list holding pointers to values stored in a vector is quite fast, so the extra | |
3757 | indirection that is needed to access the value is minimized because all the values | |
3758 | are tightly stored, improving caching. The disperse list, on the other hand, is | |
3759 | slower because the indirection to access values stored in the object list is | |
3760 | more expensive than accessing values stored in a vector. | |
3761 | ||
3762 | [endsect] | |
3763 | ||
3764 | [section:performance_results_write_access Write access] | |
3765 | ||
3766 | The next test measures the time needed to iterate through all the elements of a list, and | |
3767 | increment the value of the internal `i_` member: | |
3768 | ||
3769 | [c++] | |
3770 | ||
3771 | stdlist::iterator it(l.begin()), end(l.end()); | |
3772 | for(; it != end; ++it) | |
3773 | ++(it->i_); | |
3774 | ||
3775 | Values (`test_class` and `itest_class`) and lists are created as explained in | |
3776 | the first section. Note that for pointer lists, the iteration will suffer | |
3777 | an extra indirection: they will need to access the `test_class` values stored in | |
3778 | another container: | |
3779 | ||
3780 | [c++] | |
3781 | ||
3782 | stdptrlist::iterator it(l.begin()), end(l.end()); | |
3783 | for(; it != end; ++it) | |
3784 | ++((*it)->i_); | |
3785 | ||
3786 | These are the results: | |
3787 | ||
3788 | [table Write access times for Visual C++ 7.1 / Windows XP | |
3789 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3790 | [[`normal_link` intrusive list] [2031 / 8125] [1 / 1]] | |
3791 | [[`safe_link` intrusive list] [2031 / 8281] [1 / 1.01]] | |
3792 | [[`auto_unlink` intrusive list] [2031 / 8281] [1 / 1.01]] | |
3793 | [[Standard list] [4218 / 10000] [2.07 / 1.23]] | |
3794 | [[Standard compact pointer list] [4062 / 8437] [2.0 / 1.03]] | |
3795 | [[Standard disperse pointer list] [8593 / 13125] [4.23 / 1.61]] | |
3796 | ] | |
3797 | ||
3798 | [table Write access times for GCC 4.1.1 / MinGW over Windows XP | |
3799 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3800 | [[`normal_link` intrusive list] [2343 / 8281] [1 / 1]] | |
3801 | [[`safe_link` intrusive list] [2500 / 8281] [1.06 / 1]] | |
3802 | [[`auto_unlink` intrusive list] [2500 / 8281] [1.06 / 1]] | |
3803 | [[Standard list] [4218 / 10781] [1.8 / 1.3]] | |
3804 | [[Standard compact pointer list] [3906 / 8281] [1.66 / 1]] | |
3805 | [[Standard disperse pointer list] [8281 / 13750] [3.53 / 1.66]] | |
3806 | ] | |
3807 | ||
3808 | [table Write access times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2) | |
3809 | [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]] | |
3810 | [[`normal_link` intrusive list] [2286 / 8468] [1 / 1.1]] | |
3811 | [[`safe_link` intrusive list] [2381 / 8412] [1.04 / 1.09]] | |
3812 | [[`auto_unlink` intrusive list] [2301 / 8437] [1.01 / 1.1]] | |
3813 | [[Standard list] [3044 / 9061] [1.33 / 1.18]] | |
3814 | [[Standard compact pointer list] [2755 / 7660] [1.20 / 1]] | |
3815 | [[Standard disperse pointer list] [6118 / 12453] [2.67 / 1.62]] | |
3816 | ] | |
3817 | ||
3818 | As with the read access test, the results show that intrusive containers outperform | |
3819 | all other containers if the values are tightly packed in a vector. | |
3820 | The disperse list is again the slowest. | |
3821 | ||
3822 | [endsect] | |
3823 | ||
3824 | [section:performance_results_conclusions Conclusions] | |
3825 | ||
3826 | Intrusive containers can offer performance benefits that cannot be achieved with | |
3827 | equivalent non-intrusive containers. Memory locality improvements are noticeable | |
3828 | when the objects to be inserted are small. Minimizing memory allocation/deallocation calls is also | |
3829 | an important factor and intrusive containers make this simple if all objects | |
3830 | to be inserted in intrusive containers are allocated using `std::vector` or `std::deque`. | |
3831 | ||
3832 | [endsect] | |
3833 | ||
3834 | [endsect] | |
3835 | ||
3836 | [section:release_notes Release Notes] | |
3837 | ||
3838 | [section:release_notes_boost_1_62_00 Boost 1.62 Release] | |
3839 | ||
3840 | * Fixed bugs: | |
3841 | * [@https://svn.boost.org/trac/boost/ticket/11476 Boost Trac #11476: ['has_member_function_callable_with.hpp is massively broken with BOOST_NO_CXX11_DECLTYPE]] | |
3842 | * [@https://svn.boost.org/trac/boost/ticket/11994 Boost Trac #11994: ['Support intrusive container key extractors that return the key by value]] | |
3843 | * [@https://svn.boost.org/trac/boost/ticket/12184 Boost Trac #12184: ['clang -Wdocumentation warning]] | |
3844 | * [@https://svn.boost.org/trac/boost/ticket/12190 Boost Trac #12190: ['Intrusive List + Flat Map combination crashes]] | |
3845 | * [@https://svn.boost.org/trac/boost/ticket/12229 Boost Trac #12229: ['intrusive::unordered_set<T>::rehash() broken]] | |
3846 | * [@https://svn.boost.org/trac/boost/ticket/12245 Boost Trac #12245: ['bstree uses a shared static size_traits for constant_time_size<false>]] | |
3847 | * [@https://svn.boost.org/trac/boost/ticket/12432 Boost Trac #12432: ['Forced KeyOfValue creation when using custom compare on insert_check]] | |
3848 | ||
3849 | * Implemented `merge` functions in ordered associative containers. | |
3850 | * Officially documented `root()` function for tree-based containers. | |
3851 | ||
3852 | [endsect] | |
3853 | ||
3854 | [section:release_notes_boost_1_61_00 Boost 1.61 Release] | |
3855 | ||
3856 | * Fixed bugs: | |
3857 | * [@https://svn.boost.org/trac/boost/ticket/11832 Boost Trac #11832: ['clang-cl + boost intrusive = miscompile]] | |
3858 | * [@https://svn.boost.org/trac/boost/ticket/11865 Boost Trac #11865: ['Intrusive list explicit ctor error with Clang 3.6 (C++11/14)]] | |
3859 | * [@https://svn.boost.org/trac/boost/ticket/11992 Boost Trac #11992: ['Add an overload of insert_check taking a key_type]] | |
3860 | * [@https://github.com/boostorg/intrusive/pull/19 GitHub Pull #19: ['ebo_functor_holder: compile fix for copy constructor]] | |
3861 | ||
3862 | [endsect] | |
3863 | ||
3864 | [section:release_notes_boost_1_60_00 Boost 1.60 Release] | |
3865 | ||
3866 | * [link intrusive.advanced_lookups_insertions Advanced lookup and insertions] in ordered associative containers | |
3867 | now support comparison functions that are not required to offer the same strict weak ordering as `key_compare`, | |
3868 | the container must be partitioned in regards to the passed comparison object. | |
3869 | * Fixed bugs: | |
3870 | * [@https://svn.boost.org/trac/boost/ticket/11701 Boost Trac #11701: ['Regression in boost::intrusive::set::equal_range]] | |
3871 | * [@https://svn.boost.org/trac/boost/ticket/11765 Boost Trac #11765: ['sgtree.hpp:830: bad if test ?]] | |
3872 | ||
3873 | [endsect] | |
3874 | ||
3875 | [section:release_notes_boost_1_59_00 Boost 1.59 Release] | |
3876 | ||
3877 | * Implemented [link intrusive.map_multimap map and multimap-like interfaces]. | |
3878 | * Refactored hashtable containers to reduce template instantiations. | |
3879 | * Fixed bugs: | |
3880 | * [@https://svn.boost.org/trac/boost/ticket/11222 Boost Trac #11222: ['intrusive/pointer_traits.hpp fails to compile with C++98]] | |
3881 | ||
3882 | [endsect] | |
3883 | ||
3884 | [section:release_notes_boost_1_58_00 Boost 1.58 Release] | |
3885 | ||
3886 | * Reduced compile-time dependencies, headers, and the use of Boost.Preprocessor, specially for hooks and iterators. | |
3887 | * Fixed bugs: | |
3888 | * [@https://svn.boost.org/trac/boost/ticket/6720 Boost Trac #6720: ['intrusive::unordered_set::clear_and_dispose does not compile on VC11 Beta when passed a stateless lambda]] | |
3889 | * [@https://svn.boost.org/trac/boost/ticket/10771 Boost Trac #10771: ['remove_if is broken for slist]] | |
3890 | * [@https://svn.boost.org/trac/boost/ticket/10853 Boost Trac #10853: ['problem with detection of const_cast_from]] | |
3891 | * [@https://svn.boost.org/trac/boost/ticket/10987 Boost Trac #10987: ['bug in any_xxx_node_traits, returning by reference]] | |
3892 | ||
3893 | [endsect] | |
3894 | ||
3895 | [section:release_notes_boost_1_57_00 Boost 1.57 Release] | |
3896 | ||
3897 | * Experimental version of node checkers, contributed by Matei David. Many thanks! | |
3898 | * Implemented [@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf N3644: Null Forward Iterators] from C++14. | |
3899 | * Fixed bugs: | |
3900 | * [@https://github.com/boostorg/intrusive/pull/12 GitHub Pull #12: ['Fix MSVC14 warning C4456: declaration of 'x_parent_right' hides previous local declaration]] | |
3901 | * [@https://svn.boost.org/trac/boost/ticket/10520 Boost Trac #10520: ['Conversion warning in intrusive/detail/utilities.hpp]] | |
3902 | * [@https://svn.boost.org/trac/boost/ticket/10469 Boost Trac #10469: ['Erasing from intrusive unordered_multiset with optimize_multikey goes into an infinite loop]] | |
3903 | ||
3904 | [endsect] | |
3905 | ||
3906 | [section:release_notes_boost_1_56_00 Boost 1.56 Release] | |
3907 | ||
3908 | * Improved Doxygen generated reference and updated and fixed forward-declaration header. | |
3909 | ||
3910 | * [*ABI breaking]: Fixed ABI regression introduced in Boost 1.55 version, mainly noticeable on MSVC compilers. | |
3911 | ||
3912 | * [*Source breaking]: Removed previously deprecated `xxx_dont_splay` functions from splay containers, | |
3913 | `splay_set_base_hook` and `splay_set_member_hook`from splay containers and `bool splay = true` | |
3914 | extra parameter in `splaytree_algorithms` functions. | |
3915 | ||
3916 | * Fixed bugs: | |
3917 | * [@https://svn.boost.org/trac/boost/ticket/8468 #8468: Compile error on visual studio 2010/2012 using vector with custom allocator and aligned types] | |
3918 | * [@https://svn.boost.org/trac/boost/ticket/9332 #9332: ['"has_member_function_callable_with.hpp compile error on msvc-12.0"]]. | |
3919 | * [@https://svn.boost.org/trac/boost/ticket/9650 #9650: ['"intrusive list with stateful value traits"]]. | |
3920 | * [@https://svn.boost.org/trac/boost/ticket/9746 #9746: Modern Sun CC compiler detects error in intrusive library header] | |
3921 | * [@https://svn.boost.org/trac/boost/ticket/9940 #9940: bad bug in intrusive list with safe_link (or auto_unlink) hooks] | |
3922 | * [@https://svn.boost.org/trac/boost/ticket/9948 #9948: remove use of const_cast in intrusive containers] | |
3923 | * [@https://svn.boost.org/trac/boost/ticket/9949 #9949: clear header node hooks upon intrusive container destruction] | |
3924 | * [@https://svn.boost.org/trac/boost/ticket/9961 #9961: tests for hooks not derived frorm generic_hook] | |
3925 | ||
3926 | * Optimized tree rebalancing code to avoid redundant assignments. | |
3927 | ||
3928 | * Added 64 bit prime values for `suggested_upper_bucket_count`/`suggested_lower_bucket_count` in 64 bit platforms. | |
3929 | ||
3930 | * Deleted workarounds for old SUN_CC compilers, those are now unsupported as modern SunPro compilers are standard-corforming enough. | |
3931 | ||
3932 | [endsect] | |
3933 | ||
3934 | [section:release_notes_boost_1_55_00 Boost 1.55 Release] | |
3935 | ||
3936 | * [*Source breaking]: Deprecated `xxx_dont_splay` functions from splay containers. | |
3937 | Deprecated `splay_set_base_hook` and `splay_set_member_hook`from splay containers, use | |
3938 | `bs_set_base_hook` or `bs_set_member_hook` instead. | |
3939 | Both will be removed in Boost 1.56. | |
3940 | ||
3941 | * [*ABI breaking]: Hash containers' end iterator was implemented pointing to one-past the end of the bucket array | |
3942 | (see [@https://svn.boost.org/trac/boost/ticket/8698 #8698]) causing severe bugs when values to be inserted | |
3943 | where allocated next to the bucket array. End iterator implementation was changed to point to the beginning | |
3944 | of the bucket array. | |
3945 | ||
3946 | * Big refactoring in order to reduce template and debug symbol bloat. Test object files have been slashed | |
3947 | to half in MSVC compilers in Debug mode. Toolchains without Identical COMDAT Folding (ICF) should notice size improvements. | |
3948 | ||
3949 | * Implemented [link intrusive.scary_iterators SCARY iterators]. | |
3950 | ||
3951 | [endsect] | |
3952 | ||
3953 | [section:release_notes_boost_1_54_00 Boost 1.54 Release] | |
3954 | ||
3955 | * Added `BOOST_NO_EXCEPTIONS` support (bug [@https://svn.boost.org/trac/boost/ticket/7849 #7849]). | |
3956 | ||
3957 | [endsect] | |
3958 | ||
3959 | [section:release_notes_boost_1_53_00 Boost 1.53 Release] | |
3960 | ||
3961 | * Fixed bugs | |
3962 | [@https://svn.boost.org/trac/boost/ticket/7174 #7174], | |
3963 | [@https://svn.boost.org/trac/boost/ticket/7529 #7529], | |
3964 | [@https://svn.boost.org/trac/boost/ticket/7815 #7815]. | |
3965 | * Fixed GCC -Wshadow warnings. | |
3966 | * Added missing `explicit` keyword in several intrusive container constructors. | |
3967 | * Replaced deprecated BOOST_NO_XXXX with newer BOOST_NO_CXX11_XXX macros. | |
3968 | * Small documentation fixes. | |
3969 | ||
3970 | [endsect] | |
3971 | ||
3972 | [section:release_notes_boost_1_51_00 Boost 1.51 Release] | |
3973 | ||
3974 | * Fixed bugs | |
3975 | [@https://svn.boost.org/trac/boost/ticket/6841 #6841], | |
3976 | [@https://svn.boost.org/trac/boost/ticket/6907 #6907], | |
3977 | [@https://svn.boost.org/trac/boost/ticket/6922 #6922], | |
3978 | [@https://svn.boost.org/trac/boost/ticket/7033 #7033], | |
3979 | ||
3980 | * Added `bounded_range` function to trees. | |
3981 | ||
3982 | [endsect] | |
3983 | ||
3984 | [section:release_notes_boost_1_49_00 Boost 1.49 Release] | |
3985 | ||
3986 | * Fixed bugs | |
3987 | [@https://svn.boost.org/trac/boost/ticket/6347 #6347], | |
3988 | [@https://svn.boost.org/trac/boost/ticket/6223 #6223], | |
3989 | [@https://svn.boost.org/trac/boost/ticket/6153 #6153]. | |
3990 | ||
3991 | ||
3992 | [endsect] | |
3993 | ||
3994 | [section:release_notes_boost_1_48_00 Boost 1.48 Release] | |
3995 | ||
3996 | * Fixed bugs | |
3997 | [@https://svn.boost.org/trac/boost/ticket/4797 #4797], | |
3998 | [@https://svn.boost.org/trac/boost/ticket/5165 #5165], | |
3999 | [@https://svn.boost.org/trac/boost/ticket/5183 #5183], | |
4000 | [@https://svn.boost.org/trac/boost/ticket/5191 #5191]. | |
4001 | ||
4002 | [endsect] | |
4003 | ||
4004 | [section:release_notes_boost_1_46_00 Boost 1.46 Release] | |
4005 | ||
4006 | * Fixed bug | |
4007 | [@https://svn.boost.org/trac/boost/ticket/4980 #4980], | |
4008 | ||
4009 | [endsect] | |
4010 | ||
4011 | [section:release_notes_boost_1_45_00 Boost 1.45 Release] | |
4012 | ||
4013 | * Added `function_hook` option. | |
4014 | * Fixed bugs | |
4015 | [@https://svn.boost.org/trac/boost/ticket/2611 #2611], | |
4016 | [@https://svn.boost.org/trac/boost/ticket/3288 #3288], | |
4017 | [@https://svn.boost.org/trac/boost/ticket/3304 #3304], | |
4018 | [@https://svn.boost.org/trac/boost/ticket/3489 #3489], | |
4019 | [@https://svn.boost.org/trac/boost/ticket/3668 #3668], | |
4020 | [@https://svn.boost.org/trac/boost/ticket/3339 #3688], | |
4021 | [@https://svn.boost.org/trac/boost/ticket/3698 #3698], | |
4022 | [@https://svn.boost.org/trac/boost/ticket/3706 #3706], | |
4023 | [@https://svn.boost.org/trac/boost/ticket/3721 #3721]. | |
4024 | [@https://svn.boost.org/trac/boost/ticket/3729 #3729], | |
4025 | [@https://svn.boost.org/trac/boost/ticket/3746 #3746], | |
4026 | [@https://svn.boost.org/trac/boost/ticket/3781 #3781], | |
4027 | [@https://svn.boost.org/trac/boost/ticket/3840 #3840], | |
4028 | [@https://svn.boost.org/trac/boost/ticket/3849 #3849], | |
4029 | [@https://svn.boost.org/trac/boost/ticket/3339 #3339], | |
4030 | [@https://svn.boost.org/trac/boost/ticket/3419 #3419], | |
4031 | [@https://svn.boost.org/trac/boost/ticket/3431 #3431], | |
4032 | [@https://svn.boost.org/trac/boost/ticket/4021 #4021]. | |
4033 | ||
4034 | [endsect] | |
4035 | ||
4036 | ||
4037 | [section:release_notes_boost_1_40_00 Boost 1.40 Release] | |
4038 | ||
4039 | * Code cleanup in bstree_algorithms.hpp and avl_tree_algorithms.hpp | |
4040 | * Fixed bug | |
4041 | [@https://svn.boost.org/trac/boost/ticket/3164 #3164]. | |
4042 | ||
4043 | [endsect] | |
4044 | ||
4045 | ||
4046 | [section:release_notes_boost_1_39_00 Boost 1.39 Release] | |
4047 | ||
4048 | * Optimized `list::merge` and `slist::merge` | |
4049 | * `list::sort` and `slist::sort` are now stable. | |
4050 | * Fixed bugs | |
4051 | [@https://svn.boost.org/trac/boost/ticket/2689 #2689], | |
4052 | [@https://svn.boost.org/trac/boost/ticket/2755 #2755], | |
4053 | [@https://svn.boost.org/trac/boost/ticket/2786 #2786], | |
4054 | [@https://svn.boost.org/trac/boost/ticket/2807 #2807], | |
4055 | [@https://svn.boost.org/trac/boost/ticket/2810 #2810], | |
4056 | [@https://svn.boost.org/trac/boost/ticket/2862 #2862]. | |
4057 | ||
4058 | [endsect] | |
4059 | ||
4060 | [section:release_notes_boost_1_38_00 Boost 1.38 Release] | |
4061 | ||
4062 | * New treap-based containers: treap, treap_set, treap_multiset. | |
4063 | * Corrected compilation bug for Windows-based 64 bit compilers. | |
4064 | * Corrected exception-safety bugs in container constructors. | |
4065 | * Updated documentation to show rvalue-references functions instead of emulation functions. | |
4066 | ||
4067 | [endsect] | |
4068 | ||
4069 | [section:release_notes_boost_1_37_00 Boost 1.37 Release] | |
4070 | ||
4071 | * Intrusive now takes advantage of compilers with variadic templates. | |
4072 | * `clone_from` functions now copy predicates and hash functions of associative containers. | |
4073 | * Added incremental hashing to unordered containers via `incremental<>` option. | |
4074 | * Update some function parameters from `iterator` to `const_iterator` in containers | |
4075 | to keep up with the draft of the next standard. | |
4076 | * Added an option to specify include files for intrusive configurable assertion macros. | |
4077 | ||
4078 | [endsect] | |
4079 | ||
4080 | [section:release_notes_boost_1_36_00 Boost 1.36 Release] | |
4081 | ||
4082 | * Added `linear<>` and `cache_last<>` options to singly linked lists. | |
4083 | * Added `optimize_multikey<>` option to unordered container hooks. | |
4084 | * Optimized unordered containers when `store_hash` option is used in the hook. | |
4085 | * Implementation changed to be exception agnostic so that it can be used | |
4086 | in environments without exceptions. | |
4087 | * Added `container_from_iterator` function to tree-based containers. | |
4088 | ||
4089 | [endsect] | |
4090 | ||
4091 | [endsect] | |
4092 | ||
4093 | [section:tested_compilers Tested compilers] | |
4094 | ||
4095 | [*Boost.Intrusive] has been tested on the following compilers/platforms: | |
4096 | ||
4097 | * Visual >= 7.1 | |
4098 | * GCC >= 4.1 | |
4099 | * Intel 11 | |
4100 | ||
4101 | [endsect] | |
4102 | ||
4103 | [section:references References] | |
4104 | ||
4105 | * SGI's [@http://www.sgi.com/tech/stl/ STL Programmer's Guide]. | |
4106 | [*Boost.Intrusive] is based on STL concepts and interfaces. | |
4107 | ||
4108 | * Dr. Dobb's, September 1, 2005: [@http://www.ddj.com/architect/184402007 ['Implementing Splay Trees in C++] ]. | |
4109 | [*Boost.Intrusive] splay containers code is based on this article. | |
4110 | ||
4111 | * Olaf's original intrusive container library: [@http://freenet-homepage.de/turtle++/intrusive.html ['STL-like intrusive containers] ]. | |
4112 | ||
4113 | [endsect] | |
4114 | ||
4115 | [section:acknowledgements Acknowledgements] | |
4116 | ||
4117 | [*Olaf Krzikalla] would like to thank: | |
4118 | ||
4119 | * [*Markus Schaaf] for pointing out the possibility and the advantages of the derivation | |
4120 | approach. | |
4121 | ||
4122 | * [*Udo Steinbach] for encouragements to present this work for boost, a lot of fixes and | |
4123 | helpful discussions. | |
4124 | ||
4125 | * [*Jaap Suter] for the initial hint, which eventually lead to the member value_traits. | |
4126 | ||
4127 | [*Ion Gaztanaga] would like to thank: | |
4128 | ||
4129 | * [*Olaf Krzikalla] for the permission to continue his great work. | |
4130 | ||
4131 | * [*Joaquin M. Lopez Munoz] for his thorough review, help, and ideas. | |
4132 | ||
4133 | * [*Cory Nelson], [*Daniel James], [*Dave Harris], [*Guillaume Melquiond], | |
4134 | [*Henri Bavestrello], [*Hervé Bronnimann], [*Kai Bruning], [*Kevin Sopp], | |
4135 | [*Paul Rose], [*Pavel Vozelinek], [*Howard Hinnant], [*Olaf Krzikalla], | |
4136 | [*Samuel Debionne], [*Stjepan Rajko], [*Thorsten Ottosen], [*Tobias Schwinger], | |
4137 | [*Tom Brinkman] and [*Steven Watanabe] | |
4138 | for their comments and reviews in the Boost.Intrusive formal review. | |
4139 | ||
4140 | * Thanks to [*Julienne Walker] and [*The EC Team] ([@http://eternallyconfuzzled.com]) | |
4141 | for their great algorithms. | |
4142 | ||
4143 | * Thanks to [*Daniel K. O.] for his AVL tree rebalancing code. | |
4144 | ||
4145 | * Thanks to [*Ralf Mattethat] for his splay tree article and code. | |
4146 | ||
4147 | * Special thanks to [*Steven Watanabe] and [*Tobias Schwinger] for their | |
4148 | invaluable suggestions and improvements. | |
4149 | ||
4150 | [endsect] | |
4151 | ||
4152 | [include auto_index_helpers.qbk] | |
4153 | ||
4154 | [section:index Indexes] | |
4155 | ||
4156 | [named_index class_name Class Index] | |
4157 | [named_index typedef_name Typedef Index] | |
4158 | [named_index function_name Function Index] | |
4159 | [named_index macro_name Macro Index] | |
4160 | [/index] | |
4161 | ||
4162 | [endsect] | |
4163 | ||
4164 | [xinclude autodoc.xml] |