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