doc/html/intrusive/splay_set_multiset.html

   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=US-ASCII">
   5 <title>Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree</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&#160;19.&#160;Boost.Intrusive">
  10 <link rel="prev" href="avl_set_multiset.html" title="Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree">
  11 <link rel="next" href="sg_set_multiset.html" title="Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree">
  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="avl_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="sg_set_multiset.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.splay_set_multiset"></a><a class="link" href="splay_set_multiset.html" title="Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree">Intrusive splay tree based
  29     associative containers: splay_set, splay_multiset and , splay_tree</a>
  30 </h2></div></div></div>
  31 <div class="toc"><dl class="toc">
  32 <dt><span class="section"><a href="splay_set_multiset.html#intrusive.splay_set_multiset.splay_set_multiset_disadvantages">Advantages
  33       and disadvantages of splay tree based containers</a></span></dt>
  34 <dt><span class="section"><a href="splay_set_multiset.html#intrusive.splay_set_multiset.set_multiset_containers">splay_set,
  35       splay_multiset and splaytree containers</a></span></dt>
  36 <dt><span class="section"><a href="splay_set_multiset.html#intrusive.splay_set_multiset.splay_set_multiset_example">Example</a></span></dt>
  37 </dl></div>
  38 <p>
  39       C++ associative containers are usually based on red-black tree implementations
  40       (e.g.: STL, Boost.Intrusive associative containers). However, there are other
  41       interesting data structures that offer some advantages (and also disadvantages).
  42     </p>
  43 <p>
  44       Splay trees are self-adjusting binary search trees used typically in caches,
  45       memory allocators and other applications, because splay trees have a "caching
  46       effect": recently accessed elements have better access times than elements
  47       accessed less frequently. For more information on splay trees see <a href="http://en.wikipedia.org/wiki/Splay_tree" target="_top">the
  48       corresponding Wikipedia entry</a>.
  49     </p>
  50 <p>
  51       <span class="bold"><strong>Boost.Intrusive</strong></span> offers 3 containers based
  52       on splay trees: <code class="computeroutput"><a class="link" href="../boost/intrusive/splay_set.html" title="Class template splay_set">splay_set</a></code>,
  53       <code class="computeroutput"><a class="link" href="../boost/intrusive/splay_multiset.html" title="Class template splay_multiset">splay_multiset</a></code>
  54       and <code class="computeroutput"><a class="link" href="../boost/intrusive/splaytree.html" title="Class template splaytree">splaytree</a></code>. The
  55       first two are similar to <code class="computeroutput"><a class="link" href="../boost/intrusive/set.html" title="Class template set">set</a></code>
  56       or <code class="computeroutput"><a class="link" href="../boost/intrusive/multiset.html" title="Class template multiset">multiset</a></code> and the
  57       latter is a generalization that offers functions both to insert unique and
  58       multiple keys.
  59     </p>
  60 <p>
  61       The memory overhead of these containers with Boost.Intrusive hooks is usually
  62       3 pointers. An empty, non constant-time size splay container has also a size
  63       of 3 pointers.
  64     </p>
  65 <div class="section">
  66 <div class="titlepage"><div><div><h3 class="title">
  67 <a name="intrusive.splay_set_multiset.splay_set_multiset_disadvantages"></a><a class="link" href="splay_set_multiset.html#intrusive.splay_set_multiset.splay_set_multiset_disadvantages" title="Advantages and disadvantages of splay tree based containers">Advantages
  68       and disadvantages of splay tree based containers</a>
  69 </h3></div></div></div>
  70 <p>
  71         Splay tree based intrusive containers have logarithmic complexity in many
  72         operations like searches, insertions, erasures, etc., but if some elements
  73         are more frequently accessed than others, splay trees perform faster searches
  74         than equivalent balanced binary trees (such as red-black trees).
  75       </p>
  76 <p>
  77         The caching effect offered by splay trees comes with a cost: the tree must
  78         be rebalanced when an element is searched. To maintain const-correctness
  79         and thread-safety guarantees, this caching effect is not updated when const
  80         versions of search functions like <code class="computeroutput"><span class="identifier">find</span><span class="special">()</span></code>, <code class="computeroutput"><span class="identifier">lower_bound</span><span class="special">()</span></code>, <code class="computeroutput"><span class="identifier">upper_bound</span><span class="special">()</span></code>, <code class="computeroutput"><span class="identifier">equal_range</span><span class="special">()</span></code>, <code class="computeroutput"><span class="identifier">count</span><span class="special">()</span></code>... are called. This means that using splay-tree
  81         based associative containers as drop-in replacements of <code class="computeroutput"><a class="link" href="../boost/intrusive/set.html" title="Class template set">set</a></code>/
  82         <code class="computeroutput"><a class="link" href="../boost/intrusive/multiset.html" title="Class template multiset">multiset</a></code>, specially
  83         for const search functions, might not result in desired performance improvements.
  84       </p>
  85 <p>
  86         If element searches are randomized, the tree will be continuously srebalanced
  87         without taking advantage of the cache effect, so splay trees can offer worse
  88         performance than other balanced trees for several search patterns.
  89       </p>
  90 <p>
  91         <span class="bold"><strong>Boost.Intrusive</strong></span> splay associative containers
  92         don't use their own hook types but plain Binary search tree hooks. See <a class="link" href="bst_hooks.html" title="Binary search tree hooks: bs_set_base_hook and bs_set_member_hook">Binary search tree hooks: bs_set_base_hook
  93         and bs_set_member_hook</a> section for more information about these hooks.
  94       </p>
  95 </div>
  96 <div class="section">
  97 <div class="titlepage"><div><div><h3 class="title">
  98 <a name="intrusive.splay_set_multiset.set_multiset_containers"></a><a class="link" href="splay_set_multiset.html#intrusive.splay_set_multiset.set_multiset_containers" title="splay_set, splay_multiset and splaytree containers">splay_set,
  99       splay_multiset and splaytree containers</a>
 100 </h3></div></div></div>
 101 <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>
 102 <span class="keyword">class</span> <span class="identifier">splay_set</span><span class="special">;</span>
 103
 104 <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>
 105 <span class="keyword">class</span> <span class="identifier">splay_multiset</span><span class="special">;</span>
 106
 107 <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>
 108 <span class="keyword">class</span> <span class="identifier">splaytree</span><span class="special">;</span>
 109 </pre>
 110 <p>
 111         These containers receive the same options explained in the section <a class="link" href="usage.html" title="How to use Boost.Intrusive">How to use Boost.Intrusive</a>:
 112       </p>
 113 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 114 <li class="listitem">
 115             <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>
 116             / <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>
 117             / <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>:
 118             To specify the hook type or value traits used to configure the container.
 119             (To learn about value traits go to the section <a class="link" href="value_traits.html" title="Containers with custom ValueTraits">Containers
 120             with custom ValueTraits</a>.)
 121           </li>
 122 <li class="listitem">
 123             <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>:
 124             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>
 125           </li>
 126 <li class="listitem">
 127             <span class="bold"><strong><code class="computeroutput"><span class="identifier">size_type</span><span class="special">&lt;</span><span class="keyword">typename</span>
 128             <span class="identifier">SizeType</span><span class="special">&gt;</span></code></strong></span>:
 129             To specify the type that will be used to store the size of the container.
 130             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>
 131           </li>
 132 </ul></div>
 133 <p>
 134         And they also can receive an additional option:
 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">compare</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Compare</span><span class="special">&gt;</span></code></strong></span>:
 139             Comparison function for the objects to be inserted in containers. The
 140             comparison functor must induce a strict weak ordering. Default: <code class="computeroutput"><span class="identifier">compare</span><span class="special">&lt;</span>
 141             <span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special">&lt;</span><span class="identifier">key_type</span><span class="special">&gt;</span>
 142             <span class="special">&gt;</span></code>
 143           </li>
 144 <li class="listitem">
 145             <span class="bold"><strong><code class="computeroutput"><span class="identifier">key_of_value</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">KeyOfValueFunctionObject</span><span class="special">&gt;</span></code></strong></span>:
 146             A function object that will define the <code class="computeroutput"><span class="identifier">key_type</span></code>
 147             of the value type to be stored. This type will allow a map-like interface.
 148             See <a class="link" href="map_multimap.html" title="Map and multimap-like interface for associative containers">Map and multimap-like interface
 149             with set and multiset</a> for details. Default: <code class="computeroutput"><span class="identifier">key_type</span></code>
 150             is equal to <code class="computeroutput"><span class="identifier">value_type</span></code>
 151             (set-like interface).
 152           </li>
 153 </ul></div>
 154 </div>
 155 <div class="section">
 156 <div class="titlepage"><div><div><h3 class="title">
 157 <a name="intrusive.splay_set_multiset.splay_set_multiset_example"></a><a class="link" href="splay_set_multiset.html#intrusive.splay_set_multiset.splay_set_multiset_example" title="Example">Example</a>
 158 </h3></div></div></div>
 159 <p>
 160         Now let's see a small example using <code class="computeroutput"><a class="link" href="../boost/intrusive/splay_set.html" title="Class template splay_set">splay_set</a></code>/
 161         <code class="computeroutput"><a class="link" href="../boost/intrusive/splay_multiset.html" title="Class template splay_multiset">splay_multiset</a></code>
 162         containers:
 163       </p>
 164 <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">splay_set</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
 165 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
 166 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">functional</span><span class="special">&gt;</span>
 167
 168 <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>
 169
 170 <span class="keyword">class</span> <span class="identifier">mytag</span><span class="special">;</span>
 171
 172 <span class="keyword">class</span> <span class="identifier">MyClass</span>
 173    <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">bs_set_base_hook</span><span class="special">&lt;&gt;</span>
 174 <span class="special">{</span>
 175    <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span>
 176
 177    <span class="keyword">public</span><span class="special">:</span>
 178    <span class="comment">//This is a member hook</span>
 179    <span class="identifier">bs_set_member_hook</span><span class="special">&lt;&gt;</span> <span class="identifier">member_hook_</span><span class="special">;</span>
 180
 181    <span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span>
 182       <span class="special">:</span>  <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span>
 183       <span class="special">{}</span>
 184    <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">&lt;</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>
 185       <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">&lt;</span> <span class="identifier">b</span><span class="special">.</span><span class="identifier">int_</span><span class="special">;</span>  <span class="special">}</span>
 186    <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">&gt;</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>
 187       <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">&gt;</span> <span class="identifier">b</span><span class="special">.</span><span class="identifier">int_</span><span class="special">;</span>  <span class="special">}</span>
 188    <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>
 189       <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>
 190 <span class="special">};</span>
 191
 192 <span class="comment">//Define a set using the base hook that will store values in reverse order</span>
 193 <span class="keyword">typedef</span> <span class="identifier">splay_set</span><span class="special">&lt;</span> <span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">compare</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">greater</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="special">&gt;</span>     <span class="identifier">BaseSplaySet</span><span class="special">;</span>
 194
 195 <span class="comment">//Define an multiset using the member hook</span>
 196 <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">bs_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> <span class="identifier">MemberOption</span><span class="special">;</span>
 197 <span class="keyword">typedef</span> <span class="identifier">splay_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">MemberSplayMultiset</span><span class="special">;</span>
 198
 199 <span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
 200 <span class="special">{</span>
 201    <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>
 202
 203    <span class="comment">//Create several MyClass objects, each one with a different value</span>
 204    <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>
 205    <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>
 206
 207    <span class="identifier">BaseSplaySet</span>   <span class="identifier">baseset</span><span class="special">;</span>
 208    <span class="identifier">MemberSplayMultiset</span> <span class="identifier">membermultiset</span><span class="special">;</span>
 209
 210
 211    <span class="comment">//Insert values in the container</span>
 212    <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>
 213       <span class="identifier">baseset</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span>
 214       <span class="identifier">membermultiset</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span>
 215    <span class="special">}</span>
 216
 217    <span class="comment">//Now test sets</span>
 218    <span class="special">{</span>
 219       <span class="identifier">BaseSplaySet</span><span class="special">::</span><span class="identifier">reverse_iterator</span> <span class="identifier">rbit</span><span class="special">(</span><span class="identifier">baseset</span><span class="special">.</span><span class="identifier">rbegin</span><span class="special">());</span>
 220       <span class="identifier">MemberSplayMultiset</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">mit</span><span class="special">(</span><span class="identifier">membermultiset</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());</span>
 221       <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>
 222
 223       <span class="comment">//Test the objects inserted in the base hook set</span>
 224       <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> <span class="special">++</span><span class="identifier">rbit</span><span class="special">){</span>
 225          <span class="keyword">if</span><span class="special">(&amp;*</span><span class="identifier">rbit</span> <span class="special">!=</span> <span class="special">&amp;*</span><span class="identifier">it</span><span class="special">)</span>   <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span>
 226       <span class="special">}</span>
 227
 228       <span class="comment">//Test the objects inserted in member and binary search hook sets</span>
 229       <span class="keyword">for</span><span class="special">(</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">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">mit</span><span class="special">){</span>
 230          <span class="keyword">if</span><span class="special">(&amp;*</span><span class="identifier">mit</span> <span class="special">!=</span> <span class="special">&amp;*</span><span class="identifier">it</span><span class="special">)</span>    <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span>
 231       <span class="special">}</span>
 232    <span class="special">}</span>
 233    <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
 234 <span class="special">}</span>
 235 </pre>
 236 </div>
 237 </div>
 238 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 239 <td align="left"></td>
 240 <td align="right"><div class="copyright-footer">Copyright &#169; 2005 Olaf Krzikalla<br>Copyright &#169; 2006-2015 Ion Gaztanaga<p>
 241         Distributed under the Boost Software License, Version 1.0. (See accompanying
 242         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>)
 243       </p>
 244 </div></td>
 245 </tr></table>
 246 <hr>
 247 <div class="spirit-nav">
 248 <a accesskey="p" href="avl_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="sg_set_multiset.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
 249 </div>
 250 </body>
 251 </html>