libstdc++-v3/docs/html/ext/pb_ds/tree.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   2     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3
   4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   5 <head>
   6   <meta name="generator" content=
   7   "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
   8
   9   <title>tree Interface</title>
  10   <meta http-equiv="Content-Type" content=
  11   "text/html; charset=us-ascii" />
  12   </head>
  13
  14 <body>
  15   <div id="page">
  16     <h1><tt>tree</tt> Interface</h1>
  17
  18     <p>A concrete basic tree-based associative container.</p>
  19
  20     <p>Defined in: <a href=
  21     "../../../../include/ext/pb_ds/assoc_container.hpp"><tt>assoc_container.hpp</tt></a></p>
  22
  23     <h2><a name="link1" id="link1">Template Parameters</a></h2>
  24
  25     <table class="c1" width="100%" border="1" summary=
  26     "Template Parameters">
  27       <tr>
  28         <td width="20%" align="left"><b>Parameter</b></td>
  29
  30         <td width="50%" align="left"><b>Description</b></td>
  31
  32         <td width="30%" align="left"><b>Default Value</b></td>
  33       </tr>
  34
  35       <tr>
  36         <td>
  37           <pre>
  38 <a name="Key2501" id="Key2501"><b>typename</b> Key</a>
  39 </pre>
  40         </td>
  41
  42         <td>
  43           <p>Key type.</p>
  44         </td>
  45
  46         <td>-</td>
  47       </tr>
  48
  49       <tr>
  50         <td>
  51           <pre>
  52 <a name="Mapped318655" id="Mapped318655"><b>typename</b> Mapped</a>
  53 </pre>
  54         </td>
  55
  56         <td>
  57           <p>Mapped type.</p>
  58         </td>
  59
  60         <td>-</td>
  61       </tr>
  62
  63       <tr>
  64         <td>
  65           <pre>
  66 <a name="Cmp_Fn294335" id="Cmp_Fn294335"><b>class</b> Cmp_Fn </a>
  67 </pre>
  68         </td>
  69
  70         <td>
  71           <p>Comparison functor.</p>
  72         </td>
  73
  74         <td>
  75           <pre>
  76 std::less&lt;<a href="#Key2501"><tt>Key</tt></a>&gt;
  77 </pre>
  78         </td>
  79       </tr>
  80
  81       <tr>
  82         <td>
  83           <pre>
  84 <a name="Tag278938" id="Tag278938"><b>class</b> Tag </a>
  85 </pre>
  86         </td>
  87
  88         <td>
  89           <p>Mapped-structure tag.</p>
  90         </td>
  91
  92         <td><a href="rb_tree_tag.html"><span class=
  93         "c2"><tt>rb_tree_tag</tt></span></a></td>
  94       </tr>
  95
  96       <tr>
  97         <td>
  98           <pre>
  99 <a name="Node_Update841554648" id=
 100 "Node_Update841554648"><b>template</b>&lt;
 101   <b>typename</b> Const_Node_Iterator,
 102   <b>typename</b> Node_Iterator,
 103   <b>class</b> Cmp_Fn_,
 104   <b>typename</b> Allocator_&gt;
 105 <b>class</b> Node_Update </a>
 106 </pre>
 107         </td>
 108
 109         <td>
 110           <p>Node updater type.</p>
 111
 112           <p><a href=
 113           "tree_based_containers.html#invariants">Design::Tree-Based
 114           Containers::Node Invariants</a> explains this
 115           concept.</p>
 116         </td>
 117
 118         <td><a href="null_tree_node_update.html"><span class=
 119         "c2"><tt>null_tree_node_update</tt></span></a></td>
 120       </tr>
 121
 122       <tr>
 123         <td>
 124           <pre>
 125 <a name="Allocator35940069" id=
 126 "Allocator35940069"><b>class</b> Allocator </a>
 127 </pre>
 128         </td>
 129
 130         <td>
 131           <p>Allocator type.</p>
 132         </td>
 133
 134         <td>
 135           <pre>
 136 std::allocator&lt;<b>char</b>&gt;
 137 </pre>
 138         </td>
 139       </tr>
 140     </table>
 141
 142     <h2><a name="link2" id="link2">Base Classes</a></h2>
 143
 144     <table class="c1" width="100%" border="1" summary="Bases">
 145       <tr>
 146         <td width="80%" align="left"><b>Class</b></td>
 147
 148         <td width="20%" align="left"><b>Derivation Type</b></td>
 149       </tr>
 150
 151       <tr>
 152         <td>
 153           <pre>
 154 <a href="basic_tree.html"><span class=
 155 "c2"><tt>basic_tree</tt></span></a>
 156 </pre>
 157         </td>
 158
 159         <td>
 160           <p>public</p>
 161         </td>
 162       </tr>
 163     </table>
 164
 165     <h2><a name="link3" id="link3">Public Types and
 166     Constants</a></h2>
 167
 168     <h3><a name="link4" id="link4">Policy Definitions</a></h3>
 169
 170     <table class="c1" width="100%" border="1" summary="Types">
 171       <tr>
 172         <td width="30%" align="left"><b>Type</b></td>
 173
 174         <td width="55%" align="left"><b>Definition</b></td>
 175
 176         <td width="15%" align="left"><b>Description</b></td>
 177       </tr>
 178
 179       <tr>
 180         <td>
 181           <pre>
 182 <a name="cmp_fn394495" id="cmp_fn394495">cmp_fn</a>
 183 </pre>
 184         </td>
 185
 186         <td>
 187           <pre>
 188 <a href="#Cmp_Fn294335"><tt>Cmp_Fn</tt></a>
 189 </pre>
 190         </td>
 191
 192         <td>
 193           <p>Comparison functor type.</p>
 194         </td>
 195       </tr>
 196     </table>
 197
 198     <h3><a name="link5" id="link5">Iterator Definitions</a></h3>
 199
 200     <table class="c1" width="100%" border="1" summary="Types">
 201       <tr>
 202         <td width="30%" align="left"><b>Type</b></td>
 203
 204         <td width="55%" align="left"><b>Definition</b></td>
 205
 206         <td width="15%" align="left"><b>Description</b></td>
 207       </tr>
 208
 209       <tr>
 210         <td>
 211           <pre>
 212 <a name="const_node_iterator4205924553" id=
 213 "const_node_iterator4205924553">const_node_iterator</a>
 214 </pre>
 215         </td>
 216
 217         <td>
 218           <pre>
 219 <a href=
 220 "tree_const_node_iterator.html"><span class=
 221 "c2"><tt>const_node_iterator</tt></span></a>
 222 </pre>
 223         </td>
 224
 225         <td>
 226           <p>Const node iterator.</p>
 227         </td>
 228       </tr>
 229
 230       <tr>
 231         <td>
 232           <pre>
 233 <a name="node_iterator3431975247" id=
 234 "node_iterator3431975247">node_iterator</a>
 235 </pre>
 236         </td>
 237
 238         <td>
 239           <pre>
 240 <a href="tree_node_iterator.html"><span class=
 241 "c2"><tt>node_iterator</tt></span></a>
 242 </pre>
 243         </td>
 244
 245         <td>
 246           <p>Node iterator.</p>
 247         </td>
 248       </tr>
 249     </table>
 250
 251     <h2><a name="link6" id="link6">Public Methods</a></h2>
 252
 253     <h3><a name="link7" id="link7">Constructors, Destructor, and
 254     Related</a></h3>
 255
 256     <table class="c1" width="100%" border="1" summary="Methods">
 257       <tr>
 258         <td width="45%" align="left"><b>Method</b></td>
 259
 260         <td width="55%" align="left"><b>Description</b></td>
 261       </tr>
 262
 263       <tr>
 264         <td>
 265           <pre>
 266   tree
 267   ()
 268 </pre>
 269         </td>
 270
 271         <td>
 272           <p>Default constructor.</p>
 273         </td>
 274       </tr>
 275
 276       <tr>
 277         <td>
 278           <pre>
 279   tree
 280   (<b>const</b> <a href=
 281 "#cmp_fn394495"><tt>cmp_fn</tt></a> &amp;r_cmp_fn)
 282 </pre>
 283         </td>
 284
 285         <td>
 286           <p>Constructor taking some policy objects. <span class=
 287           "c1"><tt>r_cmp_fn</tt></span> will be copied by the
 288           <a href="#Cmp_Fn294335"><tt>Cmp_Fn</tt></a> object of the
 289           container object.</p>
 290         </td>
 291       </tr>
 292
 293       <tr>
 294         <td>
 295           <pre>
 296 <b>template</b>&lt;
 297     <b>class</b> It&gt;
 298   tree
 299   (It first_it,
 300     It last_it)
 301 </pre>
 302         </td>
 303
 304         <td>
 305           <p>Constructor taking iterators to a range of
 306           value_types. The value_types between <span class=
 307           "c1"><tt>first_it</tt></span> and <span class=
 308           "c1"><tt>last_it</tt></span> will be inserted into the
 309           container object.</p>
 310         </td>
 311       </tr>
 312
 313       <tr>
 314         <td>
 315           <pre>
 316 <b>template</b>&lt;
 317     <b>class</b> It&gt;
 318   tree
 319   (It first_it,
 320     It last_it,
 321     <b>const</b> <a href=
 322 "#cmp_fn394495"><tt>cmp_fn</tt></a> &amp;r_cmp_fn)
 323 </pre>
 324         </td>
 325
 326         <td>
 327           <p>Constructor taking iterators to a range of value_types
 328           and some policy objects The value_types between
 329           <span class="c1"><tt>first_it</tt></span> and
 330           <span class="c1"><tt>last_it</tt></span> will be inserted
 331           into the container object. <span class=
 332           "c1"><tt>r_cmp_fn</tt></span> will be copied by the
 333           <a href="#cmp_fn394495"><tt>cmp_fn</tt></a> object of the
 334           container object.</p>
 335         </td>
 336       </tr>
 337
 338       <tr>
 339         <td>
 340           <pre>
 341   tree
 342   (<b>const</b> <span class=
 343 "c2"><tt>tree</tt></span> &amp;other)
 344 </pre>
 345         </td>
 346
 347         <td>
 348           <p>Copy constructor.</p>
 349         </td>
 350       </tr>
 351
 352       <tr>
 353         <td>
 354           <pre>
 355 <b>virtual</b>
 356   ~tree
 357   ()
 358 </pre>
 359         </td>
 360
 361         <td>
 362           <p>Destructor.</p>
 363         </td>
 364       </tr>
 365
 366       <tr>
 367         <td>
 368           <pre>
 369 <span class="c2"><tt>tree</tt></span> &amp;
 370   <b>operator</b>=
 371   (<b>const</b> <span class=
 372 "c2"><tt>tree</tt></span> &amp;other)
 373 </pre>
 374         </td>
 375
 376         <td>
 377           <p>Assignment operator.</p>
 378         </td>
 379       </tr>
 380
 381       <tr>
 382         <td>
 383           <pre>
 384 <b>void</b>
 385   swap
 386   (<span class=
 387 "c2"><tt>tree</tt></span> &amp;other)
 388 </pre>
 389         </td>
 390
 391         <td>
 392           <p>Swaps content.</p>
 393         </td>
 394       </tr>
 395     </table>
 396
 397     <h3><a name="link8" id="link8">Policy Access Methods</a></h3>
 398
 399     <table class="c1" width="100%" border="1" summary="Methods">
 400       <tr>
 401         <td width="45%" align="left"><b>Method</b></td>
 402
 403         <td width="55%" align="left"><b>Description</b></td>
 404       </tr>
 405
 406       <tr>
 407         <td>
 408           <pre>
 409 <a href="#cmp_fn394495"><tt>cmp_fn</tt></a> &amp;
 410   get_cmp_fn
 411   ()
 412 </pre>
 413         </td>
 414
 415         <td>
 416           <p>Access to the <a href=
 417           "#cmp_fn394495"><tt>cmp_fn</tt></a> object.</p>
 418         </td>
 419       </tr>
 420
 421       <tr>
 422         <td>
 423           <pre>
 424 <b>const</b> <a href="#cmp_fn394495"><tt>cmp_fn</tt></a> &amp;
 425   get_cmp_fn
 426   () <b>const</b>
 427 </pre>
 428         </td>
 429
 430         <td>
 431           <p>Const access to the <a href=
 432           "#cmp_fn394495"><tt>cmp_fn</tt></a> object.</p>
 433         </td>
 434       </tr>
 435     </table>
 436
 437     <h3><a name="link9" id="link9">Node-Iteration Methods</a></h3>
 438
 439     <table class="c1" width="100%" border="1" summary="Methods">
 440       <tr>
 441         <td width="45%" align="left"><b>Method</b></td>
 442
 443         <td width="55%" align="left"><b>Description</b></td>
 444       </tr>
 445
 446       <tr>
 447         <td>
 448           <pre>
 449 <a href="#node_iterator3431975247"><tt>node_iterator</tt></a>
 450   node_begin
 451   ()
 452 </pre>
 453         </td>
 454
 455         <td>
 456           <p>Returns a <a href=
 457           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 458           corresponding to the node at the root of the tree.</p>
 459         </td>
 460       </tr>
 461
 462       <tr>
 463         <td>
 464           <pre>
 465 <a href=
 466 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 467   node_begin
 468   () <b>const</b>
 469 </pre>
 470         </td>
 471
 472         <td>
 473           <p>Returns a <a href=
 474           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 475           corresponding to the node at the root of the tree.</p>
 476         </td>
 477       </tr>
 478
 479       <tr>
 480         <td>
 481           <pre>
 482 <a href="#node_iterator3431975247"><tt>node_iterator</tt></a>
 483   node_end
 484   ()
 485 </pre>
 486         </td>
 487
 488         <td>
 489           <p>Returns a <a href=
 490           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 491           corresponding to a node just after a leaf of the
 492           tree.</p>
 493         </td>
 494       </tr>
 495
 496       <tr>
 497         <td>
 498           <pre>
 499 <a href=
 500 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 501   node_end
 502   () <b>const</b>
 503 </pre>
 504         </td>
 505
 506         <td>
 507           <p>Returns a <a href=
 508           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 509           corresponding to a node just after a leaf of the
 510           tree.</p>
 511         </td>
 512       </tr>
 513     </table>
 514   </div>
 515 </body>
 516 </html>