libstdc++-v3/docs/html/ext/pb_ds/interface.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   2  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.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>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>Interface Specifics</h1>
  17
  18 <p>Following are the library's interface specifics. <a href=
  19     "tutorial.html">Short Tutorial</a> is a short tutorial, and
  20     <a href="concepts.html">Concepts</a> describes some
  21     concepts.</p>
  22     <hr />
  23
  24     <h2><a name="namespaces" id="namespaces">Namespace</a></h2>
  25
  26     <p>All code is enclosed in namespace <tt>pb_ds</tt>. Nested within
  27     this is namespace <tt>detail</tt>, which contains the parts of this
  28     library that are considered implementation details.</p>
  29     <hr />
  30
  31     <h2><a name="containers" id="containers">Containers</a></h2>
  32
  33     <h3><a name="containers_assoc" id=
  34     "containers_assoc">Associative Containers</a></h3>
  35
  36     <ol>
  37       <li><a href=
  38       "container_base.html"><tt>container_base</tt></a> -
  39       abstract base class for associative containers.</li>
  40
  41       <li>Hash-based:
  42
  43         <ol>
  44           <li><a href=
  45           "basic_hash_table.html"><tt>basic_hash_table</tt></a>
  46           - abstract base class for hash-based
  47           containers</li>
  48
  49           <li><a href=
  50           "cc_hash_table.html"><tt>cc_hash_table</tt></a>
  51           - concrete collision-chaining hash-based
  52           containers</li>
  53
  54           <li><a href=
  55           "gp_hash_table.html"><tt>gp_hash_table</tt></a>
  56           - concrete (general) probing hash-based
  57           containers</li>
  58         </ol>
  59       </li>
  60
  61       <li>Tree-based:
  62
  63         <ol>
  64           <li><a href=
  65           "basic_tree.html"><tt>basic_tree</tt></a>
  66           - abstract base class for tree and trie based
  67           containers</li>
  68
  69           <li><a href=
  70           "tree.html"><tt>tree</tt></a>
  71           - concrete base class for tree-based
  72           containers</li>
  73
  74           <li><a href=
  75           "trie.html"><tt>trie</tt></a>
  76           - concrete base class for trie-based
  77           containers</li>
  78         </ol>
  79       </li>
  80
  81       <li>List-based:
  82
  83         <ol>
  84           <li><a href=
  85           "list_update.html"><tt>list_update</tt></a> -
  86           singly-linked list with update-policy container</li>
  87         </ol>
  88       </li>
  89     </ol>
  90
  91     <h3><a name="containers_pq" id="containers_pq">Priority
  92     Queues</a></h3>
  93
  94     <ol>
  95       <li><a href="priority_queue.html"><tt>priority_queue</tt></a>
  96       - priority queue</li>
  97     </ol>
  98     <hr />
  99
 100     <h2><a name="tag" id="tag">Container Tags and
 101     Traits</a></h2>
 102
 103     <h3><a name="ds_ts" id="ds_ts">Container Tags</a></h3>
 104
 105     <h4><a name="ds_ts_common" id="ds_ts_common">Common</a></h4>
 106
 107     <ol>
 108       <li><a href="container_tag.html"><tt>container_tag</tt></a> -
 109       base class for data structure tags</li>
 110     </ol>
 111
 112     <h4><a name="ds_ts_assoc" id=
 113     "ds_ts_assoc">Associative-Containers</a></h4>
 114
 115      <ol>
 116       <li><a href=
 117       "associative_container_tag.html"><tt>associative_container_tag</tt></a> -
 118       base class for associative-container data structure tags</li>
 119
 120       <li><a href=
 121       "basic_hash_tag.html"><tt>basic_hash_tag</tt></a> -
 122       base class for hash-based structure tags</li>
 123
 124       <li><a href="cc_hash_tag.html"><tt>cc_hash_tag</tt></a>
 125       - collision-chaining hash structure tag</li>
 126
 127       <li><a href="gp_hash_tag.html"><tt>gp_hash_tag</tt></a>
 128       - (general) probing hash structure tag</li>
 129
 130       <li><a href=
 131       "basic_tree_tag.html"><tt>basic_tree_tag</tt></a>
 132       - base class for tree-like structure tags</li>
 133
 134       <li><a href=
 135       "tree_tag.html"><tt>tree_tag</tt></a> -
 136       base class for tree structure tags</li>
 137
 138       <li><a href="rb_tree_tag.html"><tt>rb_tree_tag</tt></a>
 139       - red-black tree structure tag/li&gt;</li>
 140
 141       <li><a href=
 142       "splay_tree_tag.html"><tt>splay_tree_tag</tt></a> -
 143       splay tree structure tag</li>
 144
 145       <li><a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a>
 146       - ordered-vector tree structure tag</li>
 147
 148       <li><a href=
 149       "trie_tag.html"><tt>trie_tag</tt></a> -
 150       trie structure tag</li>
 151
 152       <li><a href=
 153       "pat_trie_tag.html"><tt>pat_trie_tag</tt></a> -
 154       PATRICIA trie structure tag</li>
 155
 156       <li><a href="list_update_tag.html"><tt>list_update_tag</tt></a> - list
 157       (with updates) structure tag</li>
 158     </ol>
 159
 160     <h4><a name="ds_ts_pq" id="ds_ts_pq">Priority-Queues</a></h4>
 161
 162      <ol>
 163       <li><a href=
 164       "priority_queue_tag.html"><tt>priority_queue_tag</tt></a> - base
 165       class for priority-queue data structure tags</li>
 166
 167       <li><a href=
 168       "pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a> -
 169       pairing-heap structure tag.</li>
 170
 171       <li><a href=
 172       "binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
 173       - binomial-heap structure tag</li>
 174
 175       <li><a href=
 176       "rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
 177       - redundant-counter binomial-heap (<i>i.e.</i>, a heap where
 178       binomial trees form a sequence that is similar to a
 179       de-amortized bit-addition algorithm) structure tag</li>
 180
 181       <li><a href=
 182       "binary_heap_tag.html"><tt>binary_heap_tag</tt></a> -
 183       binary heap (based on an array or an array of nodes)
 184       structure tag</li>
 185
 186       <li><a href=
 187       "thin_heap_tag.html"><tt>thin_heap_tag</tt></a> - thin
 188       heap (an alternative [<a href=
 189       "references.html#kt99fat_heaps">kt99fat_heaps</a>] to
 190       Fibonacci heap) data structure tag.</li>
 191     </ol>
 192
 193     <h3><a name="ds_inv_tag" id="ds_inv_tag">Invalidation-Guarantee
 194     Tags</a></h3>
 195
 196     <ol>
 197       <li><a href=
 198       "basic_invalidation_guarantee.html"><tt>basic_invalidation_guarantee</tt></a>
 199       - weakest invalidation guarantee</li>
 200
 201       <li><a href=
 202       "point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>
 203       - stronger invalidation guarantee</li>
 204
 205       <li><a href=
 206       "range_invalidation_guarantee.html"><tt>range_invalidation_guarantee</tt></a>
 207       - strongest invalidation guarantee</li>
 208     </ol>
 209
 210     <h3><a name="container_traits" id="container_traits">Container
 211     Traits</a></h3>
 212
 213     <ol>
 214       <li><a href="pq_container_traits.html"><tt>container_traits</tt></a> -
 215       traits for determining underlying data structure
 216       properties</li>
 217     </ol>
 218     <hr />
 219
 220     <h2><a name="ds_policy_classes" id=
 221     "ds_policy_classes">Container Policy Classes</a></h2>
 222
 223     <h3><a name="hash_related_policies" id=
 224     "hash_related_policies">Hash Policies</a></h3>
 225
 226     <h4>Hash and Probe Policies</h4>
 227
 228     <ol>
 229       <li>Hash Functions:
 230
 231         <ol>
 232           <li><a href="null_hash_fn.html"><tt>null_hash_fn</tt></a>
 233           - type indicating one-step range-hashing</li>
 234         </ol>
 235       </li>
 236
 237       <li>Range-Hashing Functions:
 238
 239         <ol>
 240           <li><a href="sample_range_hashing.html">Sample
 241           range-hashing function</a> - interface required of a
 242           range-hashing functor</li>
 243
 244           <li><a href=
 245           "direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a>
 246           - (bit) mask-based range hashing functor</li>
 247
 248           <li><a href=
 249           "direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a>
 250           - modulo-based range hashing functor</li>
 251         </ol>
 252       </li>
 253
 254       <li>Probe Functions:
 255
 256         <ol>
 257           <li><a href="sample_probe_fn.html">Sample probe
 258           function</a> - interface required of a probe functor</li>
 259
 260           <li><a href=
 261           "null_probe_fn.html"><tt>null_probe_fn</tt></a> - type
 262           indicating one-step ranged-probe</li>
 263
 264           <li><a href=
 265           "linear_probe_fn.html"><tt>linear_probe_fn</tt></a> -
 266           linear-probe functor</li>
 267
 268           <li><a href=
 269           "quadratic_probe_fn.html"><tt>quadratic_probe_fn</tt></a>-
 270           quadratic-probe functor</li>
 271         </ol>
 272       </li>
 273
 274       <li>Ranged-Hash Functions:
 275
 276         <ol>
 277           <li><a href="sample_ranged_hash_fn.html">Sample
 278           ranged-hash function</a> - interface required of a
 279           ranged-hash functor</li>
 280         </ol>
 281       </li>
 282
 283       <li>Ranged-Probe Functions:
 284
 285         <ol>
 286           <li><a href="sample_ranged_probe_fn.html">Sample
 287           ranged-probe function</a> - interface required of a
 288           ranged-probe functor</li>
 289         </ol>
 290       </li>
 291     </ol>
 292
 293     <h4>Resize Policies</h4>
 294     <ol>
 295       <li>Resize Policies:
 296
 297         <ol>
 298           <li><a href="sample_resize_policy.html">Sample resize
 299           policy</a> - interface required of a resize policy</li>
 300
 301           <li><a href=
 302           "hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a>
 303           - standard resize policy</li>
 304         </ol>
 305       </li>
 306
 307       <li>Size Policies:
 308
 309         <ol>
 310           <li><a href="sample_size_policy.html">Sample size
 311           policy</a> - interface required of a size policy</li>
 312
 313           <li><a href=
 314           "hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a>
 315           - exponential size policy (typically used with (bit) mask
 316           range-hashing)</li>
 317
 318           <li><a href=
 319           "hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a>
 320           - prime size policy (typically used with modulo
 321           range-hashing)</li>
 322         </ol>
 323       </li>
 324
 325       <li>Trigger Policies:
 326
 327         <ol>
 328           <li><a href="sample_resize_trigger.html">Sample trigger
 329           policy</a> - interface required of a trigger policy</li>
 330
 331           <li><a href=
 332           "hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a>
 333           - trigger policy based on load checks</li>
 334
 335           <li><a href=
 336           "cc_hash_max_collision_check_resize_trigger.html"><tt>cc_hash_max_collision_check_resize_trigger</tt></a>
 337           - trigger policy based on collision checks</li>
 338         </ol>
 339       </li>
 340     </ol>
 341
 342     <h3><a name="tree_related_policies" id=
 343     "tree_related_policies">Tree Policies</a></h3>
 344
 345     <h4>Tree Node-Update Policies</h4>
 346
 347
 348 <ol>
 349 <li><a href="sample_tree_node_update.html">Sample node
 350 updater policy</a> - interface required of a tree
 351 node-updating functor</li>
 352
 353 <li><a href=
 354      "null_tree_node_update.html"><tt>null_tree_node_update</tt></a>
 355 - null policy indicating no updates are required</li>
 356
 357 <li><a href=
 358      "tree_order_statistics_node_update.html"><tt>tree_order_statistics_node_update</tt></a>
 359 - updater enabling order statistics queries</li>
 360 </ol>
 361
 362 <h3><a name="trie_related_policies" id=
 363      "trie_related_policies">Trie Policies</a></h3>
 364
 365
 366 <h4>Trie Element-Access Traits</h4>
 367
 368     <ol>
 369       <li><a href="sample_trie_e_access_traits.html">Sample
 370       element-access traits</a> - interface required of
 371       element-access traits</li>
 372
 373       <li><a href=
 374       "string_trie_e_access_traits.html"><tt>string_trie_e_access_traits</tt></a>
 375       - String element-access traits</li>
 376     </ol>
 377
 378     <h4>Trie Node-Update Policies</h4>
 379
 380
 381 <ol>
 382 <li><a href="sample_trie_node_update.html">Sample node
 383 updater policy</a> - interface required of a trie node
 384 updater</li>
 385
 386 <li><a href=
 387      "null_trie_node_update.html"><tt>null_trie_node_update</tt></a>
 388 - null policy indicating no updates are required</li>
 389
 390 <li><a href=
 391      "trie_prefix_search_node_update.html"><tt>trie_prefix_search_node_update</tt></a>
 392 - updater enabling prefix searches</li>
 393
 394 <li><a href=
 395      "trie_order_statistics_node_update.html"><tt>trie_order_statistics_node_update</tt></a>
 396 - updater enabling order statistics queries</li>
 397 </ol>
 398
 399 <h3><a name="list_related_policies" id=
 400      "list_related_policies">List Policies</a></h3>
 401
 402 <h4>List Update Policies</h4>
 403
 404
 405     <ol>
 406       <li><a href="sample_update_policy.html">Sample list update
 407       policy</a> - interface required of a list update policy</li>
 408
 409       <li><a href=
 410       "move_to_front_lu_policy.html"><tt>move_to_front_lu_policy</tt></a>
 411       - move-to-front update algorithm</li>
 412
 413       <li><a href=
 414       "counter_lu_policy.html"><tt>counter_lu_policy</tt></a> -
 415       counter update algorithm</li>
 416     </ol>
 417
 418     <h3><a name="ds_pol" id="ds_pol">Mapped-Type Policies</a></h3>
 419
 420
 421     <ol>
 422       <li><a href=
 423       "null_mapped_type.html"><tt>null_mapped_type</tt></a> - data
 424       policy indicating that a container is a "set"</li>
 425     </ol>
 426     <hr />
 427
 428     <h2><a name="exceptions" id="exceptions">Exceptions</a></h2>
 429
 430
 431     <ol>
 432       <li><a href="exceptions.html"><tt>container_error</tt></a>
 433       - base class for all policy-based data structure errors</li>
 434
 435       <li><a href=
 436       "insert_error.html"><tt>insert_error</tt></a></li>
 437
 438       <li><a href="join_error.html"><tt>join_error</tt></a></li>
 439
 440       <li><a href=
 441       "resize_error.html"><tt>resize_error</tt></a></li>
 442     </ol>
 443
 444   </div>
 445 </body>
 446 </html>