libstdc++-v3/doc/html/ext/pb_ds/trie_prefix_search_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_prefix_search_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_prefix_search_node_update</tt> Interface</h1>
  17
  18     <p>A node updater that allows tries to be searched for the
  19     range of values that match a certain prefix.</p>
  20
  21     <p>Defined in: <a href=
  22     "../../../../include/ext/pb_ds/trie_policy.hpp"><tt>trie_policy.hpp</tt></a></p>
  23
  24     <h2><a name="link1" id="link1">Template Parameters</a></h2>
  25
  26     <table class="c1" width="100%" border="1" summary=
  27     "Template Parameters">
  28       <tr>
  29         <td width="20%" align="left"><b>Parameter</b></td>
  30
  31         <td width="50%" align="left"><b>Description</b></td>
  32
  33         <td width="30%" align="left"><b>Default Value</b></td>
  34       </tr>
  35
  36       <tr>
  37         <td>
  38           <pre>
  39 <a name="Const_Node_Iterator1933878761" id=
  40 "Const_Node_Iterator1933878761"><b>class</b> Const_Node_Iterator</a>
  41 </pre>
  42         </td>
  43
  44         <td>
  45           <p>Const node iterator type.</p>
  46         </td>
  47
  48         <td>-</td>
  49       </tr>
  50
  51       <tr>
  52         <td>
  53           <pre>
  54 <a name="Node_Iterator4206909839" id=
  55 "Node_Iterator4206909839"><b>class</b> Node_Iterator</a>
  56 </pre>
  57         </td>
  58
  59         <td>
  60           <p>Node iterator type.</p>
  61         </td>
  62
  63         <td>-</td>
  64       </tr>
  65
  66       <tr>
  67         <td>
  68           <pre>
  69 <a name="E_Access_Traits686553840" id=
  70 "E_Access_Traits686553840"><b>class</b> E_Access_Traits</a>
  71 </pre>
  72         </td>
  73
  74         <td>
  75           <p>Comparison functor.</p>
  76         </td>
  77
  78         <td>-</td>
  79       </tr>
  80
  81       <tr>
  82         <td>
  83           <pre>
  84 <a name="Allocator35940069" id=
  85 "Allocator35940069"><b>class</b> Allocator</a>
  86 </pre>
  87         </td>
  88
  89         <td>
  90           <p>Allocator type.</p>
  91         </td>
  92
  93         <td>-</td>
  94       </tr>
  95     </table>
  96
  97     <h2><a name="link2" id="link2">Public Types and
  98     Constants</a></h2>
  99
 100     <h3><a name="link3" id="link3">Key-Type Definitions</a></h3>
 101
 102     <table class="c1" width="100%" border="1" summary="Types">
 103       <tr>
 104         <td width="30%" align="left"><b>Type</b></td>
 105
 106         <td width="55%" align="left"><b>Definition</b></td>
 107
 108         <td width="15%" align="left"><b>Description</b></td>
 109       </tr>
 110
 111       <tr>
 112         <td>
 113           <pre>
 114 <a name="key_type10393186" id="key_type10393186">key_type</a>
 115 </pre>
 116         </td>
 117
 118         <td>
 119           <pre>
 120 The instantiating container's key type.
 121 </pre>
 122         </td>
 123
 124         <td>
 125           <p>Key type.</p>
 126         </td>
 127       </tr>
 128
 129       <tr>
 130         <td>
 131           <pre>
 132 <a name="const_key_reference3185471705" id=
 133 "const_key_reference3185471705">const_key_reference</a>
 134 </pre>
 135         </td>
 136
 137         <td>
 138           <pre>
 139 The instantiating container's const key reference type.
 140 </pre>
 141         </td>
 142
 143         <td>
 144           <p>Const key reference.</p>
 145         </td>
 146       </tr>
 147     </table>
 148
 149     <h3><a name="link4" id="link4">Policy Definitions</a></h3>
 150
 151     <table class="c1" width="100%" border="1" summary="Types">
 152       <tr>
 153         <td width="30%" align="left"><b>Type</b></td>
 154
 155         <td width="55%" align="left"><b>Definition</b></td>
 156
 157         <td width="15%" align="left"><b>Description</b></td>
 158       </tr>
 159
 160       <tr>
 161         <td>
 162           <pre>
 163 <a name="e_access_traits1948190928" id=
 164 "e_access_traits1948190928">e_access_traits</a>
 165 </pre>
 166         </td>
 167
 168         <td>
 169           <pre>
 170 <a href="#E_Access_Traits686553840"><tt>E_Access_Traits</tt></a>
 171 </pre>
 172         </td>
 173
 174         <td>
 175           <p>Element access traits.</p>
 176         </td>
 177       </tr>
 178
 179       <tr>
 180         <td>
 181           <pre>
 182 <a name="const_e_iterator2450008044" id=
 183 "const_e_iterator2450008044">const_e_iterator</a>
 184 </pre>
 185         </td>
 186
 187         <td>
 188           <pre>
 189 <b>typename</b> <a href=
 190 "#e_access_traits1948190928"><tt>e_access_traits</tt></a>::const_iterator
 191 </pre>
 192         </td>
 193
 194         <td>
 195           <p>Const element iterator.</p>
 196         </td>
 197       </tr>
 198
 199       <tr>
 200         <td>
 201           <pre>
 202 <a name="allocator48440069" id="allocator48440069">allocator</a>
 203 </pre>
 204         </td>
 205
 206         <td>
 207           <pre>
 208 <a href="#Allocator35940069"><tt>Allocator</tt></a>
 209 </pre>
 210         </td>
 211
 212         <td>
 213           <p><a href="#Allocator35940069"><tt>Allocator</tt></a>
 214           type.</p>
 215         </td>
 216       </tr>
 217     </table>
 218
 219     <h3><a name="link5" id="link5">General Definitions</a></h3>
 220
 221     <table class="c1" width="100%" border="1" summary="Types">
 222       <tr>
 223         <td width="30%" align="left"><b>Type</b></td>
 224
 225         <td width="55%" align="left"><b>Definition</b></td>
 226
 227         <td width="15%" align="left"><b>Description</b></td>
 228       </tr>
 229
 230       <tr>
 231         <td>
 232           <pre>
 233 <a name="size_type55424436" id="size_type55424436">size_type</a>
 234 </pre>
 235         </td>
 236
 237         <td>
 238           <pre>
 239 <b>typename</b> <a href=
 240 "#allocator48440069"><tt>allocator</tt></a>::size_type
 241 </pre>
 242         </td>
 243
 244         <td>
 245           <p>Size type.</p>
 246         </td>
 247       </tr>
 248     </table>
 249
 250     <h3><a name="link6" id="link6">Metadata-Type
 251     Definitions</a></h3>
 252
 253     <table class="c1" width="100%" border="1" summary="Types">
 254       <tr>
 255         <td width="30%" align="left"><b>Type</b></td>
 256
 257         <td width="55%" align="left"><b>Definition</b></td>
 258
 259         <td width="15%" align="left"><b>Description</b></td>
 260       </tr>
 261
 262       <tr>
 263         <td>
 264           <pre>
 265 <a name="metadata_type2849297114" id=
 266 "metadata_type2849297114">metadata_type</a>
 267 </pre>
 268         </td>
 269
 270         <td>
 271           <pre>
 272 __gnu_pbds::detail::null_node_metadata
 273 </pre>
 274         </td>
 275
 276         <td>
 277           <p>Metadata type.</p>
 278         </td>
 279       </tr>
 280     </table>
 281
 282     <h3><a name="link7" id="link7">Iterator Definitions</a></h3>
 283
 284     <table class="c1" width="100%" border="1" summary="Types">
 285       <tr>
 286         <td width="30%" align="left"><b>Type</b></td>
 287
 288         <td width="55%" align="left"><b>Definition</b></td>
 289
 290         <td width="15%" align="left"><b>Description</b></td>
 291       </tr>
 292
 293       <tr>
 294         <td>
 295           <pre>
 296 <a name="const_node_iterator4205924553" id=
 297 "const_node_iterator4205924553">const_node_iterator</a>
 298 </pre>
 299         </td>
 300
 301         <td>
 302           <pre>
 303 <a href=
 304 "#Const_Node_Iterator1933878761"><tt>Const_Node_Iterator</tt></a>
 305 </pre>
 306         </td>
 307
 308         <td>
 309           <p>Const node iterator type.</p>
 310         </td>
 311       </tr>
 312
 313       <tr>
 314         <td>
 315           <pre>
 316 <a name="node_iterator3431975247" id=
 317 "node_iterator3431975247">node_iterator</a>
 318 </pre>
 319         </td>
 320
 321         <td>
 322           <pre>
 323 <a href="#Node_Iterator4206909839"><tt>Node_Iterator</tt></a>
 324 </pre>
 325         </td>
 326
 327         <td>
 328           <p>Node iterator type.</p>
 329         </td>
 330       </tr>
 331
 332       <tr>
 333         <td>
 334           <pre>
 335 <a name="const_iterator98626788" id=
 336 "const_iterator98626788">const_iterator</a>
 337 </pre>
 338         </td>
 339
 340         <td>
 341           <pre>
 342 <b>typename</b> <a href=
 343 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>::value_type
 344 </pre>
 345         </td>
 346
 347         <td>
 348           <p>Const iterator type.</p>
 349         </td>
 350       </tr>
 351
 352       <tr>
 353         <td>
 354           <pre>
 355 <a name="iterator10418194" id="iterator10418194">iterator</a>
 356 </pre>
 357         </td>
 358
 359         <td>
 360           <pre>
 361 <b>typename</b> <a href=
 362 "#node_iterator3431975247"><tt>node_iterator</tt></a>::value_type
 363 </pre>
 364         </td>
 365
 366         <td>
 367           <p>Iterator type.</p>
 368         </td>
 369       </tr>
 370     </table>
 371
 372     <h2><a name="link8" id="link8">Public Methods</a></h2>
 373
 374     <h3><a name="link9" id="link9">Find Methods</a></h3>
 375
 376     <table class="c1" width="100%" border="1" summary="Methods">
 377       <tr>
 378         <td width="45%" align="left"><b>Method</b></td>
 379
 380         <td width="55%" align="left"><b>Description</b></td>
 381       </tr>
 382
 383       <tr>
 384         <td>
 385           <pre>
 386 std::pair&lt;
 387     <a href="#const_iterator98626788"><tt>const_iterator</tt></a>,
 388     <a href=
 389 "#const_iterator98626788"><tt>const_iterator</tt></a>&gt;
 390   prefix_range
 391   (<a href=
 392 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
 393 </pre>
 394         </td>
 395
 396         <td>
 397           <p>Finds the <tt><b>const</b></tt> <a href=
 398           "#iterator10418194"><tt>iterator</tt></a> range
 399           corresponding to all values whose prefixes match
 400           <span class="c1"><tt>r_key</tt></span>.</p>
 401         </td>
 402       </tr>
 403
 404       <tr>
 405         <td>
 406           <pre>
 407 std::pair&lt;
 408     <a href="#iterator10418194"><tt>iterator</tt></a>,
 409     <a href="#iterator10418194"><tt>iterator</tt></a>&gt;
 410   prefix_range
 411   (<a href=
 412 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
 413 </pre>
 414         </td>
 415
 416         <td>
 417           <p>Finds the <a href=
 418           "#iterator10418194"><tt>iterator</tt></a> range
 419           corresponding to all values whose prefixes match
 420           <span class="c1"><tt>r_key</tt></span>.</p>
 421         </td>
 422       </tr>
 423
 424       <tr>
 425         <td>
 426           <pre>
 427 std::pair&lt;
 428     <a href="#const_iterator98626788"><tt>const_iterator</tt></a>,
 429     <a href=
 430 "#const_iterator98626788"><tt>const_iterator</tt></a>&gt;
 431   prefix_range
 432   (<a href=
 433 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> b,
 434     <a href=
 435 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> e) <b>const</b>
 436 </pre>
 437         </td>
 438
 439         <td>
 440           <p>Finds the <tt><b>const</b></tt> <a href=
 441           "#iterator10418194"><tt>iterator</tt></a> range
 442           corresponding to all values whose prefixes match [b,
 443           <span class="c1"><tt>e</tt></span>).</p>
 444         </td>
 445       </tr>
 446
 447       <tr>
 448         <td>
 449           <pre>
 450 std::pair&lt;
 451     <a href="#iterator10418194"><tt>iterator</tt></a>,
 452     <a href="#iterator10418194"><tt>iterator</tt></a>&gt;
 453   prefix_range
 454   (<a href=
 455 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> b,
 456     <a href=
 457 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> e)
 458 </pre>
 459         </td>
 460
 461         <td>
 462           <p>Finds the <a href=
 463           "#iterator10418194"><tt>iterator</tt></a> range
 464           corresponding to all values whose prefixes match [b,
 465           <span class="c1"><tt>e</tt></span>).</p>
 466         </td>
 467       </tr>
 468     </table>
 469
 470     <h2><a name="link10" id="link10">Protected Methods</a></h2>
 471
 472     <h3><a name="link11" id="link11">Operators</a></h3>
 473
 474     <table class="c1" width="100%" border="1" summary="Methods">
 475       <tr>
 476         <td width="45%" align="left"><b>Method</b></td>
 477
 478         <td width="55%" align="left"><b>Description</b></td>
 479       </tr>
 480
 481       <tr>
 482         <td>
 483           <pre>
 484 <b>inline</b> <b>void</b>
 485   <b>operator</b>()
 486   (<a href=
 487 "#node_iterator3431975247"><tt>node_iterator</tt></a> node_it,
 488     <a href=
 489 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a> end_nd_it) <b>const</b>
 490 </pre>
 491         </td>
 492
 493         <td>
 494           <p>Called to update a node's metadata.</p>
 495         </td>
 496       </tr>
 497     </table>
 498
 499     <h2><a name="link12" id="link12">Private Methods</a></h2>
 500
 501     <h3><a name="link13" id="link13">Overrides</a></h3>
 502
 503     <table class="c1" width="100%" border="1" summary="Methods">
 504       <tr>
 505         <td width="45%" align="left"><b>Method</b></td>
 506
 507         <td width="55%" align="left"><b>Description</b></td>
 508       </tr>
 509
 510       <tr>
 511         <td>
 512           <pre>
 513 <b>virtual</b> <a href=
 514 "#const_iterator98626788"><tt>const_iterator</tt></a>
 515   end
 516   () <b>const</b> = 0
 517 </pre>
 518         </td>
 519
 520         <td>
 521           <p>Returns the <tt><b>const</b></tt> <a href=
 522           "#iterator10418194"><tt>iterator</tt></a> associated with
 523           the just-after last element.</p>
 524         </td>
 525       </tr>
 526
 527       <tr>
 528         <td>
 529           <pre>
 530 <b>virtual</b> <a href="#iterator10418194"><tt>iterator</tt></a>
 531   end
 532   () = 0
 533 </pre>
 534         </td>
 535
 536         <td>
 537           <p>Returns the <a href=
 538           "#iterator10418194"><tt>iterator</tt></a> associated with
 539           the just-after last element.</p>
 540         </td>
 541       </tr>
 542
 543       <tr>
 544         <td>
 545           <pre>
 546 <b>virtual</b> <a href=
 547 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 548   node_begin
 549   () <b>const</b> = 0
 550 </pre>
 551         </td>
 552
 553         <td>
 554           <p>Returns the <a href=
 555           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 556           associated with the trie's root node.</p>
 557         </td>
 558       </tr>
 559
 560       <tr>
 561         <td>
 562           <pre>
 563 <b>virtual</b> <a href=
 564 "#node_iterator3431975247"><tt>node_iterator</tt></a>
 565   node_begin
 566   () = 0
 567 </pre>
 568         </td>
 569
 570         <td>
 571           <p>Returns the <a href=
 572           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 573           associated with the trie's root node.</p>
 574         </td>
 575       </tr>
 576
 577       <tr>
 578         <td>
 579           <pre>
 580 <b>virtual</b> <a href=
 581 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 582   node_end
 583   () <b>const</b> = 0
 584 </pre>
 585         </td>
 586
 587         <td>
 588           <p>Returns the <a href=
 589           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 590           associated with a just-after leaf node.</p>
 591         </td>
 592       </tr>
 593
 594       <tr>
 595         <td>
 596           <pre>
 597 <b>virtual</b> <a href=
 598 "#node_iterator3431975247"><tt>node_iterator</tt></a>
 599   node_end
 600   () = 0
 601 </pre>
 602         </td>
 603
 604         <td>
 605           <p>Returns the <a href=
 606           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 607           associated with a just-after leaf node.</p>
 608         </td>
 609       </tr>
 610
 611       <tr>
 612         <td>
 613           <pre>
 614 <b>virtual</b> <b>const</b> <a href=
 615 "#e_access_traits1948190928"><tt>e_access_traits</tt></a> &amp;
 616   get_e_access_traits
 617   () <b>const</b> = 0
 618 </pre>
 619         </td>
 620
 621         <td>
 622           <p>Access to the cmp_fn object.</p>
 623         </td>
 624       </tr>
 625     </table>
 626   </div>
 627 </body>
 628 </html>