libstdc++-v3/docs/html/ext/pb_ds/trie_order_statistics_node_update.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>trie_order_statistics_node_update 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>trie_order_statistics_node_update</tt> Interface</h1>
  17
  18     <p>Functor updating ranks of entrees.</p>
  19
  20     <p>Defined in: <a href=
  21     "../../../../include/ext/pb_ds/trie_policy.hpp"><tt>trie_policy.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="Const_Node_Iterator1933878761" id=
  39 "Const_Node_Iterator1933878761"><b>class</b> Const_Node_Iterator</a>
  40 </pre>
  41         </td>
  42
  43         <td>
  44           <p>Const node iterator type.</p>
  45         </td>
  46
  47         <td>-</td>
  48       </tr>
  49
  50       <tr>
  51         <td>
  52           <pre>
  53 <a name="Node_Iterator4206909839" id=
  54 "Node_Iterator4206909839"><b>class</b> Node_Iterator</a>
  55 </pre>
  56         </td>
  57
  58         <td>
  59           <p>Node iterator type.</p>
  60         </td>
  61
  62         <td>-</td>
  63       </tr>
  64
  65       <tr>
  66         <td>
  67           <pre>
  68 <a name="E_Access_Traits686553840" id=
  69 "E_Access_Traits686553840"><b>class</b> E_Access_Traits</a>
  70 </pre>
  71         </td>
  72
  73         <td>
  74           <p>Comparison functor.</p>
  75         </td>
  76
  77         <td>-</td>
  78       </tr>
  79
  80       <tr>
  81         <td>
  82           <pre>
  83 <a name="Allocator35940069" id=
  84 "Allocator35940069"><b>class</b> Allocator</a>
  85 </pre>
  86         </td>
  87
  88         <td>
  89           <p>Allocator type.</p>
  90         </td>
  91
  92         <td>-</td>
  93       </tr>
  94     </table>
  95
  96     <h2><a name="link2" id="link2">Public Types and
  97     Constants</a></h2>
  98
  99     <h3><a name="link3" id="link3">Policy Definitions</a></h3>
 100
 101     <table class="c1" width="100%" border="1" summary="Types">
 102       <tr>
 103         <td width="30%" align="left"><b>Type</b></td>
 104
 105         <td width="55%" align="left"><b>Definition</b></td>
 106
 107         <td width="15%" align="left"><b>Description</b></td>
 108       </tr>
 109
 110       <tr>
 111         <td>
 112           <pre>
 113 <a name="e_access_traits1948190928" id=
 114 "e_access_traits1948190928">e_access_traits</a>
 115 </pre>
 116         </td>
 117
 118         <td>
 119           <pre>
 120 <a href="#E_Access_Traits686553840"><tt>E_Access_Traits</tt></a>
 121 </pre>
 122         </td>
 123
 124         <td>
 125           <p>Element access traits.</p>
 126         </td>
 127       </tr>
 128
 129       <tr>
 130         <td>
 131           <pre>
 132 <a name="const_e_iterator2450008044" id=
 133 "const_e_iterator2450008044">const_e_iterator</a>
 134 </pre>
 135         </td>
 136
 137         <td>
 138           <pre>
 139 <b>typename</b> <a href=
 140 "#e_access_traits1948190928"><tt>e_access_traits</tt></a>::const_iterator
 141 </pre>
 142         </td>
 143
 144         <td>
 145           <p>Const element iterator.</p>
 146         </td>
 147       </tr>
 148
 149       <tr>
 150         <td>
 151           <pre>
 152 <a name="allocator48440069" id="allocator48440069">allocator</a>
 153 </pre>
 154         </td>
 155
 156         <td>
 157           <pre>
 158 <a href="#Allocator35940069"><tt>Allocator</tt></a>
 159 </pre>
 160         </td>
 161
 162         <td>
 163           <p><a href="#Allocator35940069"><tt>Allocator</tt></a>
 164           type.</p>
 165         </td>
 166       </tr>
 167     </table>
 168
 169     <h3><a name="link4" id="link4">General Definitions</a></h3>
 170
 171     <table class="c1" width="100%" border="1" summary="Types">
 172       <tr>
 173         <td width="30%" align="left"><b>Type</b></td>
 174
 175         <td width="55%" align="left"><b>Definition</b></td>
 176
 177         <td width="15%" align="left"><b>Description</b></td>
 178       </tr>
 179
 180       <tr>
 181         <td>
 182           <pre>
 183 <a name="size_type55424436" id="size_type55424436">size_type</a>
 184 </pre>
 185         </td>
 186
 187         <td>
 188           <pre>
 189 <b>typename</b> <a href=
 190 "#allocator48440069"><tt>allocator</tt></a>::size_type
 191 </pre>
 192         </td>
 193
 194         <td>
 195           <p>Size type.</p>
 196         </td>
 197       </tr>
 198     </table>
 199
 200     <h3><a name="link5" id="link5">Key-Type Definitions</a></h3>
 201
 202     <table class="c1" width="100%" border="1" summary="Types">
 203       <tr>
 204         <td width="30%" align="left"><b>Type</b></td>
 205
 206         <td width="55%" align="left"><b>Definition</b></td>
 207
 208         <td width="15%" align="left"><b>Description</b></td>
 209       </tr>
 210
 211       <tr>
 212         <td>
 213           <pre>
 214 <a name="key_type10393186" id="key_type10393186">key_type</a>
 215 </pre>
 216         </td>
 217
 218         <td>
 219           <pre>
 220 The instantiating container's key type.
 221 </pre>
 222         </td>
 223
 224         <td>
 225           <p>Key type.</p>
 226         </td>
 227       </tr>
 228
 229       <tr>
 230         <td>
 231           <pre>
 232 <a name="const_key_reference3185471705" id=
 233 "const_key_reference3185471705">const_key_reference</a>
 234 </pre>
 235         </td>
 236
 237         <td>
 238           <pre>
 239 The instantiating container's const key reference type.
 240 </pre>
 241         </td>
 242
 243         <td>
 244           <p>Const key reference.</p>
 245         </td>
 246       </tr>
 247     </table>
 248
 249     <h3><a name="link6" id="link6">Metadata-Type
 250     Definitions</a></h3>
 251
 252     <table class="c1" width="100%" border="1" summary="Types">
 253       <tr>
 254         <td width="30%" align="left"><b>Type</b></td>
 255
 256         <td width="55%" align="left"><b>Definition</b></td>
 257
 258         <td width="15%" align="left"><b>Description</b></td>
 259       </tr>
 260
 261       <tr>
 262         <td>
 263           <pre>
 264 <a name="metadata_type2849297114" id=
 265 "metadata_type2849297114">metadata_type</a>
 266 </pre>
 267         </td>
 268
 269         <td>
 270           <pre>
 271 <a href="#size_type55424436"><tt>size_type</tt></a>
 272 </pre>
 273         </td>
 274
 275         <td>
 276           <p>Metadata type.</p>
 277         </td>
 278       </tr>
 279     </table>
 280
 281     <h3><a name="link7" id="link7">Iterator Definitions</a></h3>
 282
 283     <table class="c1" width="100%" border="1" summary="Types">
 284       <tr>
 285         <td width="30%" align="left"><b>Type</b></td>
 286
 287         <td width="55%" align="left"><b>Definition</b></td>
 288
 289         <td width="15%" align="left"><b>Description</b></td>
 290       </tr>
 291
 292       <tr>
 293         <td>
 294           <pre>
 295 <a name="const_node_iterator4205924553" id=
 296 "const_node_iterator4205924553">const_node_iterator</a>
 297 </pre>
 298         </td>
 299
 300         <td>
 301           <pre>
 302 <a href=
 303 "#Const_Node_Iterator1933878761"><tt>Const_Node_Iterator</tt></a>
 304 </pre>
 305         </td>
 306
 307         <td>
 308           <p>Const node iterator type.</p>
 309         </td>
 310       </tr>
 311
 312       <tr>
 313         <td>
 314           <pre>
 315 <a name="node_iterator3431975247" id=
 316 "node_iterator3431975247">node_iterator</a>
 317 </pre>
 318         </td>
 319
 320         <td>
 321           <pre>
 322 <a href="#Node_Iterator4206909839"><tt>Node_Iterator</tt></a>
 323 </pre>
 324         </td>
 325
 326         <td>
 327           <p>Node iterator type.</p>
 328         </td>
 329       </tr>
 330
 331       <tr>
 332         <td>
 333           <pre>
 334 <a name="const_iterator98626788" id=
 335 "const_iterator98626788">const_iterator</a>
 336 </pre>
 337         </td>
 338
 339         <td>
 340           <pre>
 341 <b>typename</b> <a href=
 342 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>::value_type
 343 </pre>
 344         </td>
 345
 346         <td>
 347           <p>Const iterator type.</p>
 348         </td>
 349       </tr>
 350
 351       <tr>
 352         <td>
 353           <pre>
 354 <a name="iterator10418194" id="iterator10418194">iterator</a>
 355 </pre>
 356         </td>
 357
 358         <td>
 359           <pre>
 360 <b>typename</b> <a href=
 361 "#node_iterator3431975247"><tt>node_iterator</tt></a>::value_type
 362 </pre>
 363         </td>
 364
 365         <td>
 366           <p>Iterator type.</p>
 367         </td>
 368       </tr>
 369     </table>
 370
 371     <h2><a name="link8" id="link8">Public Methods</a></h2>
 372
 373     <h3><a name="link9" id="link9">Find-Type Methods</a></h3>
 374
 375     <table class="c1" width="100%" border="1" summary="Methods">
 376       <tr>
 377         <td width="45%" align="left"><b>Method</b></td>
 378
 379         <td width="55%" align="left"><b>Description</b></td>
 380       </tr>
 381
 382       <tr>
 383         <td>
 384           <pre>
 385 <b>inline</b> <a href=
 386 "#const_iterator98626788"><tt>const_iterator</tt></a>
 387   find_by_order
 388   (<a href=
 389 "#size_type55424436"><tt>size_type</tt></a> order) <b>const</b>
 390 </pre>
 391         </td>
 392
 393         <td>
 394           <p>Finds an entry by order. Returns a <a href=
 395           "#const_iterator98626788"><tt>const_iterator</tt></a> to
 396           the entry with the order <span class=
 397           "c1"><tt>order</tt></span>, or a <a href=
 398           "#const_iterator98626788"><tt>const_iterator</tt></a> to
 399           the container object's end if <span class=
 400           "c1"><tt>order</tt></span> is at least the size of the
 401           container object.</p>
 402         </td>
 403       </tr>
 404
 405       <tr>
 406         <td>
 407           <pre>
 408 <b>inline</b> <a href="#iterator10418194"><tt>iterator</tt></a>
 409   find_by_order
 410   (<a href="#size_type55424436"><tt>size_type</tt></a> order)
 411 </pre>
 412         </td>
 413
 414         <td>
 415           <p>Finds an entry by order. Returns an <a href=
 416           "#iterator10418194"><tt>iterator</tt></a> to the entry
 417           with the order <span class="c1"><tt>order</tt></span>, or
 418           an <a href="#iterator10418194"><tt>iterator</tt></a> to
 419           the container object's end if <span class=
 420           "c1"><tt>order</tt></span> is at least the size of the
 421           container object.</p>
 422         </td>
 423       </tr>
 424
 425       <tr>
 426         <td>
 427           <pre>
 428 <b>inline</b> <a href="#size_type55424436"><tt>size_type</tt></a>
 429   order_of_key
 430   (<a href=
 431 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
 432 </pre>
 433         </td>
 434
 435         <td>
 436           <p>Returns the order of a key within a sequence. For
 437           example, if <span class="c1"><tt>r_key</tt></span> is the
 438           smallest key, this method will return 0; if <span class=
 439           "c1"><tt>r_key</tt></span> is a key between the smallest
 440           and next key, this method will return 1; if <span class=
 441           "c1"><tt>r_key</tt></span> is a key larger than the
 442           largest key, this method will return the size of r_c.</p>
 443         </td>
 444       </tr>
 445
 446       <tr>
 447         <td>
 448           <pre>
 449 <b>inline</b> <a href="#size_type55424436"><tt>size_type</tt></a>
 450   order_of_prefix
 451   (<a href=
 452 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> b,
 453     <a href=
 454 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> e) <b>const</b>
 455 </pre>
 456         </td>
 457
 458         <td>
 459           <p>Returns the order of a prefix within a sequence. For
 460           <span class="c1"><tt>e</tt></span>example, if [b,
 461           <span class="c1"><tt>e</tt></span>] is the smallest
 462           prefix, this method will return 0; if r_key is a key
 463           <span class="c1"><tt>b</tt></span>between the smallest and
 464           next key, this method will return 1; if r_key is a key
 465           larger than the largest key, this method will return the
 466           size of r_c.</p>
 467         </td>
 468       </tr>
 469     </table>
 470
 471     <h2><a name="link10" id="link10">Protected Types and
 472     Constants</a></h2>
 473
 474     <h3><a name="link11" id="link11">Value-Type
 475     Definitions</a></h3>
 476
 477     <table class="c1" width="100%" border="1" summary="Types">
 478       <tr>
 479         <td width="30%" align="left"><b>Type</b></td>
 480
 481         <td width="55%" align="left"><b>Definition</b></td>
 482
 483         <td width="15%" align="left"><b>Description</b></td>
 484       </tr>
 485
 486       <tr>
 487         <td>
 488           <pre>
 489 <a name="const_reference495461441" id=
 490 "const_reference495461441">const_reference</a>
 491 </pre>
 492         </td>
 493
 494         <td>
 495           <pre>
 496 The instantiating container's const reference  type.
 497 </pre>
 498         </td>
 499
 500         <td>
 501           <p>Const reference to the container's value-type.</p>
 502         </td>
 503       </tr>
 504
 505       <tr>
 506         <td>
 507           <pre>
 508 <a name="const_pointer878814947" id=
 509 "const_pointer878814947">const_pointer</a>
 510 </pre>
 511         </td>
 512
 513         <td>
 514           <pre>
 515 The instantiating container's const pointer  type.
 516 </pre>
 517         </td>
 518
 519         <td>
 520           <p>Const pointer to the container's value-type.</p>
 521         </td>
 522       </tr>
 523
 524       <tr>
 525         <td>
 526           <pre>
 527 <a name="const_metadata_reference1108857465" id=
 528 "const_metadata_reference1108857465">const_metadata_reference</a>
 529 </pre>
 530         </td>
 531
 532         <td>
 533           <pre>
 534 <b>typename</b> <a href=
 535 "#Allocator35940069"><tt>Allocator</tt></a>::<b>template</b> rebind&lt;
 536     <a href=
 537 "#metadata_type2849297114"><tt>metadata_type</tt></a>&gt;::other::<a href="#const_reference495461441"><tt>const_reference</tt></a>
 538 </pre>
 539         </td>
 540
 541         <td>
 542           <p>Const metadata reference.</p>
 543         </td>
 544       </tr>
 545
 546       <tr>
 547         <td>
 548           <pre>
 549 <a name="metadata_reference583863863" id=
 550 "metadata_reference583863863">metadata_reference</a>
 551 </pre>
 552         </td>
 553
 554         <td>
 555           <pre>
 556 <b>typename</b> <a href=
 557 "#Allocator35940069"><tt>Allocator</tt></a>::<b>template</b> rebind&lt;
 558     <a href=
 559 "#metadata_type2849297114"><tt>metadata_type</tt></a>&gt;::other::reference
 560 </pre>
 561         </td>
 562
 563         <td>
 564           <p>Metadata reference.</p>
 565         </td>
 566       </tr>
 567     </table>
 568
 569     <h2><a name="link12" id="link12">Protected Methods</a></h2>
 570
 571     <h3><a name="link13" id="link13">Operators</a></h3>
 572
 573     <table class="c1" width="100%" border="1" summary="Methods">
 574       <tr>
 575         <td width="45%" align="left"><b>Method</b></td>
 576
 577         <td width="55%" align="left"><b>Description</b></td>
 578       </tr>
 579
 580       <tr>
 581         <td>
 582           <pre>
 583 <b>inline</b> <b>void</b>
 584   <b>operator</b>()
 585   (<a href=
 586 "#node_iterator3431975247"><tt>node_iterator</tt></a> node_it,
 587     <a href=
 588 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a> end_nd_it) <b>const</b>
 589 </pre>
 590         </td>
 591
 592         <td>
 593           <p>Updates the rank of a node through a <a href=
 594           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 595           <span class="c1"><tt>node_it</tt></span>; <span class=
 596           "c1"><tt>end_nd_it</tt></span> is the end node <a href=
 597           "#iterator10418194"><tt>iterator</tt></a>.</p>
 598         </td>
 599       </tr>
 600     </table>
 601
 602     <h3><a name="link14" id="link14">Constructors, destructor, and
 603     related</a></h3>
 604
 605     <table class="c1" width="100%" border="1" summary="Methods">
 606       <tr>
 607         <td width="45%" align="left"><b>Method</b></td>
 608
 609         <td width="55%" align="left"><b>Description</b></td>
 610       </tr>
 611
 612       <tr>
 613         <td>
 614           <pre>
 615 <b>virtual</b>
 616   ~trie_order_statistics_node_update
 617   ()
 618 </pre>
 619         </td>
 620
 621         <td>
 622           <p>Destructor.</p>
 623         </td>
 624       </tr>
 625     </table>
 626
 627     <h2><a name="link15" id="link15">Private Methods</a></h2>
 628
 629     <h3><a name="link16" id="link16">Overrides</a></h3>
 630
 631     <table class="c1" width="100%" border="1" summary="Methods">
 632       <tr>
 633         <td width="45%" align="left"><b>Method</b></td>
 634
 635         <td width="55%" align="left"><b>Description</b></td>
 636       </tr>
 637
 638       <tr>
 639         <td>
 640           <pre>
 641 <b>virtual</b> <b>bool</b>
 642   empty
 643   () <b>const</b> = 0
 644 </pre>
 645         </td>
 646
 647         <td>
 648           <p>Returns <tt><b>true</b></tt> if the container is
 649           empty.</p>
 650         </td>
 651       </tr>
 652
 653       <tr>
 654         <td>
 655           <pre>
 656 <b>virtual</b> <a href="#iterator10418194"><tt>iterator</tt></a>
 657   begin
 658   () = 0
 659 </pre>
 660         </td>
 661
 662         <td>
 663           <p>Returns the <a href=
 664           "#iterator10418194"><tt>iterator</tt></a> associated with
 665           the trie's first element.</p>
 666         </td>
 667       </tr>
 668
 669       <tr>
 670         <td>
 671           <pre>
 672 <b>virtual</b> <a href="#iterator10418194"><tt>iterator</tt></a>
 673   end
 674   () = 0
 675 </pre>
 676         </td>
 677
 678         <td>
 679           <p>Returns the <a href=
 680           "#iterator10418194"><tt>iterator</tt></a> associated with
 681           the trie's just-after-last element.</p>
 682         </td>
 683       </tr>
 684
 685       <tr>
 686         <td>
 687           <pre>
 688 <b>virtual</b> <a href=
 689 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 690   node_begin
 691   () <b>const</b> = 0
 692 </pre>
 693         </td>
 694
 695         <td>
 696           <p>Returns the <a href=
 697           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 698           associated with the trie's root node.</p>
 699         </td>
 700       </tr>
 701
 702       <tr>
 703         <td>
 704           <pre>
 705 <b>virtual</b> <a href=
 706 "#node_iterator3431975247"><tt>node_iterator</tt></a>
 707   node_begin
 708   () = 0
 709 </pre>
 710         </td>
 711
 712         <td>
 713           <p>Returns the <a href=
 714           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 715           associated with the trie's root node.</p>
 716         </td>
 717       </tr>
 718
 719       <tr>
 720         <td>
 721           <pre>
 722 <b>virtual</b> <a href=
 723 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 724   node_end
 725   () <b>const</b> = 0
 726 </pre>
 727         </td>
 728
 729         <td>
 730           <p>Returns the <a href=
 731           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 732           associated with a just-after leaf node.</p>
 733         </td>
 734       </tr>
 735
 736       <tr>
 737         <td>
 738           <pre>
 739 <b>virtual</b> <a href=
 740 "#node_iterator3431975247"><tt>node_iterator</tt></a>
 741   node_end
 742   () = 0
 743 </pre>
 744         </td>
 745
 746         <td>
 747           <p>Returns the <a href=
 748           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 749           associated with a just-after leaf node.</p>
 750         </td>
 751       </tr>
 752
 753       <tr>
 754         <td>
 755           <pre>
 756 <b>virtual</b> <a href=
 757 "#e_access_traits1948190928"><tt>e_access_traits</tt></a> &amp;
 758   get_e_access_traits
 759   () = 0
 760 </pre>
 761         </td>
 762
 763         <td>
 764           <p>Access to the cmp_fn object.</p>
 765         </td>
 766       </tr>
 767     </table>
 768   </div>
 769 </body>
 770 </html>