doc/html/intrusive/unordered_set_unordered_multiset.html

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