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>Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset</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="set_multiset.html" title="Intrusive associative containers: set, multiset, rbtree"> 11<link rel="next" href="map_multimap.html" title="Map and multimap-like interface for associative containers"> 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="set_multiset.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="map_multimap.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.unordered_set_unordered_multiset"></a><a class="link" href="unordered_set_unordered_multiset.html" title="Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset">Semi-Intrusive 29 unordered associative containers: unordered_set, unordered_multiset</a> 30</h2></div></div></div> 31<div class="toc"><dl class="toc"> 32<dt><span class="section"><a href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_performance">unordered_set 33 and unordered_multiset performance notes</a></span></dt> 34<dt><span class="section"><a href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_hooks">unordered_set 35 and unordered_multiset hooks</a></span></dt> 36<dt><span class="section"><a href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_containers">unordered_set 37 and unordered_multiset containers</a></span></dt> 38<dt><span class="section"><a href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_example">Example</a></span></dt> 39<dt><span class="section"><a href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.custom_bucket_traits">Custom 40 bucket traits</a></span></dt> 41</dl></div> 42<p> 43 <span class="bold"><strong>Boost.Intrusive</strong></span> also offers hashed containers 44 that can be very useful to implement fast-lookup containers. These containers 45 (<code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code> 46 and <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code>) 47 are semi-intrusive containers: they need additional memory apart from the hook 48 stored in the <code class="computeroutput"><span class="identifier">value_type</span></code>. This 49 additional memory must be passed in the constructor of the container. 50 </p> 51<p> 52 Unlike C++ TR1 unordered associative containers (which are also hashed containers), 53 the contents of these semi-intrusive containers are not rehashed to maintain 54 a load factor: that would require memory management and intrusive containers 55 don't implement any memory management at all. However, the user can request 56 an explicit rehashing passing a new bucket array. This also offers an additional 57 guarantee over TR1 unordered associative containers: <span class="bold"><strong>iterators 58 are not invalidated when inserting an element</strong></span> in the container. 59 </p> 60<p> 61 As with TR1 unordered associative containers, rehashing invalidates iterators, 62 changes ordering between elements and changes which buckets elements appear 63 in, but does not invalidate pointers or references to elements. 64 </p> 65<p> 66 Apart from expected hash and equality function objects, <span class="bold"><strong>Boost.Intrusive</strong></span> 67 unordered associative containers' constructors take an argument specifying 68 an auxiliary bucket vector to be used by the container. 69 </p> 70<div class="section"> 71<div class="titlepage"><div><div><h3 class="title"> 72<a name="intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_performance"></a><a class="link" href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_performance" title="unordered_set and unordered_multiset performance notes">unordered_set 73 and unordered_multiset performance notes</a> 74</h3></div></div></div> 75<p> 76 The size overhead for a hashed container is moderate: 1 pointer per value 77 plus a bucket array per container. The size of an element of the bucket array 78 is usually one pointer. To obtain a good performance hashed container, the 79 bucket length is usually the same as the number of elements that the container 80 contains, so a well-balanced hashed container (<code class="computeroutput"><span class="identifier">bucket_count</span><span class="special">()</span></code> is equal to <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> ) will have an equivalent overhead of two 81 pointers per element. 82 </p> 83<p> 84 An empty, non constant-time size <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code> 85 or <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code> 86 has also the size of <code class="computeroutput"><span class="identifier">bucket_count</span><span class="special">()</span></code> pointers. 87 </p> 88<p> 89 Insertions, erasures, and searches, have amortized constant-time complexity 90 in hashed containers. However, some worst-case guarantees are linear. See 91 <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code> 92 or <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code> 93 for complexity guarantees of each operation. 94 </p> 95<p> 96 <span class="bold"><strong>Be careful with non constant-time size hashed containers</strong></span>: 97 some operations, like <code class="computeroutput"><span class="identifier">empty</span><span class="special">()</span></code>, have linear complexity, unlike other 98 <span class="bold"><strong>Boost.Intrusive</strong></span> containers. 99 </p> 100</div> 101<div class="section"> 102<div class="titlepage"><div><div><h3 class="title"> 103<a name="intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_hooks"></a><a class="link" href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_hooks" title="unordered_set and unordered_multiset hooks">unordered_set 104 and unordered_multiset hooks</a> 105</h3></div></div></div> 106<p> 107 <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code> 108 and <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code> 109 share the same hooks. This is an advantage, because the same user type can 110 be inserted first in a <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code> 111 and after that in <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code> 112 without changing the definition of the user class. 113 </p> 114<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 115<span class="keyword">class</span> <span class="identifier">unordered_set_base_hook</span><span class="special">;</span> 116</pre> 117<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 118 <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set_base_hook.html" title="Class template unordered_set_base_hook">unordered_set_base_hook</a></code>: 119 the user class derives publicly from <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set_base_hook.html" title="Class template unordered_set_base_hook">unordered_set_base_hook</a></code> 120 to make it <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code>/<code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code>-compatible. 121 </li></ul></div> 122<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 123<span class="keyword">class</span> <span class="identifier">unordered_set_member_hook</span><span class="special">;</span> 124</pre> 125<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 126 <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set_member_hook.html" title="Class template unordered_set_member_hook">unordered_set_member_hook</a></code>: 127 the user class contains a public <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set_member_hook.html" title="Class template unordered_set_member_hook">unordered_set_member_hook</a></code> 128 to make it <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code>/<code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code>-compatible. 129 </li></ul></div> 130<p> 131 <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set_base_hook.html" title="Class template unordered_set_base_hook">unordered_set_base_hook</a></code> 132 and <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set_member_hook.html" title="Class template unordered_set_member_hook">unordered_set_member_hook</a></code> 133 receive the same options explained in the section <a class="link" href="usage.html" title="How to use Boost.Intrusive">How 134 to use Boost.Intrusive</a>: 135 </p> 136<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 137<li class="listitem"> 138 <span class="bold"><strong><code class="computeroutput"><span class="identifier">tag</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Tag</span><span class="special">></span></code></strong></span> 139 (for base hooks only): This argument serves as a tag, so you can derive 140 from more than one base hook. Default: <code class="computeroutput"><span class="identifier">tag</span><span class="special"><</span><span class="identifier">default_tag</span><span class="special">></span></code>. 141 </li> 142<li class="listitem"> 143 <span class="bold"><strong><code class="computeroutput"><span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">link_mode_type</span> 144 <span class="identifier">LinkMode</span><span class="special">></span></code></strong></span>: 145 The linking policy. Default: <code class="computeroutput"><span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">safe_link</span><span class="special">></span></code>. 146 </li> 147<li class="listitem"> 148 <span class="bold"><strong><code class="computeroutput"><span class="identifier">void_pointer</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">VoidPointer</span><span class="special">></span></code></strong></span>: 149 The pointer type to be used internally in the hook and propagated to 150 the container. Default: <code class="computeroutput"><span class="identifier">void_pointer</span><span class="special"><</span><span class="keyword">void</span><span class="special">*></span></code>. 151 </li> 152</ul></div> 153<p> 154 Apart from them, these hooks offer additional options: 155 </p> 156<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 157<li class="listitem"> 158 <span class="bold"><strong><code class="computeroutput"><span class="identifier">store_hash</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 159 This option reserves additional space in the hook to store the hash value 160 of the object once it's introduced in the container. When this option 161 is used, the unordered container will store the calculated hash value 162 in the hook and rehashing operations won't need to recalculate the hash 163 of the value. This option will improve the performance of unordered containers 164 when rehashing is frequent or hashing the value is a slow operation. 165 Default: <code class="computeroutput"><span class="identifier">store_hash</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span></code>. 166 </li> 167<li class="listitem"> 168 <span class="bold"><strong><code class="computeroutput"><span class="identifier">optimize_multikey</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 169 This option reserves additional space in the hook that will be used to 170 group equal elements in unordered multisets, improving significantly 171 the performance when many equal values are inserted in these containers. 172 Default: <code class="computeroutput"><span class="identifier">optimize_multikey</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span></code>. 173 </li> 174</ul></div> 175</div> 176<div class="section"> 177<div class="titlepage"><div><div><h3 class="title"> 178<a name="intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_containers"></a><a class="link" href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_containers" title="unordered_set and unordered_multiset containers">unordered_set 179 and unordered_multiset containers</a> 180</h3></div></div></div> 181<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 182<span class="keyword">class</span> <span class="identifier">unordered_set</span><span class="special">;</span> 183 184<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 185<span class="keyword">class</span> <span class="identifier">unordered_multiset</span><span class="special">;</span> 186</pre> 187<p> 188 As mentioned, unordered containers need an auxiliary array to work. <span class="bold"><strong>Boost.Intrusive</strong></span> unordered containers receive this 189 auxiliary array packed in a type called <code class="computeroutput"><span class="identifier">bucket_traits</span></code> 190 (which can be also customized by a container option). All unordered containers 191 receive a <code class="computeroutput"><span class="identifier">bucket_traits</span></code> object 192 in their constructors. The default <code class="computeroutput"><span class="identifier">bucket_traits</span></code> 193 class is initialized with a pointer to an array of buckets and its size: 194 </p> 195<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">unordered_set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 196 197<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span> 198 199<span class="keyword">struct</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">unordered_set_base_hook</span><span class="special"><></span> 200<span class="special">{};</span> 201 202<span class="keyword">typedef</span> <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">>::</span><span class="identifier">bucket_type</span> <span class="identifier">bucket_type</span><span class="special">;</span> 203<span class="keyword">typedef</span> <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">>::</span><span class="identifier">bucket_traits</span> <span class="identifier">bucket_traits</span><span class="special">;</span> 204 205<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 206<span class="special">{</span> 207 <span class="identifier">bucket_type</span> <span class="identifier">buckets</span><span class="special">[</span><span class="number">100</span><span class="special">];</span> 208 <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">uset</span><span class="special">(</span><span class="identifier">bucket_traits</span><span class="special">(</span><span class="identifier">buckets</span><span class="special">,</span> <span class="number">100</span><span class="special">));</span> 209 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 210<span class="special">}</span> 211</pre> 212<p> 213 Each hashed container needs <span class="bold"><strong>its own bucket traits</strong></span>, 214 that is, <span class="bold"><strong>its own bucket vector</strong></span>. Two hashed 215 containers <span class="bold"><strong>can't</strong></span> share the same <code class="computeroutput"><span class="identifier">bucket_type</span></code> elements. The bucket array 216 <span class="bold"><strong>must</strong></span> be destroyed <span class="bold"><strong>after</strong></span> 217 the container using it is destroyed, otherwise, the result is undefined. 218 </p> 219<p> 220 <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code> 221 and <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code> 222 receive the same options explained in the section <a class="link" href="usage.html" title="How to use Boost.Intrusive">How 223 to use Boost.Intrusive</a>: 224 </p> 225<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 226<li class="listitem"> 227 <span class="bold"><strong><code class="computeroutput"><span class="identifier">base_hook</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Hook</span><span class="special">></span></code></strong></span> 228 / <span class="bold"><strong><code class="computeroutput"><span class="identifier">member_hook</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hook</span><span class="special">,</span> <span class="identifier">Hook</span> <span class="identifier">T</span><span class="special">::*</span> <span class="identifier">PtrToMember</span><span class="special">></span></code></strong></span> 229 / <span class="bold"><strong><code class="computeroutput"><span class="identifier">value_traits</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">ValueTraits</span><span class="special">></span></code></strong></span>: 230 To specify the hook type or value traits used to configure the container. 231 (To learn about value traits go to the section <a class="link" href="value_traits.html" title="Containers with custom ValueTraits">Containers 232 with custom ValueTraits</a>.) 233 </li> 234<li class="listitem"> 235 <span class="bold"><strong><code class="computeroutput"><span class="identifier">constant_time_size</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 236 To activate the constant-time <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> operation. Default: <code class="computeroutput"><span class="identifier">constant_time_size</span><span class="special"><</span><span class="keyword">true</span><span class="special">></span></code> 237 </li> 238<li class="listitem"> 239 <span class="bold"><strong><code class="computeroutput"><span class="identifier">size_type</span><span class="special"><</span><span class="keyword">typename</span> 240 <span class="identifier">SizeType</span><span class="special">></span></code></strong></span>: 241 To specify the type that will be used to store the size of the container. 242 Default: <code class="computeroutput"><span class="identifier">size_type</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span><span class="special">></span></code> 243 </li> 244</ul></div> 245<p> 246 And they also can receive additional options: 247 </p> 248<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 249<li class="listitem"> 250 <span class="bold"><strong><code class="computeroutput"><span class="identifier">equal</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Equal</span><span class="special">></span></code></strong></span>: 251 Equality function for the objects to be inserted in containers. Default: 252 <code class="computeroutput"><span class="identifier">equal</span><span class="special"><</span> 253 <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span> <span class="special">></span></code> 254 </li> 255<li class="listitem"> 256 <span class="bold"><strong><code class="computeroutput"><span class="identifier">hash</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Hash</span><span class="special">></span></code></strong></span>: 257 Hash function to be used in the container. Default: <code class="computeroutput"><span class="identifier">hash</span><span class="special"><</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span> <span class="special">></span></code> 258 </li> 259<li class="listitem"> 260 <span class="bold"><strong><code class="computeroutput"><span class="identifier">bucket_traits</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">BucketTraits</span><span class="special">></span></code></strong></span>: 261 A type that wraps the bucket vector to be used by the unordered container. 262 Default: a type initialized by the address and size of a bucket array 263 and stores both variables internally. 264 </li> 265<li class="listitem"> 266 <span class="bold"><strong><code class="computeroutput"><span class="identifier">power_2_buckets</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 267 The user guarantees that only bucket arrays with power of two length 268 will be used. The container will then use masks instead of modulo operations 269 to obtain the bucket number from the hash value. Masks are faster than 270 modulo operations and for some applications modulo operations can impose 271 a considerable overhead. In debug mode an assertion will be raised if 272 the user provides a bucket length that is not power of two. Default: 273 <code class="computeroutput"><span class="identifier">power_2_buckets</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span></code>. 274 </li> 275<li class="listitem"> 276 <span class="bold"><strong><code class="computeroutput"><span class="identifier">cache_begin</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 277 <span class="bold"><strong>Note: this option is not compatible with <code class="computeroutput"><span class="identifier">auto_unlink</span></code> hooks</strong></span>. Due to 278 its internal structure, finding the first element of an unordered container 279 (<code class="computeroutput"><span class="identifier">begin</span><span class="special">()</span></code> 280 operation) is amortized constant-time. It's possible to speed up <code class="computeroutput"><span class="identifier">begin</span><span class="special">()</span></code> 281 and other operations related to it (like <code class="computeroutput"><span class="identifier">clear</span><span class="special">()</span></code>) if the container caches internally 282 the position of the first element. This imposes the overhead of one pointer 283 to the size of the container. Default: <code class="computeroutput"><span class="identifier">cache_begin</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span></code>. 284 </li> 285<li class="listitem"> 286 <span class="bold"><strong><code class="computeroutput"><span class="identifier">compare_hash</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 287 <span class="bold"><strong>Note: this option requires <code class="computeroutput"><span class="identifier">store_hash</span><span class="special"><</span><span class="keyword">true</span><span class="special">></span></code> option in the hook</strong></span>. When 288 the comparison function is expensive, (e.g. strings with a long common 289 predicate) sometimes (specially when the load factor is high or we have 290 many equivalent elements in an <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code> 291 and no <code class="computeroutput"><span class="identifier">optimize_multikey</span><span class="special"><></span></code> is activated in the hook) the 292 equality function is a performance problem. Two equal values must have 293 equal hashes, so comparing the hash values of two elements before using 294 the comparison functor can speed up some implementations. 295 </li> 296<li class="listitem"> 297 <span class="bold"><strong><code class="computeroutput"><span class="identifier">incremental</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 298 Activates incremental hashing (also known as Linear Hashing). This option 299 implies <code class="computeroutput"><span class="identifier">power_2_buckets</span><span class="special"><</span><span class="keyword">true</span><span class="special">></span></code> and the container will require power 300 of two buckets. For more information on incremental hashing, see <a href="http://en.wikipedia.org/wiki/Linear_hashing" target="_top"><code class="computeroutput"><span class="identifier">Linear</span> 301 <span class="identifier">hash</span></code> on Wikipedia</a> Default: 302 <code class="computeroutput"><span class="identifier">incremental</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span></code> 303 </li> 304<li class="listitem"> 305 <span class="bold"><strong><code class="computeroutput"><span class="identifier">key_of_value</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">KeyOfValueFunctionObject</span><span class="special">></span></code></strong></span>: 306 A function object that will define the <code class="computeroutput"><span class="identifier">key_type</span></code> 307 of the value type to be stored. This type will allow a map-like interface. 308 See <a class="link" href="map_multimap.html" title="Map and multimap-like interface for associative containers">Map and multimap-like interface 309 with set and multiset</a> for details. Default: <code class="computeroutput"><span class="identifier">key_type</span></code> 310 is equal to <code class="computeroutput"><span class="identifier">value_type</span></code> 311 (set-like interface). 312 </li> 313</ul></div> 314</div> 315<div class="section"> 316<div class="titlepage"><div><div><h3 class="title"> 317<a name="intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_example"></a><a class="link" href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.unordered_set_unordered_multiset_example" title="Example">Example</a> 318</h3></div></div></div> 319<p> 320 Now let's see a small example using both hooks and both containers: 321 </p> 322<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">unordered_set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 323<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 324<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">functional</span><span class="special">></span> 325<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">functional</span><span class="special">/</span><span class="identifier">hash</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 326 327<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span> 328 329<span class="keyword">class</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">unordered_set_base_hook</span><span class="special"><></span> 330<span class="special">{</span> <span class="comment">//This is a derivation hook</span> 331 <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span> 332 333 <span class="keyword">public</span><span class="special">:</span> 334 <span class="identifier">unordered_set_member_hook</span><span class="special"><></span> <span class="identifier">member_hook_</span><span class="special">;</span> <span class="comment">//This is a member hook</span> 335 336 <span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> 337 <span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 338 <span class="special">{}</span> 339 340 <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">b</span><span class="special">)</span> 341 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">a</span><span class="special">.</span><span class="identifier">int_</span> <span class="special">==</span> <span class="identifier">b</span><span class="special">.</span><span class="identifier">int_</span><span class="special">;</span> <span class="special">}</span> 342 343 <span class="keyword">friend</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">hash_value</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">value</span><span class="special">)</span> 344 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span><span class="special">(</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">int_</span><span class="special">);</span> <span class="special">}</span> 345<span class="special">};</span> 346 347<span class="comment">//Define an unordered_set that will store MyClass objects using the base hook</span> 348<span class="keyword">typedef</span> <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">BaseSet</span><span class="special">;</span> 349 350<span class="comment">//Define an unordered_multiset that will store MyClass using the member hook</span> 351<span class="keyword">typedef</span> <span class="identifier">member_hook</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">unordered_set_member_hook</span><span class="special"><>,</span> <span class="special">&</span><span class="identifier">MyClass</span><span class="special">::</span><span class="identifier">member_hook_</span><span class="special">></span> 352 <span class="identifier">MemberOption</span><span class="special">;</span> 353<span class="keyword">typedef</span> <span class="identifier">unordered_multiset</span><span class="special"><</span> <span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">MemberOption</span><span class="special">></span> <span class="identifier">MemberMultiSet</span><span class="special">;</span> 354 355<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 356<span class="special">{</span> 357 <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">VectIt</span><span class="special">;</span> 358 359 <span class="comment">//Create a vector with 100 different MyClass objects</span> 360 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">values</span><span class="special">;</span> 361 <span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="number">100</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="identifier">values</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">MyClass</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span> 362 363 <span class="comment">//Create a copy of the vector</span> 364 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">values2</span><span class="special">(</span><span class="identifier">values</span><span class="special">);</span> 365 366 <span class="comment">//Create a bucket array for base_set</span> 367 <span class="identifier">BaseSet</span><span class="special">::</span><span class="identifier">bucket_type</span> <span class="identifier">base_buckets</span><span class="special">[</span><span class="number">100</span><span class="special">];</span> 368 369 <span class="comment">//Create a bucket array for member_multi_set</span> 370 <span class="identifier">MemberMultiSet</span><span class="special">::</span><span class="identifier">bucket_type</span> <span class="identifier">member_buckets</span><span class="special">[</span><span class="number">200</span><span class="special">];</span> 371 372 <span class="comment">//Create unordered containers taking buckets as arguments</span> 373 <span class="identifier">BaseSet</span> <span class="identifier">base_set</span><span class="special">(</span><span class="identifier">BaseSet</span><span class="special">::</span><span class="identifier">bucket_traits</span><span class="special">(</span><span class="identifier">base_buckets</span><span class="special">,</span> <span class="number">100</span><span class="special">));</span> 374 <span class="identifier">MemberMultiSet</span> <span class="identifier">member_multi_set</span> 375 <span class="special">(</span><span class="identifier">MemberMultiSet</span><span class="special">::</span><span class="identifier">bucket_traits</span><span class="special">(</span><span class="identifier">member_buckets</span><span class="special">,</span> <span class="number">200</span><span class="special">));</span> 376 377 <span class="comment">//Now insert values's elements in the unordered_set</span> 378 <span class="keyword">for</span><span class="special">(</span><span class="identifier">VectIt</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> 379 <span class="identifier">base_set</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span> 380 381 <span class="comment">//Now insert values's and values2's elements in the unordered_multiset</span> 382 <span class="keyword">for</span><span class="special">(</span><span class="identifier">VectIt</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">()),</span> <span class="identifier">it2</span><span class="special">(</span><span class="identifier">values2</span><span class="special">.</span><span class="identifier">begin</span><span class="special">())</span> 383 <span class="special">;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">,</span> <span class="special">++</span><span class="identifier">it2</span><span class="special">){</span> 384 <span class="identifier">member_multi_set</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span> 385 <span class="identifier">member_multi_set</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">it2</span><span class="special">);</span> 386 <span class="special">}</span> 387 388 <span class="comment">//Now find every element</span> 389 <span class="special">{</span> 390 <span class="identifier">VectIt</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> 391 392 <span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">){</span> 393 <span class="comment">//base_set should contain one element for each key</span> 394 <span class="keyword">if</span><span class="special">(</span><span class="identifier">base_set</span><span class="special">.</span><span class="identifier">count</span><span class="special">(*</span><span class="identifier">it</span><span class="special">)</span> <span class="special">!=</span> <span class="number">1</span><span class="special">)</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span> 395 <span class="comment">//member_multi_set should contain two elements for each key</span> 396 <span class="keyword">if</span><span class="special">(</span><span class="identifier">member_multi_set</span><span class="special">.</span><span class="identifier">count</span><span class="special">(*</span><span class="identifier">it</span><span class="special">)</span> <span class="special">!=</span> <span class="number">2</span><span class="special">)</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span> 397 <span class="special">}</span> 398 <span class="special">}</span> 399 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 400<span class="special">}</span> 401</pre> 402</div> 403<div class="section"> 404<div class="titlepage"><div><div><h3 class="title"> 405<a name="intrusive.unordered_set_unordered_multiset.custom_bucket_traits"></a><a class="link" href="unordered_set_unordered_multiset.html#intrusive.unordered_set_unordered_multiset.custom_bucket_traits" title="Custom bucket traits">Custom 406 bucket traits</a> 407</h3></div></div></div> 408<p> 409 Instead of using the default <code class="computeroutput"><span class="identifier">bucket_traits</span></code> 410 class to store the bucket array, a user can define his own class to store 411 the bucket array using the <span class="bold"><strong><span class="emphasis"><em>bucket_traits<></em></span></strong></span> 412 option. A user-defined bucket-traits must fulfill the following interface: 413 </p> 414<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">my_bucket_traits</span> 415<span class="special">{</span> 416 <span class="identifier">bucket_ptr</span> <span class="identifier">bucket_begin</span><span class="special">();</span> 417 <span class="identifier">const_bucket_ptr</span> <span class="identifier">bucket_begin</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> 418 <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">bucket_count</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> 419<span class="special">};</span> 420</pre> 421<p> 422 The following bucket traits just stores a pointer to the bucket array but 423 the size is a compile-time constant. Note the use of the auxiliary <code class="computeroutput">unordered_bucket</code> and 424 <code class="computeroutput">unordered_bucket_ptr</code> 425 utilities to obtain the type of the bucket and its pointer before defining 426 the unordered container: 427 </p> 428<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">unordered_set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 429<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">functional</span><span class="special">/</span><span class="identifier">hash</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 430<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 431 432<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span> 433 434<span class="comment">//A class to be inserted in an unordered_set</span> 435<span class="keyword">class</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">unordered_set_base_hook</span><span class="special"><></span> 436<span class="special">{</span> 437 <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span> 438 439 <span class="keyword">public</span><span class="special">:</span> 440 <span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 441 <span class="special">{}</span> 442 443 <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span><span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">l</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">r</span><span class="special">)</span> 444 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">l</span><span class="special">.</span><span class="identifier">int_</span> <span class="special">==</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">int_</span><span class="special">;</span> <span class="special">}</span> 445 <span class="keyword">friend</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">hash_value</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">v</span><span class="special">)</span> 446 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash_value</span><span class="special">(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">int_</span><span class="special">);</span> <span class="special">}</span> 447<span class="special">};</span> 448 449<span class="comment">//Define the base hook option</span> 450<span class="keyword">typedef</span> <span class="identifier">base_hook</span><span class="special"><</span> <span class="identifier">unordered_set_base_hook</span><span class="special"><></span> <span class="special">></span> <span class="identifier">BaseHookOption</span><span class="special">;</span> 451 452<span class="comment">//Obtain the types of the bucket and the bucket pointer</span> 453<span class="keyword">typedef</span> <span class="identifier">unordered_bucket</span><span class="special"><</span><span class="identifier">BaseHookOption</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">BucketType</span><span class="special">;</span> 454<span class="keyword">typedef</span> <span class="identifier">unordered_bucket_ptr</span><span class="special"><</span><span class="identifier">BaseHookOption</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">BucketPtr</span><span class="special">;</span> 455 456<span class="comment">//The custom bucket traits.</span> 457<span class="keyword">class</span> <span class="identifier">custom_bucket_traits</span> 458<span class="special">{</span> 459 <span class="keyword">public</span><span class="special">:</span> 460 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">NumBuckets</span> <span class="special">=</span> <span class="number">100</span><span class="special">;</span> 461 462 <span class="identifier">custom_bucket_traits</span><span class="special">(</span><span class="identifier">BucketPtr</span> <span class="identifier">buckets</span><span class="special">)</span> 463 <span class="special">:</span> <span class="identifier">buckets_</span><span class="special">(</span><span class="identifier">buckets</span><span class="special">)</span> 464 <span class="special">{}</span> 465 466 <span class="comment">//Functions to be implemented by custom bucket traits</span> 467 <span class="identifier">BucketPtr</span> <span class="identifier">bucket_begin</span><span class="special">()</span> <span class="keyword">const</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">buckets_</span><span class="special">;</span> <span class="special">}</span> 468 <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">bucket_count</span><span class="special">()</span> <span class="keyword">const</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">NumBuckets</span><span class="special">;}</span> 469 470 <span class="keyword">private</span><span class="special">:</span> 471 <span class="identifier">BucketPtr</span> <span class="identifier">buckets_</span><span class="special">;</span> 472<span class="special">};</span> 473 474<span class="comment">//Define the container using the custom bucket traits</span> 475<span class="keyword">typedef</span> <span class="identifier">unordered_set</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">bucket_traits</span><span class="special"><</span><span class="identifier">custom_bucket_traits</span><span class="special">></span> <span class="special">></span> <span class="identifier">BucketTraitsUset</span><span class="special">;</span> 476 477<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 478<span class="special">{</span> 479 <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">VectIt</span><span class="special">;</span> 480 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">values</span><span class="special">;</span> 481 482 <span class="comment">//Fill values</span> 483 <span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="number">100</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="identifier">values</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">MyClass</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span> 484 485 <span class="comment">//Now create the bucket array and the custom bucket traits object</span> 486 <span class="identifier">BucketType</span> <span class="identifier">buckets</span><span class="special">[</span><span class="identifier">custom_bucket_traits</span><span class="special">::</span><span class="identifier">NumBuckets</span><span class="special">];</span> 487 <span class="identifier">custom_bucket_traits</span> <span class="identifier">btraits</span><span class="special">(</span><span class="identifier">buckets</span><span class="special">);</span> 488 489 <span class="comment">//Now create the unordered set</span> 490 <span class="identifier">BucketTraitsUset</span> <span class="identifier">uset</span><span class="special">(</span><span class="identifier">btraits</span><span class="special">);</span> 491 492 <span class="comment">//Insert the values in the unordered set</span> 493 <span class="keyword">for</span><span class="special">(</span><span class="identifier">VectIt</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> 494 <span class="identifier">uset</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span> 495 496 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 497<span class="special">}</span> 498</pre> 499</div> 500</div> 501<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 502<td align="left"></td> 503<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 504 Distributed under the Boost Software License, Version 1.0. (See accompanying 505 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>) 506 </p> 507</div></td> 508</tr></table> 509<hr> 510<div class="spirit-nav"> 511<a accesskey="p" href="set_multiset.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="map_multimap.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 512</div> 513</body> 514</html> 515
