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 "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/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> 288Const 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> 308Reverse range-type iterator.<br /> 309If <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> & 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> & 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> &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> &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> 661