libstdc++-v3/docs/html/ext/pb_ds/trie.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 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</tt> Interface</h1>
  17
  18     <p>A concrete basic trie-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="E_Access_Traits686553840" id=
  67 "E_Access_Traits686553840"><b>class</b> E_Access_Traits </a>
  68 </pre>
  69         </td>
  70
  71         <td>
  72           <p>Element-access traits.</p>
  73         </td>
  74
  75         <td>-</td>
  76       </tr>
  77
  78       <tr>
  79         <td>
  80           <pre>
  81 <a name="Tag278938" id="Tag278938"><b>class</b> Tag </a>
  82 </pre>
  83         </td>
  84
  85         <td>
  86           <p>Data-structure tag.</p>
  87         </td>
  88
  89         <td><a href="pat_trie_tag.html"><span class=
  90         "c2"><tt>pat_trie_tag</tt></span></a></td>
  91       </tr>
  92
  93       <tr>
  94         <td>
  95           <pre>
  96 <a name="Node_Update841554648" id=
  97 "Node_Update841554648"><b>template</b>&lt;
  98   <b>typename</b> Const_Node_Iterator,
  99   <b>typename</b> Node_Iterator,
 100   <b>class</b> E_Access_Traits_,
 101   <b>typename</b> Allocator_&gt;
 102 <b>class</b> Node_Update </a>
 103 </pre>
 104         </td>
 105
 106         <td>
 107           <p>Node updater type.</p>
 108
 109           <p><a href=
 110           "tree_based_containers.html#invariants">Design::Tree-Based
 111           Containers::Node Invariants</a> explains this
 112           concept.</p>
 113         </td>
 114
 115         <td><a href="null_trie_node_update.html"><span class=
 116         "c2"><tt>null_trie_node_update</tt></span></a></td>
 117       </tr>
 118
 119       <tr>
 120         <td>
 121           <pre>
 122 <a name="Allocator35940069" id=
 123 "Allocator35940069"><b>class</b> Allocator </a>
 124 </pre>
 125         </td>
 126
 127         <td>
 128           <p>Allocator type.</p>
 129         </td>
 130
 131         <td>
 132           <pre>
 133 std::allocator&lt;<b>char</b>&gt;
 134 </pre>
 135         </td>
 136       </tr>
 137     </table>
 138
 139     <h2><a name="link2" id="link2">Public Types and
 140     Constants</a></h2>
 141
 142     <h3><a name="link3" id="link3">Policy Definitions</a></h3>
 143
 144     <table class="c1" width="100%" border="1" summary="Types">
 145       <tr>
 146         <td width="30%" align="left"><b>Type</b></td>
 147
 148         <td width="55%" align="left"><b>Definition</b></td>
 149
 150         <td width="15%" align="left"><b>Description</b></td>
 151       </tr>
 152
 153       <tr>
 154         <td>
 155           <pre>
 156 <a name="e_access_traits1948190928" id=
 157 "e_access_traits1948190928">e_access_traits</a>
 158 </pre>
 159         </td>
 160
 161         <td>
 162           <pre>
 163 <a href="#E_Access_Traits686553840"><tt>E_Access_Traits</tt></a>
 164 </pre>
 165         </td>
 166
 167         <td>
 168           <p>Element access traits type.</p>
 169         </td>
 170       </tr>
 171     </table>
 172
 173     <h3><a name="link4" id="link4">Iterator Definitions</a></h3>
 174
 175     <table class="c1" width="100%" border="1" summary="Types">
 176       <tr>
 177         <td width="30%" align="left"><b>Type</b></td>
 178
 179         <td width="55%" align="left"><b>Definition</b></td>
 180
 181         <td width="15%" align="left"><b>Description</b></td>
 182       </tr>
 183
 184       <tr>
 185         <td>
 186           <pre>
 187 <a name="const_node_iterator4205924553" id=
 188 "const_node_iterator4205924553">const_node_iterator</a>
 189 </pre>
 190         </td>
 191
 192         <td>
 193           <pre>
 194 <a href=
 195 "trie_const_node_iterator.html"><span class=
 196 "c2"><tt>const_node_iterator</tt></span></a>
 197 </pre>
 198         </td>
 199
 200         <td>
 201           <p>Const node iterator.</p>
 202         </td>
 203       </tr>
 204
 205       <tr>
 206         <td>
 207           <pre>
 208 <a name="node_iterator3431975247" id=
 209 "node_iterator3431975247">node_iterator</a>
 210 </pre>
 211         </td>
 212
 213         <td>
 214           <pre>
 215 <a href="trie_node_iterator.html"><span class=
 216 "c2"><tt>node_iterator</tt></span></a>
 217 </pre>
 218         </td>
 219
 220         <td>
 221           <p>Node iterator.</p>
 222         </td>
 223       </tr>
 224     </table>
 225
 226     <h2><a name="link5" id="link5">Public Methods</a></h2>
 227
 228     <h3><a name="link6" id="link6">Constructors, Destructor, and
 229     Related</a></h3>
 230
 231     <table class="c1" width="100%" border="1" summary="Methods">
 232       <tr>
 233         <td width="45%" align="left"><b>Method</b></td>
 234
 235         <td width="55%" align="left"><b>Description</b></td>
 236       </tr>
 237
 238       <tr>
 239         <td>
 240           <pre>
 241   trie
 242   ()
 243 </pre>
 244         </td>
 245
 246         <td>
 247           <p>Default constructor.</p>
 248         </td>
 249       </tr>
 250
 251       <tr>
 252         <td>
 253           <pre>
 254   trie
 255   (<b>const</b> <a href=
 256 "#E_Access_Traits686553840"><tt>E_Access_Traits</tt></a> &amp;r_e_access_traits)
 257 </pre>
 258         </td>
 259
 260         <td>
 261           <p>Constructor taking some policy objects. <span class=
 262           "c1"><tt>r_e_access_traits</tt></span> will be copied by
 263           the <a href=
 264           "#E_Access_Traits686553840"><tt>E_Access_Traits</tt></a>
 265           object of the container object.</p>
 266         </td>
 267       </tr>
 268
 269       <tr>
 270         <td>
 271           <pre>
 272 <b>template</b>&lt;
 273     <b>class</b> It&gt;
 274   trie
 275   (It first_it,
 276     It last_it)
 277 </pre>
 278         </td>
 279
 280         <td>
 281           <p>Constructor taking iterators to a range of
 282           value_types. The value_types between <span class=
 283           "c1"><tt>first_it</tt></span> and <span class=
 284           "c1"><tt>last_it</tt></span> will be inserted into the
 285           container object.</p>
 286         </td>
 287       </tr>
 288
 289       <tr>
 290         <td>
 291           <pre>
 292 <b>template</b>&lt;
 293     <b>class</b> It&gt;
 294   trie
 295   (It first_it,
 296     It last_it,
 297     <b>const</b> <a href=
 298 "#E_Access_Traits686553840"><tt>E_Access_Traits</tt></a> &amp;r_e_access_traits)
 299 </pre>
 300         </td>
 301
 302         <td>
 303           <p>Constructor taking iterators to a range of value_types
 304           and some policy objects. The value_types between
 305           <span class="c1"><tt>first_it</tt></span> and
 306           <span class="c1"><tt>last_it</tt></span> will be inserted
 307           into the container object.</p>
 308         </td>
 309       </tr>
 310
 311       <tr>
 312         <td>
 313           <pre>
 314   trie
 315   (<b>const</b> <span class=
 316 "c2"><tt>trie</tt></span> &amp;other)
 317 </pre>
 318         </td>
 319
 320         <td>
 321           <p>Copy constructor.</p>
 322         </td>
 323       </tr>
 324
 325       <tr>
 326         <td>
 327           <pre>
 328 <b>virtual</b>
 329   ~trie
 330   ()
 331 </pre>
 332         </td>
 333
 334         <td>
 335           <p>Destructor.</p>
 336         </td>
 337       </tr>
 338
 339       <tr>
 340         <td>
 341           <pre>
 342 <span class="c2"><tt>trie</tt></span> &amp;
 343   <b>operator</b>=
 344   (<b>const</b> <span class=
 345 "c2"><tt>trie</tt></span> &amp;other)
 346 </pre>
 347         </td>
 348
 349         <td>
 350           <p>Assignment operator.</p>
 351         </td>
 352       </tr>
 353
 354       <tr>
 355         <td>
 356           <pre>
 357 <b>void</b>
 358   swap
 359   (<span class=
 360 "c2"><tt>trie</tt></span> &amp;other)
 361 </pre>
 362         </td>
 363
 364         <td>
 365           <p>Swaps content.</p>
 366         </td>
 367       </tr>
 368     </table>
 369
 370     <h3><a name="link7" id="link7">Policy Access Methods</a></h3>
 371
 372     <table class="c1" width="100%" border="1" summary="Methods">
 373       <tr>
 374         <td width="45%" align="left"><b>Method</b></td>
 375
 376         <td width="55%" align="left"><b>Description</b></td>
 377       </tr>
 378
 379       <tr>
 380         <td>
 381           <pre>
 382 <a href=
 383 "#e_access_traits1948190928"><tt>e_access_traits</tt></a> &amp;
 384   get_e_access_traits
 385   ()
 386 </pre>
 387         </td>
 388
 389         <td>
 390           <p>Access to the comb_hash_fn object.</p>
 391         </td>
 392       </tr>
 393
 394       <tr>
 395         <td>
 396           <pre>
 397 <a href=
 398 "#e_access_traits1948190928"><tt>e_access_traits</tt></a> &amp;
 399   get_e_access_traits
 400   () <b>const</b>
 401 </pre>
 402         </td>
 403
 404         <td>
 405           <p>Const access to the comb_hash_fn object.</p>
 406         </td>
 407       </tr>
 408     </table>
 409
 410     <h3><a name="link8" id="link8">Node-Iteration Methods</a></h3>
 411
 412     <table class="c1" width="100%" border="1" summary="Methods">
 413       <tr>
 414         <td width="45%" align="left"><b>Method</b></td>
 415
 416         <td width="55%" align="left"><b>Description</b></td>
 417       </tr>
 418
 419       <tr>
 420         <td>
 421           <pre>
 422 <a href="#node_iterator3431975247"><tt>node_iterator</tt></a>
 423   node_begin
 424   ()
 425 </pre>
 426         </td>
 427
 428         <td>
 429           <p>Returns a <a href=
 430           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 431           corresponding to the node at the root of the trie.</p>
 432         </td>
 433       </tr>
 434
 435       <tr>
 436         <td>
 437           <pre>
 438 <a href=
 439 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 440   node_begin
 441   () <b>const</b>
 442 </pre>
 443         </td>
 444
 445         <td>
 446           <p>Returns a <a href=
 447           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 448           corresponding to the node at the root of the trie.</p>
 449         </td>
 450       </tr>
 451
 452       <tr>
 453         <td>
 454           <pre>
 455 <a href="#node_iterator3431975247"><tt>node_iterator</tt></a>
 456   node_end
 457   ()
 458 </pre>
 459         </td>
 460
 461         <td>
 462           <p>Returns a <a href=
 463           "#node_iterator3431975247"><tt>node_iterator</tt></a>
 464           corresponding to a node just after a leaf of the
 465           trie.</p>
 466         </td>
 467       </tr>
 468
 469       <tr>
 470         <td>
 471           <pre>
 472 <a href=
 473 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 474   node_end
 475   () <b>const</b>
 476 </pre>
 477         </td>
 478
 479         <td>
 480           <p>Returns a <a href=
 481           "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
 482           corresponding to a node just after a leaf of the
 483           trie.</p>
 484         </td>
 485       </tr>
 486     </table>
 487   </div>
 488 </body>
 489 </html>