1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Node algorithms with custom NodeTraits</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive"> 10<link rel="prev" href="concepts.html" title="Concepts explained"> 11<link rel="next" href="value_traits.html" title="Containers with custom ValueTraits"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="concepts.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="value_traits.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.node_algorithms"></a><a class="link" href="node_algorithms.html" title="Node algorithms with custom NodeTraits">Node algorithms with custom 29 NodeTraits</a> 30</h2></div></div></div> 31<div class="toc"><dl class="toc"> 32<dt><span class="section"><a href="node_algorithms.html#intrusive.node_algorithms.circular_slist_algorithms">Intrusive 33 singly linked list algorithms</a></span></dt> 34<dt><span class="section"><a href="node_algorithms.html#intrusive.node_algorithms.circular_list_algorithms">Intrusive 35 doubly linked list algorithms</a></span></dt> 36<dt><span class="section"><a href="node_algorithms.html#intrusive.node_algorithms.rbtree_algorithms">Intrusive 37 red-black tree algorithms</a></span></dt> 38<dt><span class="section"><a href="node_algorithms.html#intrusive.node_algorithms.splaytree_algorithms">Intrusive 39 splay tree algorithms</a></span></dt> 40<dt><span class="section"><a href="node_algorithms.html#intrusive.node_algorithms.avltree_algorithms">Intrusive 41 avl tree algorithms</a></span></dt> 42<dt><span class="section"><a href="node_algorithms.html#intrusive.node_algorithms.treap_algorithms">Intrusive 43 treap algorithms</a></span></dt> 44</dl></div> 45<p> 46 As explained in the <a class="link" href="concepts.html" title="Concepts explained">Concepts</a> section, 47 <span class="bold"><strong>Boost.Intrusive</strong></span> containers are implemented 48 using node algorithms that work on generic nodes. 49 </p> 50<p> 51 Sometimes, the use of intrusive containers is expensive for some environments 52 and the programmer might want to avoid all the template instantiations related 53 to <span class="bold"><strong>Boost.Intrusive</strong></span> containers. However, the 54 user can still benefit from <span class="bold"><strong>Boost.Intrusive</strong></span> 55 using the node algorithms, because some of those algorithms, like red-black 56 tree algorithms, are not trivial to write. 57 </p> 58<p> 59 All node algorithm classes are templatized by a <code class="computeroutput"><span class="identifier">NodeTraits</span></code> 60 class. This class encapsulates the needed internal type declarations and operations 61 to make a node compatible with node algorithms. Each type of node algorithms 62 has its own requirements: 63 </p> 64<div class="section"> 65<div class="titlepage"><div><div><h3 class="title"> 66<a name="intrusive.node_algorithms.circular_slist_algorithms"></a><a class="link" href="node_algorithms.html#intrusive.node_algorithms.circular_slist_algorithms" title="Intrusive singly linked list algorithms">Intrusive 67 singly linked list algorithms</a> 68</h3></div></div></div> 69<p> 70 These algorithms are static members of the <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_slist_algorithms.html" title="Class template circular_slist_algorithms">circular_slist_algorithms</a></code> 71 class: 72 </p> 73<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NodeTraits</span><span class="special">></span> 74<span class="keyword">struct</span> <span class="identifier">circular_slist_algorithms</span><span class="special">;</span> 75</pre> 76<p> 77 An empty list is formed by a node whose pointer to the next node points to 78 itself. <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_slist_algorithms.html" title="Class template circular_slist_algorithms">circular_slist_algorithms</a></code> 79 is configured with a NodeTraits class, which encapsulates the information 80 about the node to be manipulated. NodeTraits must support the following interface: 81 </p> 82<p> 83 <span class="bold"><strong>Typedefs</strong></span>: 84 </p> 85<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 86<li class="listitem"> 87 <code class="computeroutput"><span class="identifier">node</span></code>: The type of the 88 node that forms the circular list 89 </li> 90<li class="listitem"> 91 <code class="computeroutput"><span class="identifier">node_ptr</span></code>: The type of 92 a pointer to a node (usually node*) 93 </li> 94<li class="listitem"> 95 <code class="computeroutput"><span class="identifier">const_node_ptr</span></code>: The type 96 of a pointer to a const node (usually const node*) 97 </li> 98</ul></div> 99<p> 100 <span class="bold"><strong>Static functions</strong></span>: 101 </p> 102<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 103<li class="listitem"> 104 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 105 <span class="identifier">get_next</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the next node 106 stored in "n". 107 </li> 108<li class="listitem"> 109 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 110 <span class="identifier">set_next</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 111 <span class="identifier">next</span><span class="special">);</span></code>: 112 Sets the pointer to the next node stored in "n" to "next". 113 </li> 114</ul></div> 115<p> 116 Once we have a node traits configuration we can use <span class="bold"><strong>Boost.Intrusive</strong></span> 117 algorithms with our nodes: 118 </p> 119<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">circular_slist_algorithms</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 120<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 121 122<span class="keyword">struct</span> <span class="identifier">my_node</span> 123<span class="special">{</span> 124 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">;</span> 125 <span class="comment">//other members...</span> 126<span class="special">};</span> 127 128<span class="comment">//Define our own slist_node_traits</span> 129<span class="keyword">struct</span> <span class="identifier">my_slist_node_traits</span> 130<span class="special">{</span> 131 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="identifier">node</span><span class="special">;</span> 132 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 133 <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 134 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_next</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span><span class="special">;</span> <span class="special">}</span> 135 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_next</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">next</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span> <span class="special">=</span> <span class="identifier">next</span><span class="special">;</span> <span class="special">}</span> 136<span class="special">};</span> 137 138<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 139<span class="special">{</span> 140 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">circular_slist_algorithms</span><span class="special"><</span><span class="identifier">my_slist_node_traits</span><span class="special">></span> <span class="identifier">algo</span><span class="special">;</span> 141 <span class="identifier">my_node</span> <span class="identifier">one</span><span class="special">,</span> <span class="identifier">two</span><span class="special">,</span> <span class="identifier">three</span><span class="special">;</span> 142 143 <span class="comment">//Create an empty singly linked list container:</span> 144 <span class="comment">//"one" will be the first node of the container</span> 145 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">init_header</span><span class="special">(&</span><span class="identifier">one</span><span class="special">);</span> 146 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> 147 148 <span class="comment">//Now add a new node</span> 149 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">link_after</span><span class="special">(&</span><span class="identifier">one</span><span class="special">,</span> <span class="special">&</span><span class="identifier">two</span><span class="special">);</span> 150 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">2</span><span class="special">);</span> 151 152 <span class="comment">//Now add a new node after "one"</span> 153 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">link_after</span><span class="special">(&</span><span class="identifier">one</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 154 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">3</span><span class="special">);</span> 155 156 <span class="comment">//Now unlink the node after one</span> 157 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink_after</span><span class="special">(&</span><span class="identifier">one</span><span class="special">);</span> 158 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">2</span><span class="special">);</span> 159 160 <span class="comment">//Now unlink two</span> 161 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">two</span><span class="special">);</span> 162 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> 163 164 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 165<span class="special">}</span> 166</pre> 167<p> 168 For a complete list of functions see <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_slist_algorithms.html" title="Class template circular_slist_algorithms">circular_slist_algorithms 169 reference</a></code>. 170 </p> 171</div> 172<div class="section"> 173<div class="titlepage"><div><div><h3 class="title"> 174<a name="intrusive.node_algorithms.circular_list_algorithms"></a><a class="link" href="node_algorithms.html#intrusive.node_algorithms.circular_list_algorithms" title="Intrusive doubly linked list algorithms">Intrusive 175 doubly linked list algorithms</a> 176</h3></div></div></div> 177<p> 178 These algorithms are static members of the <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_list_algorithms.html" title="Class template circular_list_algorithms">circular_list_algorithms</a></code> 179 class: 180 </p> 181<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NodeTraits</span><span class="special">></span> 182<span class="keyword">struct</span> <span class="identifier">circular_list_algorithms</span><span class="special">;</span> 183</pre> 184<p> 185 An empty list is formed by a node whose pointer to the next node points to 186 itself. <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_list_algorithms.html" title="Class template circular_list_algorithms">circular_list_algorithms</a></code> 187 is configured with a NodeTraits class, which encapsulates the information 188 about the node to be manipulated. NodeTraits must support the following interface: 189 </p> 190<p> 191 <span class="bold"><strong>Typedefs</strong></span>: 192 </p> 193<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 194<li class="listitem"> 195 <code class="computeroutput"><span class="identifier">node</span></code>: The type of the 196 node that forms the circular list 197 </li> 198<li class="listitem"> 199 <code class="computeroutput"><span class="identifier">node_ptr</span></code>: The type of 200 a pointer to a node (usually node*) 201 </li> 202<li class="listitem"> 203 <code class="computeroutput"><span class="identifier">const_node_ptr</span></code>: The type 204 of a pointer to a const node (usually const node*) 205 </li> 206</ul></div> 207<p> 208 <span class="bold"><strong>Static functions</strong></span>: 209 </p> 210<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 211<li class="listitem"> 212 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 213 <span class="identifier">get_next</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the next node 214 stored in "n". 215 </li> 216<li class="listitem"> 217 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 218 <span class="identifier">set_next</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 219 <span class="identifier">next</span><span class="special">);</span></code>: 220 Sets the pointer to the next node stored in "n" to "next". 221 </li> 222<li class="listitem"> 223 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 224 <span class="identifier">get_previous</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the previous 225 node stored in "n". 226 </li> 227<li class="listitem"> 228 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 229 <span class="identifier">set_previous</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 230 <span class="identifier">prev</span><span class="special">);</span></code>: 231 Sets the pointer to the previous node stored in "n" to "prev". 232 </li> 233</ul></div> 234<p> 235 Once we have a node traits configuration we can use <span class="bold"><strong>Boost.Intrusive</strong></span> 236 algorithms with our nodes: 237 </p> 238<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">circular_list_algorithms</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 239<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 240 241<span class="keyword">struct</span> <span class="identifier">my_node</span> 242<span class="special">{</span> 243 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">prev_</span><span class="special">;</span> 244 <span class="comment">//other members...</span> 245<span class="special">};</span> 246 247<span class="comment">//Define our own list_node_traits</span> 248<span class="keyword">struct</span> <span class="identifier">my_list_node_traits</span> 249<span class="special">{</span> 250 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="identifier">node</span><span class="special">;</span> 251 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 252 <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 253 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_next</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span><span class="special">;</span> <span class="special">}</span> 254 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_next</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">next</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span> <span class="special">=</span> <span class="identifier">next</span><span class="special">;</span> <span class="special">}</span> 255 <span class="keyword">static</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">get_previous</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">prev_</span><span class="special">;</span> <span class="special">}</span> 256 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_previous</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">prev</span><span class="special">){</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">prev_</span> <span class="special">=</span> <span class="identifier">prev</span><span class="special">;</span> <span class="special">}</span> 257<span class="special">};</span> 258 259<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 260<span class="special">{</span> 261 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">circular_list_algorithms</span><span class="special"><</span><span class="identifier">my_list_node_traits</span><span class="special">></span> <span class="identifier">algo</span><span class="special">;</span> 262 <span class="identifier">my_node</span> <span class="identifier">one</span><span class="special">,</span> <span class="identifier">two</span><span class="special">,</span> <span class="identifier">three</span><span class="special">;</span> 263 264 <span class="comment">//Create an empty doubly linked list container:</span> 265 <span class="comment">//"one" will be the first node of the container</span> 266 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">init_header</span><span class="special">(&</span><span class="identifier">one</span><span class="special">);</span> 267 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> 268 269 <span class="comment">//Now add a new node before "one"</span> 270 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">link_before</span><span class="special">(&</span><span class="identifier">one</span><span class="special">,</span> <span class="special">&</span><span class="identifier">two</span><span class="special">);</span> 271 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">2</span><span class="special">);</span> 272 273 <span class="comment">//Now add a new node after "two"</span> 274 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">link_after</span><span class="special">(&</span><span class="identifier">two</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 275 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">3</span><span class="special">);</span> 276 277 <span class="comment">//Now unlink the node after one</span> 278 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">three</span><span class="special">);</span> 279 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">2</span><span class="special">);</span> 280 281 <span class="comment">//Now unlink two</span> 282 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">two</span><span class="special">);</span> 283 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> 284 285 <span class="comment">//Now unlink one</span> 286 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">one</span><span class="special">);</span> 287 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">algo</span><span class="special">::</span><span class="identifier">count</span><span class="special">(&</span><span class="identifier">one</span><span class="special">)</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> 288 289 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 290<span class="special">}</span> 291</pre> 292<p> 293 For a complete list of functions see <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_list_algorithms.html" title="Class template circular_list_algorithms">circular_list_algorithms 294 reference</a></code>. 295 </p> 296</div> 297<div class="section"> 298<div class="titlepage"><div><div><h3 class="title"> 299<a name="intrusive.node_algorithms.rbtree_algorithms"></a><a class="link" href="node_algorithms.html#intrusive.node_algorithms.rbtree_algorithms" title="Intrusive red-black tree algorithms">Intrusive 300 red-black tree algorithms</a> 301</h3></div></div></div> 302<p> 303 These algorithms are static members of the <code class="computeroutput"><a class="link" href="../boost/intrusive/rbtree_algorithms.html" title="Class template rbtree_algorithms">rbtree_algorithms</a></code> 304 class: 305 </p> 306<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NodeTraits</span><span class="special">></span> 307<span class="keyword">struct</span> <span class="identifier">rbtree_algorithms</span><span class="special">;</span> 308</pre> 309<p> 310 An empty tree is formed by a node whose pointer to the parent node is null, 311 the left and right node pointers point to itself, and whose color is red. 312 <code class="computeroutput"><a class="link" href="../boost/intrusive/rbtree_algorithms.html" title="Class template rbtree_algorithms">rbtree_algorithms</a></code> 313 is configured with a NodeTraits class, which encapsulates the information 314 about the node to be manipulated. NodeTraits must support the following interface: 315 </p> 316<p> 317 <span class="bold"><strong>Typedefs</strong></span>: 318 </p> 319<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 320<li class="listitem"> 321 <code class="computeroutput"><span class="identifier">node</span></code>: The type of the 322 node that forms the circular rbtree 323 </li> 324<li class="listitem"> 325 <code class="computeroutput"><span class="identifier">node_ptr</span></code>: The type of 326 a pointer to a node (usually node*) 327 </li> 328<li class="listitem"> 329 <code class="computeroutput"><span class="identifier">const_node_ptr</span></code>: The type 330 of a pointer to a const node (usually const node*) 331 </li> 332<li class="listitem"> 333 <code class="computeroutput"><span class="identifier">color</span></code>: The type that 334 can store the color of a node 335 </li> 336</ul></div> 337<p> 338 <span class="bold"><strong>Static functions</strong></span>: 339 </p> 340<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 341<li class="listitem"> 342 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 343 <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the parent node 344 stored in "n". 345 </li> 346<li class="listitem"> 347 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 348 <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 349 <span class="identifier">p</span><span class="special">);</span></code>: 350 Sets the pointer to the parent node stored in "n" to "p". 351 </li> 352<li class="listitem"> 353 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 354 <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the left node 355 stored in "n". 356 </li> 357<li class="listitem"> 358 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 359 <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 360 <span class="identifier">l</span><span class="special">);</span></code>: 361 Sets the pointer to the left node stored in "n" to "l". 362 </li> 363<li class="listitem"> 364 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 365 <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the right node 366 stored in "n". 367 </li> 368<li class="listitem"> 369 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 370 <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 371 <span class="identifier">r</span><span class="special">);</span></code>: 372 Sets the pointer to the right node stored in "n" to "r". 373 </li> 374<li class="listitem"> 375 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">color</span> 376 <span class="identifier">get_color</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns the color stored in "n". 377 </li> 378<li class="listitem"> 379 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 380 <span class="identifier">set_color</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">color</span> <span class="identifier">c</span><span class="special">);</span></code>: 381 Sets the color stored in "n" to "c". 382 </li> 383<li class="listitem"> 384 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">color</span> 385 <span class="identifier">black</span><span class="special">();</span></code>: 386 Returns a value representing the black color. 387 </li> 388<li class="listitem"> 389 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">color</span> 390 <span class="identifier">red</span><span class="special">();</span></code>: 391 Returns a value representing the red color. 392 </li> 393</ul></div> 394<p> 395 Once we have a node traits configuration we can use <span class="bold"><strong>Boost.Intrusive</strong></span> 396 algorithms with our nodes: 397 </p> 398<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">rbtree_algorithms</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 399<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 400 401<span class="keyword">struct</span> <span class="identifier">my_node</span> 402<span class="special">{</span> 403 <span class="identifier">my_node</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> 404 <span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 405 <span class="special">{}</span> 406 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">parent_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">left_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">right_</span><span class="special">;</span> 407 <span class="keyword">int</span> <span class="identifier">color_</span><span class="special">;</span> 408 <span class="comment">//other members</span> 409 <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span> 410<span class="special">};</span> 411 412<span class="comment">//Define our own rbtree_node_traits</span> 413<span class="keyword">struct</span> <span class="identifier">my_rbtree_node_traits</span> 414<span class="special">{</span> 415 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="identifier">node</span><span class="special">;</span> 416 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 417 <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 418 <span class="keyword">typedef</span> <span class="keyword">int</span> <span class="identifier">color</span><span class="special">;</span> 419 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span><span class="special">;</span> <span class="special">}</span> 420 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">parent</span><span class="special">){</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span> <span class="special">=</span> <span class="identifier">parent</span><span class="special">;</span> <span class="special">}</span> 421 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span><span class="special">;</span> <span class="special">}</span> 422 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">left</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span> <span class="special">=</span> <span class="identifier">left</span><span class="special">;</span> <span class="special">}</span> 423 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span><span class="special">;</span> <span class="special">}</span> 424 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">right</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span> <span class="special">=</span> <span class="identifier">right</span><span class="special">;</span> <span class="special">}</span> 425 <span class="keyword">static</span> <span class="identifier">color</span> <span class="identifier">get_color</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">color_</span><span class="special">;</span> <span class="special">}</span> 426 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_color</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">color</span> <span class="identifier">c</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">color_</span> <span class="special">=</span> <span class="identifier">c</span><span class="special">;</span> <span class="special">}</span> 427 <span class="keyword">static</span> <span class="identifier">color</span> <span class="identifier">black</span><span class="special">()</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">color</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> <span class="special">}</span> 428 <span class="keyword">static</span> <span class="identifier">color</span> <span class="identifier">red</span><span class="special">()</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">color</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> <span class="special">}</span> 429<span class="special">};</span> 430 431<span class="keyword">struct</span> <span class="identifier">node_ptr_compare</span> 432<span class="special">{</span> 433 <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">a</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">b</span><span class="special">)</span> 434 <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> 435<span class="special">};</span> 436 437<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 438<span class="special">{</span> 439 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">rbtree_algorithms</span><span class="special"><</span><span class="identifier">my_rbtree_node_traits</span><span class="special">></span> <span class="identifier">algo</span><span class="special">;</span> 440 <span class="identifier">my_node</span> <span class="identifier">header</span><span class="special">,</span> <span class="identifier">two</span><span class="special">(</span><span class="number">2</span><span class="special">),</span> <span class="identifier">three</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 441 442 <span class="comment">//Create an empty rbtree container:</span> 443 <span class="comment">//"header" will be the header node of the tree</span> 444 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">init_header</span><span class="special">(&</span><span class="identifier">header</span><span class="special">);</span> 445 446 <span class="comment">//Now insert node "two" in the tree using the sorting functor</span> 447 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_upper_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">two</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">());</span> 448 449 <span class="comment">//Now insert node "three" in the tree using the sorting functor</span> 450 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_lower_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">());</span> 451 452 <span class="comment">//Now take the first node (the left node of the header)</span> 453 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">n</span> <span class="special">=</span> <span class="identifier">header</span><span class="special">.</span><span class="identifier">left_</span><span class="special">;</span> 454 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">two</span><span class="special">);</span> 455 456 <span class="comment">//Now go to the next node</span> 457 <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">algo</span><span class="special">::</span><span class="identifier">next_node</span><span class="special">(</span><span class="identifier">n</span><span class="special">);</span> 458 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 459 460 <span class="comment">//Erase a node just using a pointer to it</span> 461 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">two</span><span class="special">);</span> 462 463 <span class="comment">//Erase a node using also the header (faster)</span> 464 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 465 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 466<span class="special">}</span> 467</pre> 468<p> 469 For a complete list of functions see <code class="computeroutput"><a class="link" href="../boost/intrusive/rbtree_algorithms.html" title="Class template rbtree_algorithms">rbtree_algorithms 470 reference</a></code>. 471 </p> 472</div> 473<div class="section"> 474<div class="titlepage"><div><div><h3 class="title"> 475<a name="intrusive.node_algorithms.splaytree_algorithms"></a><a class="link" href="node_algorithms.html#intrusive.node_algorithms.splaytree_algorithms" title="Intrusive splay tree algorithms">Intrusive 476 splay tree algorithms</a> 477</h3></div></div></div> 478<p> 479 These algorithms are static members of the <code class="computeroutput"><a class="link" href="../boost/intrusive/splaytree_algorithms.html" title="Class template splaytree_algorithms">splaytree_algorithms</a></code> 480 class: 481 </p> 482<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NodeTraits</span><span class="special">></span> 483<span class="keyword">struct</span> <span class="identifier">splaytree_algorithms</span><span class="special">;</span> 484</pre> 485<p> 486 An empty tree is formed by a node whose pointer to the parent node is null, 487 and whose left and right nodes pointers point to itself. <code class="computeroutput"><a class="link" href="../boost/intrusive/splaytree_algorithms.html" title="Class template splaytree_algorithms">splaytree_algorithms</a></code> 488 is configured with a NodeTraits class, which encapsulates the information 489 about the node to be manipulated. NodeTraits must support the following interface: 490 </p> 491<p> 492 <span class="bold"><strong>Typedefs</strong></span>: 493 </p> 494<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 495<li class="listitem"> 496 <code class="computeroutput"><span class="identifier">node</span></code>: The type of the 497 node that forms the circular splaytree 498 </li> 499<li class="listitem"> 500 <code class="computeroutput"><span class="identifier">node_ptr</span></code>: The type of 501 a pointer to a node (usually node*) 502 </li> 503<li class="listitem"> 504 <code class="computeroutput"><span class="identifier">const_node_ptr</span></code>: The type 505 of a pointer to a const node (usually const node*) 506 </li> 507</ul></div> 508<p> 509 <span class="bold"><strong>Static functions</strong></span>: 510 </p> 511<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 512<li class="listitem"> 513 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 514 <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the parent node 515 stored in "n". 516 </li> 517<li class="listitem"> 518 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 519 <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 520 <span class="identifier">p</span><span class="special">);</span></code>: 521 Sets the pointer to the parent node stored in "n" to "p". 522 </li> 523<li class="listitem"> 524 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 525 <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the left node 526 stored in "n". 527 </li> 528<li class="listitem"> 529 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 530 <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 531 <span class="identifier">l</span><span class="special">);</span></code>: 532 Sets the pointer to the left node stored in "n" to "l". 533 </li> 534<li class="listitem"> 535 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 536 <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the right node 537 stored in "n". 538 </li> 539<li class="listitem"> 540 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 541 <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 542 <span class="identifier">r</span><span class="special">);</span></code>: 543 Sets the pointer to the right node stored in "n" to "r". 544 </li> 545</ul></div> 546<p> 547 Once we have a node traits configuration we can use <span class="bold"><strong>Boost.Intrusive</strong></span> 548 algorithms with our nodes: 549 </p> 550<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">splaytree_algorithms</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 551<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 552 553<span class="keyword">struct</span> <span class="identifier">my_node</span> 554<span class="special">{</span> 555 <span class="identifier">my_node</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> 556 <span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 557 <span class="special">{}</span> 558 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">parent_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">left_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">right_</span><span class="special">;</span> 559 <span class="comment">//other members</span> 560 <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span> 561<span class="special">};</span> 562 563<span class="comment">//Define our own splaytree_node_traits</span> 564<span class="keyword">struct</span> <span class="identifier">my_splaytree_node_traits</span> 565<span class="special">{</span> 566 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="identifier">node</span><span class="special">;</span> 567 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 568 <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 569 570 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span><span class="special">;</span> <span class="special">}</span> 571 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">parent</span><span class="special">){</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span> <span class="special">=</span> <span class="identifier">parent</span><span class="special">;</span> <span class="special">}</span> 572 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span><span class="special">;</span> <span class="special">}</span> 573 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">left</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span> <span class="special">=</span> <span class="identifier">left</span><span class="special">;</span> <span class="special">}</span> 574 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span><span class="special">;</span> <span class="special">}</span> 575 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">right</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span> <span class="special">=</span> <span class="identifier">right</span><span class="special">;</span> <span class="special">}</span> 576<span class="special">};</span> 577 578<span class="keyword">struct</span> <span class="identifier">node_ptr_compare</span> 579<span class="special">{</span> 580 <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">a</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">b</span><span class="special">)</span> 581 <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> 582<span class="special">};</span> 583 584<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 585<span class="special">{</span> 586 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">splaytree_algorithms</span><span class="special"><</span><span class="identifier">my_splaytree_node_traits</span><span class="special">></span> <span class="identifier">algo</span><span class="special">;</span> 587 <span class="identifier">my_node</span> <span class="identifier">header</span><span class="special">,</span> <span class="identifier">two</span><span class="special">(</span><span class="number">2</span><span class="special">),</span> <span class="identifier">three</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 588 589 <span class="comment">//Create an empty splaytree container:</span> 590 <span class="comment">//"header" will be the header node of the tree</span> 591 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">init_header</span><span class="special">(&</span><span class="identifier">header</span><span class="special">);</span> 592 593 <span class="comment">//Now insert node "two" in the tree using the sorting functor</span> 594 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_upper_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">two</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">());</span> 595 596 <span class="comment">//Now insert node "three" in the tree using the sorting functor</span> 597 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_lower_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">());</span> 598 599 <span class="comment">//Now take the first node (the left node of the header)</span> 600 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">n</span> <span class="special">=</span> <span class="identifier">header</span><span class="special">.</span><span class="identifier">left_</span><span class="special">;</span> 601 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">two</span><span class="special">);</span> 602 603 <span class="comment">//Now go to the next node</span> 604 <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">algo</span><span class="special">::</span><span class="identifier">next_node</span><span class="special">(</span><span class="identifier">n</span><span class="special">);</span> 605 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 606 607 <span class="comment">//Erase a node just using a pointer to it</span> 608 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">two</span><span class="special">);</span> 609 610 <span class="comment">//Erase a node using also the header (faster)</span> 611 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 612 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 613<span class="special">}</span> 614</pre> 615<p> 616 For a complete list of functions see <code class="computeroutput"><a class="link" href="../boost/intrusive/splaytree_algorithms.html" title="Class template splaytree_algorithms">splaytree_algorithms 617 reference</a></code>. 618 </p> 619</div> 620<div class="section"> 621<div class="titlepage"><div><div><h3 class="title"> 622<a name="intrusive.node_algorithms.avltree_algorithms"></a><a class="link" href="node_algorithms.html#intrusive.node_algorithms.avltree_algorithms" title="Intrusive avl tree algorithms">Intrusive 623 avl tree algorithms</a> 624</h3></div></div></div> 625<p> 626 <code class="computeroutput"><a class="link" href="../boost/intrusive/avltree_algorithms.html" title="Class template avltree_algorithms">avltree_algorithms</a></code> 627 have the same interface as <code class="computeroutput"><a class="link" href="../boost/intrusive/rbtree_algorithms.html" title="Class template rbtree_algorithms">rbtree_algorithms</a></code>. 628 </p> 629<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NodeTraits</span><span class="special">></span> 630<span class="keyword">struct</span> <span class="identifier">avltree_algorithms</span><span class="special">;</span> 631</pre> 632<p> 633 <code class="computeroutput"><a class="link" href="../boost/intrusive/avltree_algorithms.html" title="Class template avltree_algorithms">avltree_algorithms</a></code> 634 is configured with a NodeTraits class, which encapsulates the information 635 about the node to be manipulated. NodeTraits must support the following interface: 636 </p> 637<p> 638 <span class="bold"><strong>Typedefs</strong></span>: 639 </p> 640<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 641<li class="listitem"> 642 <code class="computeroutput"><span class="identifier">node</span></code>: The type of the 643 node that forms the circular avltree 644 </li> 645<li class="listitem"> 646 <code class="computeroutput"><span class="identifier">node_ptr</span></code>: The type of 647 a pointer to a node (usually node*) 648 </li> 649<li class="listitem"> 650 <code class="computeroutput"><span class="identifier">const_node_ptr</span></code>: The type 651 of a pointer to a const node (usually const node*) 652 </li> 653<li class="listitem"> 654 <code class="computeroutput"><span class="identifier">balance</span></code>: A type that 655 can represent 3 balance types (usually an integer) 656 </li> 657</ul></div> 658<p> 659 <span class="bold"><strong>Static functions</strong></span>: 660 </p> 661<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 662<li class="listitem"> 663 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 664 <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the parent node 665 stored in "n". 666 </li> 667<li class="listitem"> 668 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 669 <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 670 <span class="identifier">p</span><span class="special">);</span></code>: 671 Sets the pointer to the parent node stored in "n" to "p". 672 </li> 673<li class="listitem"> 674 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 675 <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the left node 676 stored in "n". 677 </li> 678<li class="listitem"> 679 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 680 <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 681 <span class="identifier">l</span><span class="special">);</span></code>: 682 Sets the pointer to the left node stored in "n" to "l". 683 </li> 684<li class="listitem"> 685 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 686 <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the right node 687 stored in "n". 688 </li> 689<li class="listitem"> 690 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 691 <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 692 <span class="identifier">r</span><span class="special">);</span></code>: 693 Sets the pointer to the right node stored in "n" to "r". 694 </li> 695<li class="listitem"> 696 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">balance</span> 697 <span class="identifier">get_balance</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns the balance factor stored 698 in "n". 699 </li> 700<li class="listitem"> 701 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 702 <span class="identifier">set_balance</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">balance</span> 703 <span class="identifier">b</span><span class="special">);</span></code>: 704 Sets the balance factor stored in "n" to "b". 705 </li> 706<li class="listitem"> 707 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">balance</span> 708 <span class="identifier">negative</span><span class="special">();</span></code>: 709 Returns a value representing a negative balance factor. 710 </li> 711<li class="listitem"> 712 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">balance</span> 713 <span class="identifier">zero</span><span class="special">();</span></code>: 714 Returns a value representing a zero balance factor. 715 </li> 716<li class="listitem"> 717 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">balance</span> 718 <span class="identifier">positive</span><span class="special">();</span></code>: 719 Returns a value representing a positive balance factor. 720 </li> 721</ul></div> 722<p> 723 Once we have a node traits configuration we can use <span class="bold"><strong>Boost.Intrusive</strong></span> 724 algorithms with our nodes: 725 </p> 726<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">avltree_algorithms</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 727<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 728 729<span class="keyword">struct</span> <span class="identifier">my_node</span> 730<span class="special">{</span> 731 <span class="identifier">my_node</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> 732 <span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 733 <span class="special">{}</span> 734 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">parent_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">left_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">right_</span><span class="special">;</span> 735 <span class="keyword">int</span> <span class="identifier">balance_</span><span class="special">;</span> 736 <span class="comment">//other members</span> 737 <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span> 738<span class="special">};</span> 739 740<span class="comment">//Define our own avltree_node_traits</span> 741<span class="keyword">struct</span> <span class="identifier">my_avltree_node_traits</span> 742<span class="special">{</span> 743 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="identifier">node</span><span class="special">;</span> 744 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 745 <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 746 <span class="keyword">typedef</span> <span class="keyword">int</span> <span class="identifier">balance</span><span class="special">;</span> 747 748 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span><span class="special">;</span> <span class="special">}</span> 749 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">parent</span><span class="special">){</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span> <span class="special">=</span> <span class="identifier">parent</span><span class="special">;</span> <span class="special">}</span> 750 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span><span class="special">;</span> <span class="special">}</span> 751 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">left</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span> <span class="special">=</span> <span class="identifier">left</span><span class="special">;</span> <span class="special">}</span> 752 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span><span class="special">;</span> <span class="special">}</span> 753 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">right</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span> <span class="special">=</span> <span class="identifier">right</span><span class="special">;</span> <span class="special">}</span> 754 <span class="keyword">static</span> <span class="identifier">balance</span> <span class="identifier">get_balance</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">balance_</span><span class="special">;</span> <span class="special">}</span> 755 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_balance</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">balance</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">balance_</span> <span class="special">=</span> <span class="identifier">b</span><span class="special">;</span> <span class="special">}</span> 756 <span class="keyword">static</span> <span class="identifier">balance</span> <span class="identifier">negative</span><span class="special">()</span> <span class="special">{</span> <span class="keyword">return</span> <span class="special">-</span><span class="number">1</span><span class="special">;</span> <span class="special">}</span> 757 <span class="keyword">static</span> <span class="identifier">balance</span> <span class="identifier">zero</span><span class="special">()</span> <span class="special">{</span> <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> <span class="special">}</span> 758 <span class="keyword">static</span> <span class="identifier">balance</span> <span class="identifier">positive</span><span class="special">()</span> <span class="special">{</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span> <span class="special">}</span> 759<span class="special">};</span> 760 761<span class="keyword">struct</span> <span class="identifier">node_ptr_compare</span> 762<span class="special">{</span> 763 <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">a</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">b</span><span class="special">)</span> 764 <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> 765<span class="special">};</span> 766 767<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 768<span class="special">{</span> 769 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">avltree_algorithms</span><span class="special"><</span><span class="identifier">my_avltree_node_traits</span><span class="special">></span> <span class="identifier">algo</span><span class="special">;</span> 770 <span class="identifier">my_node</span> <span class="identifier">header</span><span class="special">,</span> <span class="identifier">two</span><span class="special">(</span><span class="number">2</span><span class="special">),</span> <span class="identifier">three</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 771 772 <span class="comment">//Create an empty avltree container:</span> 773 <span class="comment">//"header" will be the header node of the tree</span> 774 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">init_header</span><span class="special">(&</span><span class="identifier">header</span><span class="special">);</span> 775 776 <span class="comment">//Now insert node "two" in the tree using the sorting functor</span> 777 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_upper_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">two</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">());</span> 778 779 <span class="comment">//Now insert node "three" in the tree using the sorting functor</span> 780 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_lower_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">());</span> 781 782 <span class="comment">//Now take the first node (the left node of the header)</span> 783 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">n</span> <span class="special">=</span> <span class="identifier">header</span><span class="special">.</span><span class="identifier">left_</span><span class="special">;</span> 784 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">two</span><span class="special">);</span> 785 786 <span class="comment">//Now go to the next node</span> 787 <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">algo</span><span class="special">::</span><span class="identifier">next_node</span><span class="special">(</span><span class="identifier">n</span><span class="special">);</span> 788 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 789 790 <span class="comment">//Erase a node just using a pointer to it</span> 791 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">two</span><span class="special">);</span> 792 793 <span class="comment">//Erase a node using also the header (faster)</span> 794 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 795 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 796<span class="special">}</span> 797</pre> 798<p> 799 For a complete list of functions see <code class="computeroutput"><a class="link" href="../boost/intrusive/avltree_algorithms.html" title="Class template avltree_algorithms">avltree_algorithms 800 reference</a></code>. 801 </p> 802</div> 803<div class="section"> 804<div class="titlepage"><div><div><h3 class="title"> 805<a name="intrusive.node_algorithms.treap_algorithms"></a><a class="link" href="node_algorithms.html#intrusive.node_algorithms.treap_algorithms" title="Intrusive treap algorithms">Intrusive 806 treap algorithms</a> 807</h3></div></div></div> 808<p> 809 <code class="computeroutput"><a class="link" href="../boost/intrusive/treap_algorithms.html" title="Class template treap_algorithms">treap_algorithms</a></code> 810 have the same interface as <code class="computeroutput"><a class="link" href="../boost/intrusive/rbtree_algorithms.html" title="Class template rbtree_algorithms">rbtree_algorithms</a></code>. 811 </p> 812<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NodeTraits</span><span class="special">></span> 813<span class="keyword">struct</span> <span class="identifier">treap_algorithms</span><span class="special">;</span> 814</pre> 815<p> 816 <code class="computeroutput"><a class="link" href="../boost/intrusive/treap_algorithms.html" title="Class template treap_algorithms">treap_algorithms</a></code> 817 is configured with a NodeTraits class, which encapsulates the information 818 about the node to be manipulated. NodeTraits must support the following interface: 819 </p> 820<p> 821 <span class="bold"><strong>Typedefs</strong></span>: 822 </p> 823<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 824<li class="listitem"> 825 <code class="computeroutput"><span class="identifier">node</span></code>: The type of the 826 node that forms the circular treap 827 </li> 828<li class="listitem"> 829 <code class="computeroutput"><span class="identifier">node_ptr</span></code>: The type of 830 a pointer to a node (usually node*) 831 </li> 832<li class="listitem"> 833 <code class="computeroutput"><span class="identifier">const_node_ptr</span></code>: The type 834 of a pointer to a const node (usually const node*) 835 </li> 836</ul></div> 837<p> 838 <span class="bold"><strong>Static functions</strong></span>: 839 </p> 840<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 841<li class="listitem"> 842 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 843 <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the parent node 844 stored in "n". 845 </li> 846<li class="listitem"> 847 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 848 <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 849 <span class="identifier">p</span><span class="special">);</span></code>: 850 Sets the pointer to the parent node stored in "n" to "p". 851 </li> 852<li class="listitem"> 853 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 854 <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the left node 855 stored in "n". 856 </li> 857<li class="listitem"> 858 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 859 <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 860 <span class="identifier">l</span><span class="special">);</span></code>: 861 Sets the pointer to the left node stored in "n" to "l". 862 </li> 863<li class="listitem"> 864 <code class="computeroutput"><span class="keyword">static</span> <span class="identifier">node_ptr</span> 865 <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span></code>: Returns a pointer to the right node 866 stored in "n". 867 </li> 868<li class="listitem"> 869 <code class="computeroutput"><span class="keyword">static</span> <span class="keyword">void</span> 870 <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> 871 <span class="identifier">r</span><span class="special">);</span></code>: 872 Sets the pointer to the right node stored in "n" to "r". 873 </li> 874</ul></div> 875<p> 876 Once we have a node traits configuration we can use <span class="bold"><strong>Boost.Intrusive</strong></span> 877 algorithms with our nodes: 878 </p> 879<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">treap_algorithms</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 880<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 881 882<span class="keyword">struct</span> <span class="identifier">my_node</span> 883<span class="special">{</span> 884 <span class="identifier">my_node</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="keyword">unsigned</span> <span class="keyword">int</span> <span class="identifier">priority</span> <span class="special">=</span> <span class="number">0</span><span class="special">)</span> 885 <span class="special">:</span> <span class="identifier">prio_</span><span class="special">(</span><span class="identifier">priority</span><span class="special">),</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 886 <span class="special">{}</span> 887 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">parent_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">left_</span><span class="special">,</span> <span class="special">*</span><span class="identifier">right_</span><span class="special">;</span> 888 <span class="keyword">int</span> <span class="identifier">prio_</span><span class="special">;</span> 889 <span class="comment">//other members</span> 890 <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span> 891<span class="special">};</span> 892 893<span class="comment">//Define our own treap_node_traits</span> 894<span class="keyword">struct</span> <span class="identifier">my_treap_node_traits</span> 895<span class="special">{</span> 896 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="identifier">node</span><span class="special">;</span> 897 <span class="keyword">typedef</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 898 <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 899 900 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_parent</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span><span class="special">;</span> <span class="special">}</span> 901 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_parent</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">parent</span><span class="special">){</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">parent_</span> <span class="special">=</span> <span class="identifier">parent</span><span class="special">;</span> <span class="special">}</span> 902 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_left</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span><span class="special">;</span> <span class="special">}</span> 903 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_left</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">left</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">left_</span> <span class="special">=</span> <span class="identifier">left</span><span class="special">;</span> <span class="special">}</span> 904 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_right</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span><span class="special">;</span> <span class="special">}</span> 905 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_right</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">right</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">right_</span> <span class="special">=</span> <span class="identifier">right</span><span class="special">;</span> <span class="special">}</span> 906<span class="special">};</span> 907 908<span class="keyword">struct</span> <span class="identifier">node_ptr_compare</span> 909<span class="special">{</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">a</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">b</span><span class="special">)</span> <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> <span class="special">};</span> 910 911<span class="keyword">struct</span> <span class="identifier">node_ptr_priority</span> 912<span class="special">{</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">a</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">b</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">a</span><span class="special">-></span><span class="identifier">prio_</span> <span class="special"><</span> <span class="identifier">b</span><span class="special">-></span><span class="identifier">prio_</span><span class="special">;}</span> <span class="special">};</span> 913 914<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 915<span class="special">{</span> 916 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">treap_algorithms</span><span class="special"><</span><span class="identifier">my_treap_node_traits</span><span class="special">></span> <span class="identifier">algo</span><span class="special">;</span> 917 <span class="identifier">my_node</span> <span class="identifier">header</span><span class="special">,</span> <span class="identifier">two</span><span class="special">(</span><span class="number">2</span><span class="special">,</span> <span class="number">5</span><span class="special">),</span> <span class="identifier">three</span><span class="special">(</span><span class="number">3</span><span class="special">,</span> <span class="number">1</span><span class="special">);</span> 918 919 <span class="comment">//Create an empty treap container:</span> 920 <span class="comment">//"header" will be the header node of the tree</span> 921 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">init_header</span><span class="special">(&</span><span class="identifier">header</span><span class="special">);</span> 922 923 <span class="comment">//Now insert node "two" in the tree using the sorting functor</span> 924 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_upper_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">two</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">(),</span> <span class="identifier">node_ptr_priority</span><span class="special">());</span> 925 926 <span class="comment">//Now insert node "three" in the tree using the sorting functor</span> 927 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">insert_equal_lower_bound</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">,</span> <span class="identifier">node_ptr_compare</span><span class="special">(),</span> <span class="identifier">node_ptr_priority</span><span class="special">());</span> 928 929 <span class="comment">//Now take the first node (the left node of the header)</span> 930 <span class="identifier">my_node</span> <span class="special">*</span><span class="identifier">n</span> <span class="special">=</span> <span class="identifier">header</span><span class="special">.</span><span class="identifier">left_</span><span class="special">;</span> 931 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">two</span><span class="special">);</span> 932 933 <span class="comment">//Now go to the next node</span> 934 <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">algo</span><span class="special">::</span><span class="identifier">next_node</span><span class="special">(</span><span class="identifier">n</span><span class="special">);</span> 935 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">n</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">three</span><span class="special">);</span> 936 937 <span class="comment">//Erase a node just using a pointer to it</span> 938 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">(&</span><span class="identifier">two</span><span class="special">,</span> <span class="identifier">node_ptr_priority</span><span class="special">());</span> 939 940 <span class="comment">//Erase a node using also the header (faster)</span> 941 <span class="identifier">algo</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(&</span><span class="identifier">header</span><span class="special">,</span> <span class="special">&</span><span class="identifier">three</span><span class="special">,</span> <span class="identifier">node_ptr_priority</span><span class="special">());</span> 942 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 943<span class="special">}</span> 944</pre> 945<p> 946 For a complete list of functions see <code class="computeroutput"><a class="link" href="../boost/intrusive/treap_algorithms.html" title="Class template treap_algorithms">treap_algorithms 947 reference</a></code>. 948 </p> 949</div> 950</div> 951<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 952<td align="left"></td> 953<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 954 Distributed under the Boost Software License, Version 1.0. (See accompanying 955 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>) 956 </p> 957</div></td> 958</tr></table> 959<hr> 960<div class="spirit-nav"> 961<a accesskey="p" href="concepts.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="value_traits.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 962</div> 963</body> 964</html> 965
