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></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 350updater policy</a> - interface required of a tree 351node-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 383updater policy</a> - interface required of a trie node 384updater</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> 447