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 "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/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> 220The 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> 239The 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> 496The 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> 515The 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< 536 <a href= 537"#metadata_type2849297114"><tt>metadata_type</tt></a>>::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< 558 <a href= 559"#metadata_type2849297114"><tt>metadata_type</tt></a>>::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> & 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> 771