1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Presenting Boost.Intrusive containers</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive"> 10<link rel="prev" href="concepts_summary.html" title="Concept summary"> 11<link rel="next" href="safe_hook.html" title="Safe hooks"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="concepts_summary.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="safe_hook.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="intrusive.presenting_containers"></a><a class="link" href="presenting_containers.html" title="Presenting Boost.Intrusive containers">Presenting Boost.Intrusive 29 containers</a> 30</h2></div></div></div> 31<p> 32 <span class="bold"><strong>Boost.Intrusive</strong></span> offers a wide range of intrusive 33 containers: 34 </p> 35<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 36<li class="listitem"> 37 <span class="bold"><strong>slist</strong></span>: An intrusive singly linked list. 38 The size overhead is very small for user classes (usually the size of one 39 pointer) but many operations have linear time complexity, so the user must 40 be careful if he wants to avoid performance problems. 41 </li> 42<li class="listitem"> 43 <span class="bold"><strong>list</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code> 44 like intrusive linked list. The size overhead is quite small for user classes 45 (usually the size of two pointers). Many operations have constant time 46 complexity. 47 </li> 48<li class="listitem"> 49 <span class="bold"><strong>set/multiset/rbtree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> 50 like intrusive associative containers based on red-black trees. The size 51 overhead is moderate for user classes (usually the size of three pointers). 52 Many operations have logarithmic time complexity. 53 </li> 54<li class="listitem"> 55 <span class="bold"><strong>avl_set/avl_multiset/avltree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers 56 based on AVL trees. The size overhead is moderate for user classes (usually 57 the size of three pointers). Many operations have logarithmic time complexity. 58 </li> 59<li class="listitem"> 60 <span class="bold"><strong>splay_set/splay_multiset/splaytree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers 61 based on splay trees. Splay trees have no constant operations, but they 62 have some interesting caching properties. The size overhead is moderate 63 for user classes (usually the size of three pointers). Many operations 64 have logarithmic time complexity. 65 </li> 66<li class="listitem"> 67 <span class="bold"><strong>sg_set/sg_multiset/sgtree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers 68 based on scapegoat trees. Scapegoat can be configured with the desired 69 balance factor to achieve the desired rebalancing frequency/search time 70 compromise. The size overhead is moderate for user classes (usually the 71 size of three pointers). Many operations have logarithmic time complexity. 72 </li> 73</ul></div> 74<p> 75 <span class="bold"><strong>Boost.Intrusive</strong></span> also offers semi-intrusive 76 containers: 77 </p> 78<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 79 <span class="bold"><strong>unordered_set/unordered_multiset</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_multiset</span></code> like intrusive unordered 80 associative containers. The size overhead is moderate for user classes 81 (an average of two pointers per element). Many operations have amortized 82 constant time complexity. 83 </li></ul></div> 84<p> 85 Most of these intrusive containers can be configured with constant or linear 86 time size: 87 </p> 88<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 89<li class="listitem"> 90 <span class="bold"><strong>Linear time size</strong></span>: The intrusive container 91 doesn't hold a size member that is updated with every insertion/erasure. 92 This implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> function doesn't have constant time complexity. 93 On the other hand, the container is smaller, and some operations, like 94 <code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code> 95 taking a range of iterators in linked lists, have constant time complexity 96 instead of linear complexity. 97 </li> 98<li class="listitem"> 99 <span class="bold"><strong>Constant time size</strong></span>: The intrusive container 100 holds a size member that is updated with every insertion/erasure. This 101 implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> 102 function has constant time complexity. On the other hand, increases the 103 size of the container, and some operations, like <code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code> taking a range of iterators, have linear 104 time complexity in linked lists. 105 </li> 106</ul></div> 107<p> 108 To make user classes compatible with these intrusive containers <span class="bold"><strong>Boost.Intrusive</strong></span> 109 offers two types of hooks for each container type: 110 </p> 111<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 112<li class="listitem"> 113 <span class="bold"><strong>Base hook</strong></span>: The hook is stored as a public 114 base class of the user class. 115 </li> 116<li class="listitem"> 117 <span class="bold"><strong>Member hook</strong></span>: The hook is stored as a public 118 member of the user class. 119 </li> 120</ul></div> 121<p> 122 Apart from that, <span class="bold"><strong>Boost.Intrusive</strong></span> offers additional 123 features: 124 </p> 125<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 126<li class="listitem"> 127 <span class="bold"><strong>Safe mode hooks</strong></span>: Hook constructor initializes 128 the internal <code class="computeroutput"><span class="identifier">node</span></code> to a 129 well-known safe state and intrusive containers check that state before 130 inserting a value in the container using that hook. When erasing an element 131 from the container, the container puts the <code class="computeroutput"><span class="identifier">node</span></code> 132 of the hook in the safe state again. This allows a safer use mode and it 133 can be used to detect programming errors. It implies a slight performance 134 overhead in some operations and can convert some constant time operations 135 to linear time operations. 136 </li> 137<li class="listitem"> 138 <span class="bold"><strong>Auto-unlink hooks</strong></span>: The hook destructor 139 removes the object from the container automatically and the user can safely 140 unlink the object from the container without referring to the container. 141 </li> 142<li class="listitem"> 143 <span class="bold"><strong>Non-raw pointers</strong></span>: If the user wants to 144 use smart pointers instead of raw pointers, <span class="bold"><strong>Boost.Intrusive</strong></span> 145 hooks can be configured to use any type of pointer. This configuration 146 information is also transmitted to the containers, so all the internal 147 pointers used by intrusive containers configured with these hooks will 148 be smart pointers. As an example, <span class="bold"><strong>Boost.Interprocess</strong></span> 149 defines a smart pointer compatible with shared memory, called <code class="computeroutput"><span class="identifier">offset_ptr</span></code>. <span class="bold"><strong>Boost.Intrusive</strong></span> 150 can be configured to use this smart pointer to allow shared memory intrusive 151 containers. 152 </li> 153</ul></div> 154</div> 155<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 156<td align="left"></td> 157<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 158 Distributed under the Boost Software License, Version 1.0. (See accompanying 159 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 160 </p> 161</div></td> 162</tr></table> 163<hr> 164<div class="spirit-nav"> 165<a accesskey="p" href="concepts_summary.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="safe_hook.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 166</div> 167</body> 168</html> 169
