libstdc++-v3/docs/html/ext/pb_ds/basic_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>basic_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>basic_tree</tt> Interface</h1>
  17
  18     <p>An abstract basic tree-like-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="Tag278938" id="Tag278938"><b>class</b> Tag</a>
  67 </pre>
  68         </td>
  69
  70         <td>
  71           <p>Mapped-structure tag.</p>
  72         </td>
  73
  74         <td>-</td>
  75       </tr>
  76
  77       <tr>
  78         <td>
  79           <pre>
  80 <a name="Node_Update841554648" id=
  81 "Node_Update841554648"><b>class</b> Node_Update</a>
  82 </pre>
  83         </td>
  84
  85         <td>
  86           <p>Node updater.</p>
  87
  88           <p>Restores node-invariants when invalidated.</p>
  89         </td>
  90
  91         <td>-</td>
  92       </tr>
  93
  94       <tr>
  95         <td>
  96           <pre>
  97 <a name="Policy_Tl42017403" id=
  98 "Policy_Tl42017403"><b>class</b> Policy_Tl</a>
  99 </pre>
 100         </td>
 101
 102         <td>
 103           <p>Policy typelist.</p>
 104
 105           <p>Contains subclasses' policies.</p>
 106         </td>
 107
 108         <td>-</td>
 109       </tr>
 110
 111       <tr>
 112         <td>
 113           <pre>
 114 <a name="Allocator35940069" id=
 115 "Allocator35940069"><b>class</b> Allocator</a>
 116 </pre>
 117         </td>
 118
 119         <td>
 120           <p>Allocator type.</p>
 121         </td>
 122
 123         <td>-</td>
 124       </tr>
 125     </table>
 126
 127     <h2><a name="link2" id="link2">Base Classes</a></h2>
 128
 129     <table class="c1" width="100%" border="1" summary="Bases">
 130       <tr>
 131         <td width="80%" align="left"><b>Class</b></td>
 132
 133         <td width="20%" align="left"><b>Derivation Type</b></td>
 134       </tr>
 135
 136       <tr>
 137         <td>
 138           <pre>
 139 <a href="#Node_Update841554648"><tt>Node_Update</tt></a>
 140 </pre>
 141         </td>
 142
 143         <td>
 144           <p>public</p>
 145         </td>
 146       </tr>
 147
 148       <tr>
 149         <td>
 150           <pre>
 151 <a href="container_base.html"><span class=
 152 "c2"><tt>container_base</tt></span></a>
 153 </pre>
 154         </td>
 155
 156         <td>
 157           <p>public</p>
 158         </td>
 159       </tr>
 160     </table>
 161
 162     <h2><a name="link3" id="link3">Public Types and
 163     Constants</a></h2>
 164
 165     <h3><a name="link4" id="link4">Key-Type Definitions</a></h3>
 166
 167     <table class="c1" width="100%" border="1" summary="Types">
 168       <tr>
 169         <td width="30%" align="left"><b>Type</b></td>
 170
 171         <td width="55%" align="left"><b>Definition</b></td>
 172
 173         <td width="15%" align="left"><b>Description</b></td>
 174       </tr>
 175
 176       <tr>
 177         <td>
 178           <pre>
 179 <a name="const_key_reference3185471705" id=
 180 "const_key_reference3185471705">const_key_reference</a>
 181 </pre>
 182         </td>
 183
 184         <td>
 185           <pre>
 186 <b>typename</b> <a href="container_base.html"><span class=
 187 "c2"><tt>container_base</tt></span></a>::const_key_reference
 188 </pre>
 189         </td>
 190
 191         <td>
 192           <p>Const key reference type.</p>
 193         </td>
 194       </tr>
 195     </table>
 196
 197     <h3><a name="link5" id="link5">Policy Definitions</a></h3>
 198
 199     <table class="c1" width="100%" border="1" summary="Types">
 200       <tr>
 201         <td width="30%" align="left"><b>Type</b></td>
 202
 203         <td width="55%" align="left"><b>Definition</b></td>
 204
 205         <td width="15%" align="left"><b>Description</b></td>
 206       </tr>
 207
 208       <tr>
 209         <td>
 210           <pre>
 211 <a name="node_update2404554648" id=
 212 "node_update2404554648">node_update</a>
 213 </pre>
 214         </td>
 215
 216         <td>
 217           <pre>
 218 <a href="#Node_Update841554648"><tt>Node_Update</tt></a>
 219 </pre>
 220         </td>
 221
 222         <td>
 223           <p>Node updater type.</p>
 224         </td>
 225       </tr>
 226     </table>
 227
 228     <h3><a name="link6" id="link6">Iterator Definitions</a></h3>
 229
 230     <table class="c1" width="100%" border="1" summary="Types">
 231       <tr>
 232         <td width="30%" align="left"><b>Type</b></td>
 233
 234         <td width="55%" align="left"><b>Definition</b></td>
 235
 236         <td width="15%" align="left"><b>Description</b></td>
 237       </tr>
 238
 239       <tr>
 240         <td>
 241           <pre>
 242 <a name="const_iterator98626788" id=
 243 "const_iterator98626788">const_iterator</a>
 244 </pre>
 245         </td>
 246
 247         <td>
 248           <pre>
 249 <b>typename</b> <a href="container_base.html"><span class=
 250 "c2"><tt>container_base</tt></span></a>::const_iterator
 251 </pre>
 252         </td>
 253
 254         <td>
 255           <p>Const range-type iterator.</p>
 256         </td>
 257       </tr>
 258
 259       <tr>
 260         <td>
 261           <pre>
 262 <a name="iterator10418194" id="iterator10418194">iterator</a>
 263 </pre>
 264         </td>
 265
 266         <td>
 267           <pre>
 268 <b>typename</b> <a href="container_base.html"><span class=
 269 "c2"><tt>container_base</tt></span></a>::iterator
 270 </pre>
 271         </td>
 272
 273         <td>
 274           <p>Range-type iterator.</p>
 275         </td>
 276       </tr>
 277
 278       <tr>
 279         <td>
 280           <pre>
 281 <a name="const_reverse_iterator4151293083" id=
 282 "const_reverse_iterator4151293083">const_reverse_iterator</a>
 283 </pre>
 284         </td>
 285
 286         <td>
 287           <pre>
 288 Const reverse range-type iterator.
 289 </pre>
 290         </td>
 291
 292         <td>
 293           <p>Const reverse range-type <a href=
 294           "#iterator10418194"><tt>iterator</tt></a>.</p>
 295         </td>
 296       </tr>
 297
 298       <tr>
 299         <td>
 300           <pre>
 301 <a name="reverse_iterator1896910345" id=
 302 "reverse_iterator1896910345">reverse_iterator</a>
 303 </pre>
 304         </td>
 305
 306         <td>
 307           <pre>
 308 Reverse range-type iterator.<br />
 309 If <a href="#Mapped318655"><tt>Mapped</tt></a> is <a href=
 310 "null_mapped_type.html"><span class=
 311 "c2"><tt>null_mapped_type</tt></span></a>, then this is synonymous to <a href="#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
 312 </pre>
 313         </td>
 314
 315         <td>
 316           <p>Reverse range-type <a href=
 317           "#iterator10418194"><tt>iterator</tt></a>.</p>
 318         </td>
 319       </tr>
 320     </table>
 321
 322     <h2><a name="link7" id="link7">Public Methods</a></h2>
 323
 324     <h3><a name="link8" id="link8">Constructors, Destructor, and
 325     Related</a></h3>
 326
 327     <table class="c1" width="100%" border="1" summary="Methods">
 328       <tr>
 329         <td width="45%" align="left"><b>Method</b></td>
 330
 331         <td width="55%" align="left"><b>Description</b></td>
 332       </tr>
 333
 334       <tr>
 335         <td>
 336           <pre>
 337 <b>virtual</b>
 338   ~basic_tree
 339   ()
 340 </pre>
 341         </td>
 342
 343         <td>
 344           <p>Destructor.</p>
 345         </td>
 346       </tr>
 347     </table>
 348
 349     <h3><a name="link9" id="link9">Policy Access Methods</a></h3>
 350
 351     <table class="c1" width="100%" border="1" summary="Methods">
 352       <tr>
 353         <td width="45%" align="left"><b>Method</b></td>
 354
 355         <td width="55%" align="left"><b>Description</b></td>
 356       </tr>
 357
 358       <tr>
 359         <td>
 360           <pre>
 361 <a href="#node_update2404554648"><tt>node_update</tt></a> &amp;
 362   get_node_update
 363   ()
 364 </pre>
 365         </td>
 366
 367         <td>
 368           <p>Access to the <a href=
 369           "#node_update2404554648"><tt>node_update</tt></a>
 370           object.</p>
 371         </td>
 372       </tr>
 373
 374       <tr>
 375         <td>
 376           <pre>
 377 <b>const</b> <a href=
 378 "#node_update2404554648"><tt>node_update</tt></a> &amp;
 379   get_node_update
 380   () <b>const</b>
 381 </pre>
 382         </td>
 383
 384         <td>
 385           <p>Const access to the <a href=
 386           "#node_update2404554648"><tt>node_update</tt></a>
 387           object.</p>
 388         </td>
 389       </tr>
 390     </table>
 391
 392     <h3><a name="link10" id="link10">Find Methods</a></h3>
 393
 394     <table class="c1" width="100%" border="1" summary="Methods">
 395       <tr>
 396         <td width="45%" align="left"><b>Method</b></td>
 397
 398         <td width="55%" align="left"><b>Description</b></td>
 399       </tr>
 400
 401       <tr>
 402         <td>
 403           <pre>
 404 <a href="#iterator10418194"><tt>iterator</tt></a>
 405   lower_bound
 406   (<a href=
 407 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
 408 </pre>
 409         </td>
 410
 411         <td>
 412           <p>Returns an <a href=
 413           "#iterator10418194"><tt>iterator</tt></a> corresponding
 414           to the entry whose key is the smallest one at least as
 415           large as <span class="c1"><tt>r_key</tt></span>.</p>
 416         </td>
 417       </tr>
 418
 419       <tr>
 420         <td>
 421           <pre>
 422 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>
 423   lower_bound
 424   (<a href=
 425 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
 426 </pre>
 427         </td>
 428
 429         <td>
 430           <p>Returns a <tt><b>const</b></tt> <a href=
 431           "#iterator10418194"><tt>iterator</tt></a> corresponding
 432           to the entry whose key is the smallest one at least as
 433           large as <span class="c1"><tt>r_key</tt></span>.</p>
 434         </td>
 435       </tr>
 436
 437       <tr>
 438         <td>
 439           <pre>
 440 <a href="#iterator10418194"><tt>iterator</tt></a>
 441   upper_bound
 442   (<a href=
 443 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
 444 </pre>
 445         </td>
 446
 447         <td>
 448           <p>Returns an <a href=
 449           "#iterator10418194"><tt>iterator</tt></a> corresponding
 450           to the entry whose key is the smallest one larger than
 451           <span class="c1"><tt>r_key</tt></span>.</p>
 452         </td>
 453       </tr>
 454
 455       <tr>
 456         <td>
 457           <pre>
 458 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>
 459   upper_bound
 460   (<a href=
 461 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
 462 </pre>
 463         </td>
 464
 465         <td>
 466           <p>Returns a <a href=
 467           "#const_iterator98626788"><tt>const_iterator</tt></a>
 468           corresponding to the entry whose key is the smallest one
 469           larger than <span class="c1"><tt>r_key</tt></span>.</p>
 470         </td>
 471       </tr>
 472     </table>
 473
 474     <h3><a name="link11" id="link11">Erase Methods</a></h3>
 475
 476     <table class="c1" width="100%" border="1" summary="Methods">
 477       <tr>
 478         <td width="45%" align="left"><b>Method</b></td>
 479
 480         <td width="55%" align="left"><b>Description</b></td>
 481       </tr>
 482
 483       <tr>
 484         <td>
 485           <pre>
 486 <a href="#iterator10418194"><tt>iterator</tt></a>
 487   erase
 488   (<a href="#iterator10418194"><tt>iterator</tt></a> it)
 489 </pre>
 490         </td>
 491
 492         <td>
 493           <p>Erases the value_type corresponding to the <a href=
 494           "#iterator10418194"><tt>iterator</tt></a> <span class=
 495           "c1"><tt>it</tt></span>. Returns the <a href=
 496           "#iterator10418194"><tt>iterator</tt></a> corresponding
 497           to the next value_type.</p>
 498         </td>
 499       </tr>
 500
 501       <tr>
 502         <td>
 503           <pre>
 504 <a href="#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
 505   erase
 506   (<a href=
 507 "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a> it)
 508 </pre>
 509         </td>
 510
 511         <td>
 512           <p>Erases the value_type corresponding to the <a href=
 513           "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
 514           <span class="c1"><tt>it</tt></span>. Returns the <a href=
 515           "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
 516           corresponding to the previous value_type.</p>
 517         </td>
 518       </tr>
 519     </table>
 520
 521     <h3><a name="link12" id="link12">Iteration Methods</a></h3>
 522
 523     <table class="c1" width="100%" border="1" summary="Methods">
 524       <tr>
 525         <td width="45%" align="left"><b>Method</b></td>
 526
 527         <td width="55%" align="left"><b>Description</b></td>
 528       </tr>
 529
 530       <tr>
 531         <td>
 532           <pre>
 533 <a href="#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
 534   rbegin
 535   ()
 536 </pre>
 537         </td>
 538
 539         <td>
 540           <p>Returns a <a href=
 541           "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
 542           corresponding to the last value_type in the
 543           container.</p>
 544         </td>
 545       </tr>
 546
 547       <tr>
 548         <td>
 549           <pre>
 550 <a href=
 551 "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
 552   rbegin
 553   () <b>const</b>
 554 </pre>
 555         </td>
 556
 557         <td>
 558           <p>Returns a <a href=
 559           "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
 560           corresponding to the last value_type in the
 561           container.</p>
 562         </td>
 563       </tr>
 564
 565       <tr>
 566         <td>
 567           <pre>
 568 <a href="#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
 569   rend
 570   ()
 571 </pre>
 572         </td>
 573
 574         <td>
 575           <p>Returns a <a href=
 576           "#reverse_iterator1896910345"><tt>reverse_iterator</tt></a>
 577           corresponding to the just-before-first value_type in the
 578           container.</p>
 579         </td>
 580       </tr>
 581
 582       <tr>
 583         <td>
 584           <pre>
 585 <a href=
 586 "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
 587   rend
 588   () <b>const</b>
 589 </pre>
 590         </td>
 591
 592         <td>
 593           <p>Returns a <a href=
 594           "#const_reverse_iterator4151293083"><tt>const_reverse_iterator</tt></a>
 595           corresponding to the just-before-first value_type in the
 596           container.</p>
 597         </td>
 598       </tr>
 599     </table>
 600
 601     <h3><a name="link13" id="link13">Split and join
 602     Methods</a></h3>
 603
 604     <table class="c1" width="100%" border="1" summary="Methods">
 605       <tr>
 606         <td width="45%" align="left"><b>Method</b></td>
 607
 608         <td width="55%" align="left"><b>Description</b></td>
 609       </tr>
 610
 611       <tr>
 612         <td>
 613           <pre>
 614 <b>void</b>
 615   join
 616   (<span class=
 617 "c2"><tt>basic_tree</tt></span> &amp;other)
 618 </pre>
 619         </td>
 620
 621         <td>
 622           <p>Joins two trees. When this function returns,
 623           <span class="c1"><tt>other</tt></span> will be
 624           empty.</p>
 625
 626           <p>When calling this method, <span class=
 627           "c1"><tt>other</tt></span>'s keys must be all larger or
 628           all smaller than this object's keys, and <span class=
 629           "c1"><tt>other</tt></span>'s policies must be
 630           equivalent to this object's policies.</p>
 631         </td>
 632       </tr>
 633
 634       <tr>
 635         <td>
 636           <pre>
 637 <b>void</b>
 638   split
 639   (<a href=
 640 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key,
 641     <span class=
 642 "c2"><tt>basic_tree</tt></span> &amp;other)
 643 </pre>
 644         </td>
 645
 646         <td>
 647           <p>Splits into two trees. When this function returns,
 648           <span class="c1"><tt>other</tt></span> will contain
 649           only keys larger than <span class=
 650           "c1"><tt>r_key</tt></span>.</p>
 651
 652           <p>When calling this method, <span class=
 653           "c1"><tt>other</tt></span>'s policies must be
 654           equivalent to this object's policies.</p>
 655         </td>
 656       </tr>
 657     </table>
 658   </div>
 659 </body>
 660 </html>