gcc-4_8-branch/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Testing</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.78.1" /><meta name="keywords" content="ISO C++, policy, container, data, structure, associated, tree, trie, hash, metaprogramming" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="policy_data_structures.html" title="Chapter 22. Policy-Based Data Structures" /><link rel="prev" href="policy_data_structures_design.html" title="Design" /><link rel="next" href="policy_data_structures_ack.html" title="Acknowledgments" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Testing</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="policy_data_structures_design.html">Prev</a> </td><th width="60%" align="center">Chapter 22. Policy-Based Data Structures</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_ack.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="pbds.test"></a>Testing</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.regression"></a>Regression</h3></div></div></div><p>The library contains a single comprehensive regression test.
   3     For a given container type in this library, the test creates
   4     an object of the container type and an object of the
   5     corresponding standard type (e.g., <code class="classname">std::set</code>). It
   6     then performs a random sequence of methods with random
   7     arguments (e.g., inserts, erases, and so forth) on both
   8     objects. At each operation, the test checks the return value of
   9     the method, and optionally both compares this library's
  10     object with the standard's object as well as performing other
  11     consistency checks on this library's object (e.g.,
  12     order preservation, when applicable, or node invariants, when
  13     applicable).</p><p>Additionally, the test integrally checks exception safety
  14     and resource leaks. This is done as follows. A special
  15     allocator type, written for the purpose of the test, both
  16     randomly throws an exceptions when allocations are performed,
  17     and tracks allocations and de-allocations. The exceptions thrown
  18     at allocations simulate memory-allocation failures; the
  19     tracking mechanism checks for memory-related bugs (e.g.,
  20     resource leaks and multiple de-allocations). Both
  21     this library's containers and the containers' value-types are
  22     configured to use this allocator.</p><p>For granularity, the test is split into the
  23     several sources, each checking only some containers.</p><p>For more details, consult the files in
  24     <code class="filename">testsuite/ext/pb_ds/regression</code>.
  25     </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.performance"></a>Performance</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.hash"></a>Hash-Based</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.text_find"></a>
  26           Text <code class="function">find</code>
  27         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.info"></a>
  28             Description
  29           </h6></div></div></div><p>
  30             This test inserts a number of values with keys from an
  31             arbitrary text (<a class="xref" href="policy_data_structures.html#biblio.wickland96thirty" title="Thirty Years Among the Dead">[biblio.wickland96thirty]</a>) into a container,
  32             then performs a series of finds using
  33             <code class="function">find</code> . It measures the average
  34             time for <code class="function">find</code> as a function of
  35           the number of values inserted.</p><p>
  36             It uses the test file:
  37             <code class="filename">performance/ext/pb_ds/text_find_timing_test.cc</code>
  38           </p><p>
  39             And uses the data file:
  40             <code class="filename">filethirty_years_among_the_dead_preproc.txt</code>
  41           </p><p>The test checks the effect of different range-hashing
  42           functions, trigger policies, and cache-hashing policies.
  43           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.results"></a>
  44             Results
  45           </h6></div></div></div><p>The graphic below show the results for the native
  46           and collision-chaining hash types the the function
  47           applied being a text find timing test using
  48           <code class="function">find</code>.
  49           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_text_find.png" align="middle" /></div></div><p>
  50             The abbreviated names in the legend of the graphic above are
  51             instantiated with the types in the following table.
  52           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
  53                     n_hash_map_ncah
  54                   </td></tr><tr><td align="left">
  55                     <code class="classname">std::tr1::unordered_map</code>
  56                   </td><td align="left">
  57                     <code class="classname">cache_hash_code</code>
  58                   </td><td align="left">
  59                     <code class="constant">false</code>
  60                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
  61                     cc_hash_mod_prime_1div1_nsth_map
  62                   </td></tr><tr><td rowspan="3" align="left" valign="top">
  63                     <code class="classname">cc_hash_table</code>
  64                   </td><td align="left">
  65                     <code class="classname">Comb_Hash_Fn</code>
  66                   </td><td align="left">
  67                     <code class="classname">direct_mod_range_hashing</code>
  68                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
  69                     <code class="classname">Resize_Policy</code>
  70                   </td><td rowspan="2" align="left" valign="top">
  71                     <code class="classname">hash_standard_resize_policy</code>
  72                   </td><td align="left">
  73                     <code class="classname">Size_Policy</code>
  74                   </td><td align="left">
  75                     <code class="classname">hash_prime_size_policy</code>
  76                   </td></tr><tr><td align="left" valign="top">
  77                     <code class="classname">Trigger_Policy</code>
  78                   </td><td align="left">
  79                     <code class="classname">hash_load_check_resize_trigger</code> with
  80                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
  81                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
  82                     cc_hash_mask_exp_1div2_sth_map
  83                   </td></tr><tr><td rowspan="3" align="left" valign="top">
  84                     <code class="classname">
  85                       cc_hash_table
  86                     </code>
  87                   </td><td align="left">
  88                     <code class="classname">Comb_Hash_Fn</code>
  89                   </td><td align="left">
  90                     <code class="classname">direct_mask_range_hashing</code>
  91                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
  92                     <code class="classname">Resize_Policy</code>
  93                   </td><td rowspan="2" align="left" valign="top">
  94                     <code class="classname">hash_standard_resize_policy</code>
  95                   </td><td align="left">
  96                     <code class="classname">Size_Policy</code>
  97                   </td><td align="left">
  98                     <code class="classname">hash_exponential_size_policy</code>
  99                   </td></tr><tr><td align="left" valign="top">
 100                     <code class="classname">Trigger_Policy</code>
 101                   </td><td align="left">
 102                     <code class="classname">hash_load_check_resize_trigger</code> with
 103                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 104                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 105                     cc_hash_mask_exp_1div1_nsth_map
 106                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 107                     <code class="classname">cc_hash_table</code>
 108                   </td><td align="left">
 109                     <code class="classname">Comb_Hash_Fn</code>
 110                   </td><td align="left">
 111                     <code class="classname">direct_mask_range_hashing</code>
 112                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 113                     <code class="classname">Resize_Policy</code>
 114                   </td><td rowspan="2" align="left" valign="top">
 115                     <code class="classname">hash_standard_resize_policy</code>
 116                   </td><td align="left">
 117                     <code class="classname">Size_Policy</code>
 118                   </td><td align="left">
 119                     <code class="classname">hash_exponential_size_policy</code>
 120                   </td></tr><tr><td align="left" valign="top">
 121                     <code class="classname">Trigger_Policy</code>
 122                   </td><td align="left">
 123                     <code class="classname">hash_load_check_resize_trigger</code> with
 124                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 125                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 126                     cc_hash_mask_exp_1div2_nsth_map
 127                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 128                     <code class="classname">cc_hash_table</code>
 129                   </td><td align="left">
 130                     <code class="classname">Comb_Hash_Fn</code>
 131                   </td><td align="left">
 132                     <code class="classname">direct_mask_range_hashing</code>
 133                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 134                     <code class="classname">Resize_Policy</code>
 135                   </td><td rowspan="2" align="left" valign="top">
 136                     <code class="classname">hash_standard_resize_policy</code>
 137                   </td><td align="left">
 138                     <code class="classname">Size_Policy</code>
 139                   </td><td align="left">
 140                     <code class="classname">hash_exponential_size_policy</code>
 141                   </td></tr><tr><td align="left" valign="top">
 142                     <code class="classname">Trigger_Policy</code>
 143                   </td><td align="left">
 144                     <code class="classname">hash_load_check_resize_trigger</code> with
 145                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 146                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.observations"></a>
 147             Observations
 148           </h6></div></div></div><p>In this setting, the range-hashing scheme affects performance
 149           more than other policies. As the results show, containers using
 150           mod-based range-hashing (including the native hash-based container,
 151           which is currently hard-wired to this scheme) have lower performance
 152           than those using mask-based range-hashing. A modulo-based
 153           range-hashing scheme's main benefit is that it takes into account
 154           all hash-value bits. Standard string hash-functions are designed to
 155           create hash values that are nearly-uniform as is (<a class="xref" href="policy_data_structures.html#biblio.knuth98sorting" title="The Art of Computer Programming - Sorting and Searching">[biblio.knuth98sorting]</a>).</p><p>Trigger policies, i.e. the load-checks constants, affect
 156           performance to a lesser extent.</p><p>Perhaps surprisingly, storing the hash value alongside each
 157           entry affects performance only marginally, at least in this
 158           library's implementation. (Unfortunately, it was not possible to run
 159           the tests with <code class="classname">std::tr1::unordered_map</code> 's
 160           <code class="classname">cache_hash_code = true</code> , as it appeared to
 161           malfuntion.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_find"></a>
 162           Integer <code class="function">find</code>
 163         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.info"></a>
 164             Description
 165           </h6></div></div></div><p>This test inserts a number of values with uniform
 166           integer keys into a container, then performs a series of finds
 167           using <code class="function">find</code>. It measures the average time
 168           for <code class="function">find</code> as a function of the number of values
 169           inserted.</p><p>
 170             It uses the test file:
 171             <code class="filename">performance/ext/pb_ds/random_int_find_timing.cc</code>
 172           </p><p>The test checks the effect of different underlying
 173           hash-tables,
 174           range-hashing functions, and trigger policies.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.results"></a>
 175             Results
 176           </h6></div></div></div><p>
 177             There are two sets of results for this type, one for
 178             collision-chaining hashes, and one for general-probe hashes.
 179           </p><p>The first graphic below shows the results for the native and
 180           collision-chaining hash types. The function applied being a random
 181           integer timing test using <code class="function">find</code>.
 182           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_find.png" align="middle" /></div></div><p>
 183             The abbreviated names in the legend of the graphic above are
 184             instantiated with the types in the following table.
 185           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 186                     n_hash_map_ncah
 187                   </td></tr><tr><td align="left">
 188                     <code class="classname">std::tr1::unordered_map</code>
 189                   </td><td align="left">
 190                     <code class="classname">cache_hash_code</code>
 191                   </td><td align="left">
 192                     <code class="constant">false</code>
 193                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 194                     cc_hash_mod_prime_1div1_nsth_map
 195                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 196                     <code class="classname">cc_hash_table</code>
 197                   </td><td align="left">
 198                     <code class="classname">Comb_Hash_Fn</code>
 199                   </td><td align="left">
 200                     <code class="classname">direct_mod_range_hashing</code>
 201                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 202                     <code class="classname">Resize_Policy</code>
 203                   </td><td rowspan="2" align="left" valign="top">
 204                     <code class="classname">hash_standard_resize_policy</code>
 205                   </td><td align="left">
 206                     <code class="classname">Size_Policy</code>
 207                   </td><td align="left">
 208                     <code class="classname">hash_prime_size_policy</code>
 209                   </td></tr><tr><td align="left" valign="top">
 210                     <code class="classname">Trigger_Policy</code>
 211                   </td><td align="left">
 212                     <code class="classname">hash_load_check_resize_trigger</code> with
 213                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 214                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 215                     cc_hash_mod_prime_1div2_nsth_map
 216                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 217                     <code class="classname">
 218                       cc_hash_table
 219                     </code>
 220                   </td><td align="left">
 221                     <code class="classname">Comb_Hash_Fn</code>
 222                   </td><td align="left">
 223                     <code class="classname">direct_mod_range_hashing</code>
 224                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 225                     <code class="classname">Resize_Policy</code>
 226                   </td><td rowspan="2" align="left" valign="top">
 227                     <code class="classname">hash_standard_resize_policy</code>
 228                   </td><td align="left">
 229                     <code class="classname">Size_Policy</code>
 230                   </td><td align="left">
 231                     <code class="classname">hash_prime_size_policy</code>
 232                   </td></tr><tr><td align="left" valign="top">
 233                     <code class="classname">Trigger_Policy</code>
 234                   </td><td align="left">
 235                     <code class="classname">hash_load_check_resize_trigger</code> with
 236                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 237                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 238                     cc_hash_mask_exp_1div1_nsth_map
 239                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 240                     <code class="classname">cc_hash_table</code>
 241                   </td><td align="left">
 242                     <code class="classname">Comb_Hash_Fn</code>
 243                   </td><td align="left">
 244                     <code class="classname">direct_mask_range_hashing</code>
 245                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 246                     <code class="classname">Resize_Policy</code>
 247                   </td><td rowspan="2" align="left" valign="top">
 248                     <code class="classname">hash_standard_resize_policy</code>
 249                   </td><td align="left">
 250                     <code class="classname">Size_Policy</code>
 251                   </td><td align="left">
 252                     <code class="classname">hash_exponential_size_policy</code>
 253                   </td></tr><tr><td align="left" valign="top">
 254                     <code class="classname">Trigger_Policy</code>
 255                   </td><td align="left">
 256                     <code class="classname">hash_load_check_resize_trigger</code> with
 257                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 258                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 259                     cc_hash_mask_exp_1div2_nsth_map
 260                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 261                     <code class="classname">cc_hash_table</code>
 262                   </td><td align="left">
 263                     <code class="classname">Comb_Hash_Fn</code>
 264                   </td><td align="left">
 265                     <code class="classname">direct_mask_range_hashing</code>
 266                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 267                     <code class="classname">Resize_Policy</code>
 268                   </td><td rowspan="2" align="left" valign="top">
 269                     <code class="classname">hash_standard_resize_policy</code>
 270                   </td><td align="left">
 271                     <code class="classname">Size_Policy</code>
 272                   </td><td align="left">
 273                     <code class="classname">hash_exponential_size_policy</code>
 274                   </td></tr><tr><td align="left" valign="top">
 275                     <code class="classname">Trigger_Policy</code>
 276                   </td><td align="left">
 277                     <code class="classname">hash_load_check_resize_trigger</code> with
 278                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 279                   </td></tr></tbody></table></div><p>
 280           </p><p>
 281           </p><p>And the second graphic shows the results for the native and
 282           general-probe hash types. The function applied being a random
 283           integer timing test using <code class="function">find</code>.
 284           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_find.png" align="middle" /></div></div><p>
 285             The abbreviated names in the legend of the graphic above are
 286             instantiated with the types in the following table.
 287           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 288                     n_hash_map_ncah
 289                   </td></tr><tr><td align="left">
 290                     <code class="classname">std::tr1::unordered_map</code>
 291                   </td><td align="left">
 292                     <code class="classname">cache_hash_code</code>
 293                   </td><td align="left">
 294                     <code class="constant">false</code>
 295                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 296                     gp_hash_mod_quadp_prime_1div2_nsth_map
 297                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 298                     <code class="classname">gp_hash_table</code>
 299                   </td><td align="left">
 300                     <code class="classname">Comb_Hash_Fn</code>
 301                   </td><td align="left">
 302                     <code class="classname">direct_mod_range_hashing</code>
 303                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 304                     <code class="classname">Probe_Fn</code>
 305                   </td><td align="left">
 306                     <code class="classname">quadratic_probe_fn</code>
 307                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 308                     <code class="classname">Resize_Policy</code>
 309                   </td><td rowspan="2" align="left" valign="top">
 310                     <code class="classname">hash_standard_resize_policy</code>
 311                   </td><td align="left">
 312                     <code class="classname">Size_Policy</code>
 313                   </td><td align="left">
 314                     <code class="classname">hash_prime_size_policy</code>
 315                   </td></tr><tr><td align="left" valign="top">
 316                     <code class="classname">Trigger_Policy</code>
 317                   </td><td align="left">
 318                     <code class="classname">hash_load_check_resize_trigger</code> with
 319                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 320                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 321                     gp_hash_mask_linp_exp_1div2_nsth_map
 322                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 323                     <code class="classname">
 324                       gp_hash_table
 325                     </code>
 326                   </td><td align="left">
 327                     <code class="classname">Comb_Hash_Fn</code>
 328                   </td><td align="left">
 329                     <code class="classname">direct_mask_range_hashing</code>
 330                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 331                     <code class="classname">Probe_Fn</code>
 332                   </td><td align="left">
 333                     <code class="classname">linear_probe_fn</code>
 334                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 335                     <code class="classname">Resize_Policy</code>
 336                   </td><td rowspan="2" align="left" valign="top">
 337                     <code class="classname">hash_standard_resize_policy</code>
 338                   </td><td align="left">
 339                     <code class="classname">Size_Policy</code>
 340                   </td><td align="left">
 341                     <code class="classname">hash_exponential_size_policy</code>
 342                   </td></tr><tr><td align="left" valign="top">
 343                     <code class="classname">Trigger_Policy</code>
 344                   </td><td align="left">
 345                     <code class="classname">hash_load_check_resize_trigger</code> with
 346                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 347                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.observations"></a>
 348             Observations
 349           </h6></div></div></div><p>In this setting, the choice of underlying hash-table affects
 350           performance most, then the range-hashing scheme and, only finally,
 351           other policies.</p><p>When comparing probing and chaining containers, it is
 352           apparent that the probing containers are less efficient than the
 353           collision-chaining containers (
 354           <code class="classname">std::tr1::unordered_map</code> uses
 355           collision-chaining) in this case.</p><p>Hash-Based Integer Subscript Insert Timing Test shows
 356           a different case, where the situation is reversed;
 357           </p><p>Within each type of hash-table, the range-hashing scheme
 358           affects performance more than other policies; Hash-Based Text
 359           <code class="function">find</code> Find Timing Test also shows this. In the
 360           above graphics should be noted that
 361           <code class="classname">std::tr1::unordered_map</code> are hard-wired
 362           currently to mod-based schemes.
 363           </p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_subscript_find"></a>
 364           Integer Subscript <code class="function">find</code>
 365         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.info"></a>
 366             Description
 367           </h6></div></div></div><p>This test inserts a number of values with uniform
 368           integer keys into a container, then performs a series of finds
 369           using <code class="function">operator[]</code>. It measures the average time
 370           for <code class="function">operator[]</code> as a function of the number of
 371           values inserted.</p><p>
 372             It uses the test file:
 373             <code class="filename">performance/ext/pb_ds/random_int_subscript_find_timing.cc</code>
 374           </p><p>The test checks the effect of different underlying
 375           hash-tables, range-hashing functions, and trigger policies.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.results"></a>
 376             Results
 377           </h6></div></div></div><p>
 378             There are two sets of results for this type, one for
 379             collision-chaining hashes, and one for general-probe hashes.
 380           </p><p>The first graphic below shows the results for the native
 381           and collision-chaining hash types, using as the function
 382           applied an integer subscript timing test with
 383           <code class="function">find</code>.
 384           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_subscript_find.png" align="middle" /></div></div><p>
 385             The abbreviated names in the legend of the graphic above are
 386             instantiated with the types in the following table.
 387           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 388                     n_hash_map_ncah
 389                   </td></tr><tr><td align="left">
 390                     <code class="classname">std::tr1::unordered_map</code>
 391                   </td><td align="left">
 392                     <code class="classname">cache_hash_code</code>
 393                   </td><td align="left">
 394                     <code class="constant">false</code>
 395                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 396                     cc_hash_mod_prime_1div1_nsth_map
 397                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 398                     <code class="classname">cc_hash_table</code>
 399                   </td><td align="left">
 400                     <code class="classname">Comb_Hash_Fn</code>
 401                   </td><td align="left">
 402                     <code class="classname">direct_mod_range_hashing</code>
 403                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 404                     <code class="classname">Resize_Policy</code>
 405                   </td><td rowspan="2" align="left" valign="top">
 406                     <code class="classname">hash_standard_resize_policy</code>
 407                   </td><td align="left">
 408                     <code class="classname">Size_Policy</code>
 409                   </td><td align="left">
 410                     <code class="classname">hash_prime_size_policy</code>
 411                   </td></tr><tr><td align="left" valign="top">
 412                     <code class="classname">Trigger_Policy</code>
 413                   </td><td align="left">
 414                     <code class="classname">hash_load_check_resize_trigger</code> with
 415                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 416                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 417                     cc_hash_mod_prime_1div2_nsth_map
 418                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 419                     <code class="classname">cc_hash_table</code>
 420                   </td><td align="left">
 421                     <code class="classname">Comb_Hash_Fn</code>
 422                   </td><td align="left">
 423                     <code class="classname">direct_mod_range_hashing</code>
 424                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 425                     <code class="classname">Resize_Policy</code>
 426                   </td><td rowspan="2" align="left" valign="top">
 427                     <code class="classname">hash_standard_resize_policy</code>
 428                   </td><td align="left">
 429                     <code class="classname">Size_Policy</code>
 430                   </td><td align="left">
 431                     <code class="classname">hash_prime_size_policy</code>
 432                   </td></tr><tr><td align="left" valign="top">
 433                     <code class="classname">Trigger_Policy</code>
 434                   </td><td align="left">
 435                     <code class="classname">hash_load_check_resize_trigger</code> with
 436                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 437                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 438                     cc_hash_mask_exp_1div1_nsth_map
 439                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 440                     <code class="classname">cc_hash_table</code>
 441                   </td><td align="left">
 442                     <code class="classname">Comb_Hash_Fn</code>
 443                   </td><td align="left">
 444                     <code class="classname">direct_mask_range_hashing</code>
 445                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 446                     <code class="classname">Resize_Policy</code>
 447                   </td><td rowspan="2" align="left" valign="top">
 448                     <code class="classname">hash_standard_resize_policy</code>
 449                   </td><td align="left">
 450                     <code class="classname">Size_Policy</code>
 451                   </td><td align="left">
 452                     <code class="classname">hash_exponential_size_policy</code>
 453                   </td></tr><tr><td align="left" valign="top">
 454                     <code class="classname">Trigger_Policy</code>
 455                   </td><td align="left">
 456                     <code class="classname">hash_load_check_resize_trigger</code> with
 457                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 458                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 459                     cc_hash_mask_exp_1div2_nsth_map
 460                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 461                     <code class="classname">cc_hash_table</code>
 462                   </td><td align="left">
 463                     <code class="classname">Comb_Hash_Fn</code>
 464                   </td><td align="left">
 465                     <code class="classname">direct_mask_range_hashing</code>
 466                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 467                     <code class="classname">Resize_Policy</code>
 468                   </td><td rowspan="2" align="left" valign="top">
 469                     <code class="classname">hash_standard_resize_policy</code>
 470                   </td><td align="left">
 471                     <code class="classname">Size_Policy</code>
 472                   </td><td align="left">
 473                     <code class="classname">hash_exponential_size_policy</code>
 474                   </td></tr><tr><td align="left" valign="top">
 475                     <code class="classname">Trigger_Policy</code>
 476                   </td><td align="left">
 477                     <code class="classname">hash_load_check_resize_trigger</code> with
 478                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 479                   </td></tr></tbody></table></div><p>
 480           </p><p>
 481           </p><p>And the second graphic shows the results for the native and
 482           general-probe hash types. The function applied being a random
 483           integer timing test using <code class="function">find</code>.
 484           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_subscript_find.png" align="middle" /></div></div><p>
 485             The abbreviated names in the legend of the graphic above are
 486             instantiated with the types in the following table.
 487           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 488                     n_hash_map_ncah
 489                   </td></tr><tr><td align="left">
 490                     <code class="classname">std::tr1::unordered_map</code>
 491                   </td><td align="left">
 492                     <code class="classname">cache_hash_code</code>
 493                   </td><td align="left">
 494                     <code class="constant">false</code>
 495                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 496                     gp_hash_mod_quadp_prime_1div2_nsth_map
 497                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 498                     <code class="classname">gp_hash_table</code>
 499                   </td><td align="left">
 500                     <code class="classname">Comb_Hash_Fn</code>
 501                   </td><td align="left">
 502                     <code class="classname">direct_mod_range_hashing</code>
 503                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 504                     <code class="classname">Probe_Fn</code>
 505                   </td><td align="left">
 506                     <code class="classname">quadratic_probe_fn</code>
 507                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 508                     <code class="classname">Resize_Policy</code>
 509                   </td><td rowspan="2" align="left" valign="top">
 510                     <code class="classname">hash_standard_resize_policy</code>
 511                   </td><td align="left">
 512                     <code class="classname">Size_Policy</code>
 513                   </td><td align="left">
 514                     <code class="classname">hash_prime_size_policy</code>
 515                   </td></tr><tr><td align="left" valign="top">
 516                     <code class="classname">Trigger_Policy</code>
 517                   </td><td align="left">
 518                     <code class="classname">hash_load_check_resize_trigger</code> with
 519                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 520                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 521                     gp_hash_mask_linp_exp_1div2_nsth_map
 522                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 523                     <code class="classname">
 524                       gp_hash_table
 525                     </code>
 526                   </td><td align="left">
 527                     <code class="classname">Comb_Hash_Fn</code>
 528                   </td><td align="left">
 529                     <code class="classname">direct_mask_range_hashing</code>
 530                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 531                     <code class="classname">Probe_Fn</code>
 532                   </td><td align="left">
 533                     <code class="classname">linear_probe_fn</code>
 534                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 535                     <code class="classname">Resize_Policy</code>
 536                   </td><td rowspan="2" align="left" valign="top">
 537                     <code class="classname">hash_standard_resize_policy</code>
 538                   </td><td align="left">
 539                     <code class="classname">Size_Policy</code>
 540                   </td><td align="left">
 541                     <code class="classname">hash_exponential_size_policy</code>
 542                   </td></tr><tr><td align="left" valign="top">
 543                     <code class="classname">Trigger_Policy</code>
 544                   </td><td align="left">
 545                     <code class="classname">hash_load_check_resize_trigger</code> with
 546                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 547                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.observations"></a>
 548             Observations
 549           </h6></div></div></div><p>This test shows similar results to Hash-Based
 550           Integer <code class="classname">find</code> Find Timing test.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_subscript_insert"></a>
 551           Integer Subscript <code class="function">insert</code>
 552         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.info"></a>
 553             Description
 554           </h6></div></div></div><p>This test inserts a number of values with uniform i.i.d.
 555           integer keys into a container, using
 556           <code class="function">operator[]</code>. It measures the average time for
 557           <code class="function">operator[]</code> as a function of the number of
 558           values inserted.</p><p>
 559             It uses the test file:
 560             <code class="filename">performance/ext/pb_ds/random_int_subscript_insert_timing.cc</code>
 561           </p><p>The test checks the effect of different underlying
 562           hash-tables.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.results"></a>
 563             Results
 564           </h6></div></div></div><p>
 565             There are two sets of results for this type, one for
 566             collision-chaining hashes, and one for general-probe hashes.
 567           </p><p>The first graphic below shows the results for the native
 568           and collision-chaining hash types, using as the function
 569           applied an integer subscript timing test with
 570           <code class="function">insert</code>.
 571           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_subscript_insert.png" align="middle" /></div></div><p>
 572             The abbreviated names in the legend of the graphic above are
 573             instantiated with the types in the following table.
 574           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 575                     n_hash_map_ncah
 576                   </td></tr><tr><td align="left">
 577                     <code class="classname">std::tr1::unordered_map</code>
 578                   </td><td align="left">
 579                     <code class="classname">cache_hash_code</code>
 580                   </td><td align="left">
 581                     <code class="constant">false</code>
 582                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 583                     cc_hash_mod_prime_1div1_nsth_map
 584                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 585                     <code class="classname">cc_hash_table</code>
 586                   </td><td align="left">
 587                     <code class="classname">Comb_Hash_Fn</code>
 588                   </td><td align="left">
 589                     <code class="classname">direct_mod_range_hashing</code>
 590                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 591                     <code class="classname">Resize_Policy</code>
 592                   </td><td rowspan="2" align="left" valign="top">
 593                     <code class="classname">hash_standard_resize_policy</code>
 594                   </td><td align="left">
 595                     <code class="classname">Size_Policy</code>
 596                   </td><td align="left">
 597                     <code class="classname">hash_prime_size_policy</code>
 598                   </td></tr><tr><td align="left" valign="top">
 599                     <code class="classname">Trigger_Policy</code>
 600                   </td><td align="left">
 601                     <code class="classname">hash_load_check_resize_trigger</code> with
 602                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 603                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 604                     cc_hash_mod_prime_1div2_nsth_map
 605                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 606                     <code class="classname">cc_hash_table</code>
 607                   </td><td align="left">
 608                     <code class="classname">Comb_Hash_Fn</code>
 609                   </td><td align="left">
 610                     <code class="classname">direct_mod_range_hashing</code>
 611                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 612                     <code class="classname">Resize_Policy</code>
 613                   </td><td rowspan="2" align="left" valign="top">
 614                     <code class="classname">hash_standard_resize_policy</code>
 615                   </td><td align="left">
 616                     <code class="classname">Size_Policy</code>
 617                   </td><td align="left">
 618                     <code class="classname">hash_prime_size_policy</code>
 619                   </td></tr><tr><td align="left" valign="top">
 620                     <code class="classname">Trigger_Policy</code>
 621                   </td><td align="left">
 622                     <code class="classname">hash_load_check_resize_trigger</code> with
 623                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 624                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 625                     cc_hash_mask_exp_1div1_nsth_map
 626                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 627                     <code class="classname">cc_hash_table</code>
 628                   </td><td align="left">
 629                     <code class="classname">Comb_Hash_Fn</code>
 630                   </td><td align="left">
 631                     <code class="classname">direct_mask_range_hashing</code>
 632                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 633                     <code class="classname">Resize_Policy</code>
 634                   </td><td rowspan="2" align="left" valign="top">
 635                     <code class="classname">hash_standard_resize_policy</code>
 636                   </td><td align="left">
 637                     <code class="classname">Size_Policy</code>
 638                   </td><td align="left">
 639                     <code class="classname">hash_exponential_size_policy</code>
 640                   </td></tr><tr><td align="left" valign="top">
 641                     <code class="classname">Trigger_Policy</code>
 642                   </td><td align="left">
 643                     <code class="classname">hash_load_check_resize_trigger</code> with
 644                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 645                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 646                     cc_hash_mask_exp_1div2_nsth_map
 647                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 648                     <code class="classname">cc_hash_table</code>
 649                   </td><td align="left">
 650                     <code class="classname">Comb_Hash_Fn</code>
 651                   </td><td align="left">
 652                     <code class="classname">direct_mask_range_hashing</code>
 653                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 654                     <code class="classname">Resize_Policy</code>
 655                   </td><td rowspan="2" align="left" valign="top">
 656                     <code class="classname">hash_standard_resize_policy</code>
 657                   </td><td align="left">
 658                     <code class="classname">Size_Policy</code>
 659                   </td><td align="left">
 660                     <code class="classname">hash_exponential_size_policy</code>
 661                   </td></tr><tr><td align="left" valign="top">
 662                     <code class="classname">Trigger_Policy</code>
 663                   </td><td align="left">
 664                     <code class="classname">hash_load_check_resize_trigger</code> with
 665                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 666                   </td></tr></tbody></table></div><p>
 667           </p><p>
 668           </p><p>And the second graphic shows the results for the native and
 669           general-probe hash types. The function applied being a random
 670           integer timing test using <code class="function">find</code>.
 671           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_subscript_insert.png" align="middle" /></div></div><p>
 672             The abbreviated names in the legend of the graphic above are
 673             instantiated with the types in the following table.
 674           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 675                     n_hash_map_ncah
 676                   </td></tr><tr><td align="left">
 677                     <code class="classname">std::tr1::unordered_map</code>
 678                   </td><td align="left">
 679                     <code class="classname">cache_hash_code</code>
 680                   </td><td align="left">
 681                     <code class="constant">false</code>
 682                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 683                     gp_hash_mod_quadp_prime_1div2_nsth_map
 684                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 685                     <code class="classname">gp_hash_table</code>
 686                   </td><td align="left">
 687                     <code class="classname">Comb_Hash_Fn</code>
 688                   </td><td align="left">
 689                     <code class="classname">direct_mod_range_hashing</code>
 690                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 691                     <code class="classname">Probe_Fn</code>
 692                   </td><td align="left">
 693                     <code class="classname">quadratic_probe_fn</code>
 694                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 695                     <code class="classname">Resize_Policy</code>
 696                   </td><td rowspan="2" align="left" valign="top">
 697                     <code class="classname">hash_standard_resize_policy</code>
 698                   </td><td align="left">
 699                     <code class="classname">Size_Policy</code>
 700                   </td><td align="left">
 701                     <code class="classname">hash_prime_size_policy</code>
 702                   </td></tr><tr><td align="left" valign="top">
 703                     <code class="classname">Trigger_Policy</code>
 704                   </td><td align="left">
 705                     <code class="classname">hash_load_check_resize_trigger</code> with
 706                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 707                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 708                     gp_hash_mask_linp_exp_1div2_nsth_map
 709                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 710                     <code class="classname">
 711                       gp_hash_table
 712                     </code>
 713                   </td><td align="left">
 714                     <code class="classname">Comb_Hash_Fn</code>
 715                   </td><td align="left">
 716                     <code class="classname">direct_mask_range_hashing</code>
 717                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 718                     <code class="classname">Probe_Fn</code>
 719                   </td><td align="left">
 720                     <code class="classname">linear_probe_fn</code>
 721                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 722                     <code class="classname">Resize_Policy</code>
 723                   </td><td rowspan="2" align="left" valign="top">
 724                     <code class="classname">hash_standard_resize_policy</code>
 725                   </td><td align="left">
 726                     <code class="classname">Size_Policy</code>
 727                   </td><td align="left">
 728                     <code class="classname">hash_exponential_size_policy</code>
 729                   </td></tr><tr><td align="left" valign="top">
 730                     <code class="classname">Trigger_Policy</code>
 731                   </td><td align="left">
 732                     <code class="classname">hash_load_check_resize_trigger</code> with
 733                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 734                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.observations"></a>
 735             Observations
 736           </h6></div></div></div><p>In this setting, as in Hash-Based Text
 737           <code class="function">find</code> Find Timing test and Hash-Based
 738           Integer <code class="function">find</code> Find Timing test , the choice
 739           of underlying hash-table underlying hash-table affects performance
 740           most, then the range-hashing scheme, and
 741           finally any other policies.</p><p>There are some differences, however:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>In this setting, probing tables function sometimes more
 742             efficiently than collision-chaining tables.
 743             This is explained shortly.</p></li><li class="listitem"><p>The performance graphs have a "saw-tooth" shape. The
 744             average insert time rises and falls. As values are inserted
 745             into the container, the load factor grows larger. Eventually,
 746             a resize occurs. The reallocations and rehashing are
 747             relatively expensive. After this, the load factor is smaller
 748             than before.</p></li></ol></div><p>Collision-chaining containers use indirection for greater
 749           flexibility; probing containers store values contiguously, in
 750           an array (see Figure Motivation::Different
 751           underlying data structures A and B, respectively). It
 752           follows that for simple data types, probing containers access
 753           their allocator less frequently than collision-chaining
 754           containers, (although they still have less efficient probing
 755           sequences). This explains why some probing containers fare
 756           better than collision-chaining containers in this case.</p><p>
 757             Within each type of hash-table, the range-hashing scheme affects
 758             performance more than other policies. This is similar to the
 759             situation in Hash-Based Text
 760             <code class="function">find</code> Find Timing Test and Hash-Based
 761             Integer <code class="function">find</code> Find Timing Test.
 762             Unsurprisingly, however, containers with lower α<sub>max</sub> perform worse in this case,
 763           since more re-hashes are performed.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.zlob_int_find"></a>
 764           Integer <code class="function">find</code> with Skewed-Distribution
 765         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.info"></a>
 766             Description
 767           </h6></div></div></div><p>This test inserts a number of values with a markedly
 768           non-uniform integer keys into a container, then performs
 769           a series of finds using <code class="function">find</code>. It measures the average
 770           time for <code class="function">find</code> as a function of the number of values in
 771           the containers. The keys are generated as follows. First, a
 772           uniform integer is created. Then it is then shifted left 8 bits.</p><p>
 773             It uses the test file:
 774             <code class="filename">performance/ext/pb_ds/hash_zlob_random_int_find_timing.cc</code>
 775           </p><p>The test checks the effect of different range-hashing
 776           functions and trigger policies.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.results"></a>
 777             Results
 778           </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
 779           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_zlob_int_find.png" align="middle" /></div></div><p>
 780             The abbreviated names in the legend of the graphic above are
 781             instantiated with the types in the following table.
 782           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 783                     n_hash_map_ncah
 784                   </td></tr><tr><td align="left">
 785                     <code class="classname">std::tr1::unordered_map</code>
 786                   </td><td align="left">
 787                     <code class="classname">cache_hash_code</code>
 788                   </td><td align="left">
 789                     <code class="constant">false</code>
 790                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 791                     cc_hash_mod_prime_1div1_nsth_map
 792                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 793                     <code class="classname">cc_hash_table</code>
 794                   </td><td align="left">
 795                     <code class="classname">Comb_Hash_Fn</code>
 796                   </td><td align="left">
 797                     <code class="classname">direct_mod_range_hashing</code>
 798                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 799                     <code class="classname">Resize_Policy</code>
 800                   </td><td rowspan="2" align="left" valign="top">
 801                     <code class="classname">hash_standard_resize_policy</code>
 802                   </td><td align="left">
 803                     <code class="classname">Size_Policy</code>
 804                   </td><td align="left">
 805                     <code class="classname">hash_prime_size_policy</code>
 806                   </td></tr><tr><td align="left" valign="top">
 807                     <code class="classname">Trigger_Policy</code>
 808                   </td><td align="left">
 809                     <code class="classname">hash_load_check_resize_trigger</code> with
 810                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 811                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 812                     cc_hash_mask_exp_1div1_nsth_map
 813                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 814                     <code class="classname">
 815                       cc_hash_table
 816                     </code>
 817                   </td><td align="left">
 818                     <code class="classname">Comb_Hash_Fn</code>
 819                   </td><td align="left">
 820                     <code class="classname">direct_mask_range_hashing</code>
 821                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 822                     <code class="classname">Resize_Policy</code>
 823                   </td><td rowspan="2" align="left" valign="top">
 824                     <code class="classname">hash_standard_resize_policy</code>
 825                   </td><td align="left">
 826                     <code class="classname">Size_Policy</code>
 827                   </td><td align="left">
 828                     <code class="classname">hash_exponential_size_policy</code>
 829                   </td></tr><tr><td align="left" valign="top">
 830                     <code class="classname">Trigger_Policy</code>
 831                   </td><td align="left">
 832                     <code class="classname">hash_load_check_resize_trigger</code> with
 833                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 834                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 835                     gp_hash_mod_quadp_prime_1div2_nsth_map
 836                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 837                     <code class="classname">gp_hash_table</code>
 838                   </td><td align="left">
 839                     <code class="classname">Comb_Hash_Fn</code>
 840                   </td><td align="left">
 841                     <code class="classname">direct_mod_range_hashing</code>
 842                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 843                     <code class="classname">Probe_Fn</code>
 844                   </td><td align="left">
 845                     <code class="classname">quadratic_probe_fn</code>
 846                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 847                     <code class="classname">Resize_Policy</code>
 848                   </td><td rowspan="2" align="left" valign="top">
 849                     <code class="classname">hash_standard_resize_policy</code>
 850                   </td><td align="left">
 851                     <code class="classname">Size_Policy</code>
 852                   </td><td align="left">
 853                     <code class="classname">hash_prime_size_policy</code>
 854                   </td></tr><tr><td align="left" valign="top">
 855                     <code class="classname">Trigger_Policy</code>
 856                   </td><td align="left">
 857                     <code class="classname">hash_load_check_resize_trigger</code> with
 858                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 859                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.observations"></a>
 860             Observations
 861           </h6></div></div></div><p>In this setting, the distribution of keys is so skewed that
 862           the underlying hash-table type affects performance marginally.
 863           (This is in contrast with Hash-Based Text
 864           <code class="function">find</code> Find Timing Test, Hash-Based
 865           Integer <code class="function">find</code> Find Timing Test, Hash-Based
 866           Integer Subscript Find Timing Test and Hash-Based
 867           Integer Subscript Insert Timing Test.)</p><p>The range-hashing scheme affects performance dramatically. A
 868           mask-based range-hashing scheme effectively maps all values
 869           into the same bucket. Access degenerates into a search within
 870           an unordered linked-list. In the graphic above, it should be noted that
 871           <code class="classname">std::tr1::unordered_map</code> is hard-wired currently to mod-based and mask-based schemes,
 872           respectively.</p><p>When observing the settings of this test, it is apparent
 873           that the keys' distribution is far from natural. One might ask
 874           if the test is not contrived to show that, in some cases,
 875           mod-based range hashing does better than mask-based range
 876           hashing. This is, in fact just the case. A
 877           more natural case in which mod-based range hashing is better was not encountered.
 878           Thus the inescapable conclusion: real-life key distributions are handled better
 879           with an appropriate hash function and a mask-based
 880           range-hashing function. (<code class="filename">pb_ds/example/hash_shift_mask.cc</code>
 881           shows an example of handling this a-priori known skewed
 882           distribution with a mask-based range-hashing function). If hash
 883           performance is bad, a χ<sup>2</sup> test can be used
 884           to check how to transform it into a more uniform
 885           distribution.</p><p>For this reason, this library's default range-hashing
 886           function is mask-based.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.erase_mem"></a>
 887           Erase Memory Use
 888         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.info"></a>
 889             Description
 890           </h6></div></div></div><p>This test inserts a number of uniform integer keys
 891           into a container, then erases all keys except one. It measures
 892           the final size of the container.</p><p>
 893             It uses the test file:
 894             <code class="filename">performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc</code>
 895           </p><p>The test checks how containers adjust internally as their
 896           logical size decreases.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.results"></a>
 897             Results
 898           </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
 899           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_int_erase_mem.png" align="middle" /></div></div><p>
 900             The abbreviated names in the legend of the graphic above are
 901             instantiated with the types in the following table.
 902           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 903                     n_hash_map_ncah
 904                   </td></tr><tr><td align="left">
 905                     <code class="classname">std::tr1::unordered_map</code>
 906                   </td><td align="left">
 907                     <code class="classname">cache_hash_code</code>
 908                   </td><td align="left">
 909                     <code class="constant">false</code>
 910                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 911                     cc_hash_mod_prime_1div1_nsth_map
 912                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 913                     <code class="classname">cc_hash_table</code>
 914                   </td><td align="left">
 915                     <code class="classname">Comb_Hash_Fn</code>
 916                   </td><td align="left">
 917                     <code class="classname">direct_mod_range_hashing</code>
 918                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 919                     <code class="classname">Resize_Policy</code>
 920                   </td><td rowspan="2" align="left" valign="top">
 921                     <code class="classname">hash_standard_resize_policy</code>
 922                   </td><td align="left">
 923                     <code class="classname">Size_Policy</code>
 924                   </td><td align="left">
 925                     <code class="classname">hash_prime_size_policy</code>
 926                   </td></tr><tr><td align="left" valign="top">
 927                     <code class="classname">Trigger_Policy</code>
 928                   </td><td align="left">
 929                     <code class="classname">hash_load_check_resize_trigger</code> with
 930                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1
 931                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 932                     cc_hash_mask_exp_1div2_nsth_map
 933                   </td></tr><tr><td rowspan="3" align="left" valign="top">
 934                     <code class="classname">
 935                       cc_hash_table
 936                     </code>
 937                   </td><td align="left">
 938                     <code class="classname">Comb_Hash_Fn</code>
 939                   </td><td align="left">
 940                     <code class="classname">direct_mask_range_hashing</code>
 941                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 942                     <code class="classname">Resize_Policy</code>
 943                   </td><td rowspan="2" align="left" valign="top">
 944                     <code class="classname">hash_standard_resize_policy</code>
 945                   </td><td align="left">
 946                     <code class="classname">Size_Policy</code>
 947                   </td><td align="left">
 948                     <code class="classname">hash_exponential_size_policy</code>
 949                   </td></tr><tr><td align="left" valign="top">
 950                     <code class="classname">Trigger_Policy</code>
 951                   </td><td align="left">
 952                     <code class="classname">hash_load_check_resize_trigger</code> with
 953                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 954                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left">
 955                     gp_hash_mask_linp_exp_1div2_nsth_set
 956                   </td></tr><tr><td rowspan="4" align="left" valign="top">
 957                     <code class="classname">gp_hash_table</code>
 958                   </td><td align="left">
 959                     <code class="classname">Comb_Hash_Fn</code>
 960                   </td><td align="left">
 961                     <code class="classname">direct_mask_range_hashing</code>
 962                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
 963                     <code class="classname">Probe_Fn</code>
 964                   </td><td align="left">
 965                     <code class="classname">linear_probe_fn</code>
 966                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
 967                     <code class="classname">Resize_Policy</code>
 968                   </td><td rowspan="2" align="left" valign="top">
 969                     <code class="classname">hash_standard_resize_policy</code>
 970                   </td><td align="left">
 971                     <code class="classname">Size_Policy</code>
 972                   </td><td align="left">
 973                     <code class="classname">hash_exponential_size_policy</code>
 974                   </td></tr><tr><td align="left" valign="top">
 975                     <code class="classname">Trigger_Policy</code>
 976                   </td><td align="left">
 977                     <code class="classname">hash_load_check_resize_trigger</code> with
 978                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
 979                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.observations"></a>
 980             Observations
 981           </h6></div></div></div><p>The standard's hash-based containers act very differently than trees in
 982           this respect. When erasing numerous keys from an standard
 983           associative-container, the resulting memory user varies greatly
 984           depending on whether the container is tree-based or hash-based.
 985           This is a fundamental consequence of the standard's interface for
 986           associative containers, and it is not due to a specific
 987           implementation.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.branch"></a>Branch-Based</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_insert"></a>
 988           Text <code class="function">insert</code>
 989         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.info"></a>
 990             Description
 991           </h6></div></div></div><p>This test inserts a number of values with keys from an arbitrary
 992           text ([ wickland96thirty ]) into a container
 993           using <code class="function">insert</code> . It measures the average time
 994           for <code class="function">insert</code> as a function of the number of
 995           values inserted.</p><p>The test checks the effect of different underlying
 996           data structures.</p><p>
 997             It uses the test file:
 998             <code class="filename">performance/ext/pb_ds/tree_text_insert_timing.cc</code>
 999           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.results"></a>
1000             Results
1001           </h6></div></div></div><p>The three graphics below show the results for the native
1002           tree and this library's node-based trees, the native tree and
1003           this library's vector-based trees, and the native tree
1004           and this library's PATRICIA-trie, respectively.
1005           </p><p>The graphic immediately below shows the results for the
1006           native tree type and several node-based tree types.
1007           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_node.png" align="middle" /></div><p>
1008               The abbreviated names in the legend of the graphic above are
1009               instantiated with the types in the following table.
1010             </p></div><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1011                     n_map
1012                   </td></tr><tr><td align="left">
1013                     <code class="classname">std::map</code>
1014                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1015                     splay_tree_map
1016                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1017                     <code class="classname">tree</code>
1018                   </td><td align="left">
1019                     <code class="classname">Tag</code>
1020                   </td><td align="left">
1021                     <code class="classname">splay_tree_tag</code>
1022                   </td></tr><tr><td align="left">
1023                     <code class="classname">Node_update</code>
1024                   </td><td align="left">
1025                     <code class="classname">null_node_update</code>
1026                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1027                     rb_tree_map
1028                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1029                     <code class="classname">tree</code>
1030                   </td><td align="left">
1031                     <code class="classname">Tag</code>
1032                   </td><td align="left">
1033                     <code class="classname">rb_tree_tag</code>
1034                   </td></tr><tr><td align="left">
1035                     <code class="classname">Node_update</code>
1036                   </td><td align="left">
1037                     <code class="classname">null_node_update</code>
1038                   </td></tr></tbody></table></div><p>The graphic below shows the results for the
1039           native tree type and a vector-based tree type.
1040           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_vector.png" align="middle" /></div></div><p>
1041             The abbreviated names in the legend of the graphic above are
1042             instantiated with the types in the following table.
1043           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1044                     n_map
1045                   </td></tr><tr><td align="left">
1046                     <code class="classname">std::map</code>
1047                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1048                     ov_tree_map
1049                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1050                     <code class="classname">tree</code>
1051                   </td><td align="left">
1052                     <code class="classname">Tag</code>
1053                   </td><td align="left">
1054                     <code class="classname">ov_tree_tag</code>
1055                   </td></tr><tr><td align="left">
1056                     <code class="classname">Node_update</code>
1057                   </td><td align="left">
1058                     <code class="classname">null_node_update</code>
1059                   </td></tr></tbody></table></div><p>The graphic below shows the results for the
1060           native tree type and a PATRICIA trie type.
1061           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_trie.png" align="middle" /></div></div><p>
1062             The abbreviated names in the legend of the graphic above are
1063             instantiated with the types in the following table.
1064           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1065                     n_map
1066                   </td></tr><tr><td align="left">
1067                     <code class="classname">std::map</code>
1068                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1069                     pat_trie_map
1070                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1071                     <code class="classname">tree</code>
1072                   </td><td align="left">
1073                     <code class="classname">Tag</code>
1074                   </td><td align="left">
1075                     <code class="classname">pat_trie_tag</code>
1076                   </td></tr><tr><td align="left">
1077                     <code class="classname">Node_update</code>
1078                   </td><td align="left">
1079                     <code class="classname">null_node_update</code>
1080                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.observations"></a>
1081             Observations
1082           </h6></div></div></div><p>Observing the first graphic implies that for this setting, a splay tree
1083           (<code class="classname">tree</code> with <code class="classname">Tag
1084           </code> = <code class="classname">splay_tree_tag</code>) does not do
1085           well. See also the Branch-Based
1086           Text <code class="function">find</code> Find Timing Test. The two
1087           red-black trees perform better.</p><p>Observing the second graphic, an ordered-vector tree
1088           (<code class="classname">tree</code> with <code class="classname">Tag
1089           </code> = <code class="classname">ov_tree_tag</code>) performs
1090           abysmally. Inserting into this type of tree has linear complexity
1091           [ austern00noset].</p><p>Observing the third and last graphic, A PATRICIA trie
1092           (<code class="classname">trie</code> with <code class="classname">Tag
1093           </code> = <code class="classname">pat_trie_tag</code>) has abysmal
1094           performance, as well. This is not that surprising, since a
1095           large-fan-out PATRICIA trie works like a hash table with
1096           collisions resolved by a sub-trie. Each time a collision is
1097           encountered, a new "hash-table" is built A large fan-out PATRICIA
1098           trie, however, doe does well in look-ups (see Branch-Based
1099           Text <code class="function">find</code> Find Timing Test). It may be
1100           beneficial in semi-static settings.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_find"></a>
1101           Text <code class="function">find</code>
1102         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.info"></a>
1103             Description
1104           </h6></div></div></div><p>This test inserts a number of values with keys from an
1105           arbitrary text ([wickland96thirty]) into
1106           a container, then performs a series of finds using
1107           <code class="function">find</code>. It measures the average time
1108           for <code class="function">find</code> as a function of the number of
1109           values inserted.</p><p>
1110             It uses the test file:
1111             <code class="filename">performance/ext/pb_ds/text_find_timing.cc</code>
1112           </p><p>The test checks the effect of different underlying
1113           data structures.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.results"></a>
1114             Results
1115           </h6></div></div></div><p>The graphic immediately below shows the results for the
1116           native tree type and several other tree types.
1117           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_find.png" align="middle" /></div></div><p>
1118             The abbreviated names in the legend of the graphic above are
1119             instantiated with the types in the following table.
1120           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1121                     n_map
1122                   </td></tr><tr><td align="left">
1123                     <code class="classname">std::map</code>
1124                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1125                     splay_tree_map
1126                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1127                     <code class="classname">tree</code>
1128                   </td><td align="left">
1129                     <code class="classname">Tag</code>
1130                   </td><td align="left">
1131                     <code class="classname">splay_tree_tag</code>
1132                   </td></tr><tr><td align="left">
1133                     <code class="classname">Node_Update</code>
1134                   </td><td align="left">
1135                     <code class="classname">null_node_update</code>
1136                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1137                     rb_tree_map
1138                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1139                     <code class="classname">tree</code>
1140                   </td><td align="left">
1141                     <code class="classname">Tag</code>
1142                   </td><td align="left">
1143                     <code class="classname">rb_tree_tag</code>
1144                   </td></tr><tr><td align="left">
1145                     <code class="classname">Node_Update</code>
1146                   </td><td align="left">
1147                     <code class="classname">null_node_update</code>
1148                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1149                     ov_tree_map
1150                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1151                     <code class="classname">tree</code>
1152                   </td><td align="left">
1153                     <code class="classname">Tag</code>
1154                   </td><td align="left">
1155                     <code class="classname">ov_tree_tag</code>
1156                   </td></tr><tr><td align="left">
1157                     <code class="classname">Node_Update</code>
1158                   </td><td align="left">
1159                     <code class="classname">null_node_update</code>
1160                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1161                     pat_trie_map
1162                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1163                     <code class="classname">tree</code>
1164                   </td><td align="left">
1165                     <code class="classname">Tag</code>
1166                   </td><td align="left">
1167                     <code class="classname">pat_trie_tag</code>
1168                   </td></tr><tr><td align="left">
1169                     <code class="classname">Node_Update</code>
1170                   </td><td align="left">
1171                     <code class="classname">null_node_update</code>
1172                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.observations"></a>
1173             Observations
1174           </h6></div></div></div><p>For this setting, a splay tree (<code class="classname">tree</code>
1175           with <code class="classname">Tag
1176           </code> = <code class="classname">splay_tree_tag</code>) does not do
1177           well. This is possibly due to two reasons:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>A splay tree is not guaranteed to be balanced [motwani95random]. If a
1178             splay tree contains n nodes, its average root-leaf
1179             path can be m &gt;&gt; log(n).</p></li><li class="listitem"><p>Assume a specific root-leaf search path has length
1180             m, and the search-target node has distance m'
1181             from the root. A red-black tree will require m + 1
1182             comparisons to find the required node; a splay tree will
1183             require 2 m' comparisons. A splay tree, consequently,
1184             can perform many more comparisons than a red-black tree.</p></li></ol></div><p>An ordered-vector tree (<code class="classname">tree</code>
1185           with <code class="classname">Tag</code> =  <code class="classname">ov_tree_tag</code>), a red-black
1186           tree (<code class="classname">tree</code>
1187           with <code class="classname">Tag</code>  = <code class="classname">rb_tree_tag</code>), and the
1188           native red-black tree all share approximately the same
1189           performance.</p><p>An ordered-vector tree is slightly slower than red-black
1190           trees, since it requires, in order to find a key, more math
1191           operations than they do. Conversely, an ordered-vector tree
1192           requires far lower space than the others. ([austern00noset], however,
1193           seems to have an implementation that is also faster than a
1194           red-black tree).</p><p>A PATRICIA trie (<code class="classname">trie</code>
1195           with <code class="classname">Tag</code> = <code class="classname">pat_trie_tag</code>) has good
1196           look-up performance, due to its large fan-out in this case. In
1197           this setting, a PATRICIA trie has look-up performance comparable
1198           to a hash table (see Hash-Based Text
1199           <code class="classname">find</code> Timing Test), but it is order
1200           preserving. This is not that surprising, since a large-fan-out
1201           PATRICIA trie works like a hash table with collisions resolved
1202           by a sub-trie. A large-fan-out PATRICIA trie does not do well on
1203           modifications (see Tree-Based and Trie-Based
1204           Text Insert Timing Test). Therefore, it is possibly beneficial in
1205           semi-static settings.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_lor_find"></a>
1206           Text <code class="function">find</code> with Locality-of-Reference
1207         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.info"></a>
1208             Description
1209           </h6></div></div></div><p>This test inserts a number of values with keys from an
1210           arbitrary text ([ wickland96thirty ]) into
1211           a container, then performs a series of finds using
1212           <code class="function">find</code>. It is different than Tree-Based and
1213           Trie-Based Text <code class="function">find</code> Find Timing Test in the
1214           sequence of finds it performs: this test performs multiple
1215           <code class="function">find</code>s on the same key before moving on to the next
1216           key. It measures the average time for <code class="function">find</code> as a
1217           function of the number of values inserted.</p><p>
1218             It uses the test file:
1219             <code class="filename">performance/ext/pb_ds/tree_text_lor_find_timing.cc</code>
1220           </p><p>The test checks the effect of different underlying
1221           data structures in a locality-of-reference setting.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.results"></a>
1222             Results
1223           </h6></div></div></div><p>The graphic immediately below shows the results for the
1224           native tree type and several other tree types.
1225           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_lor_find.png" align="middle" /></div></div><p>
1226             The abbreviated names in the legend of the graphic above are
1227             instantiated with the types in the following table.
1228           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1229                     n_map
1230                   </td></tr><tr><td align="left">
1231                     <code class="classname">std::map</code>
1232                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1233                     splay_tree_map
1234                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1235                     <code class="classname">tree</code>
1236                   </td><td align="left">
1237                     <code class="classname">Tag</code>
1238                   </td><td align="left">
1239                     <code class="classname">splay_tree_tag</code>
1240                   </td></tr><tr><td align="left">
1241                     <code class="classname">Node_Update</code>
1242                   </td><td align="left">
1243                     <code class="classname">null_node_update</code>
1244                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1245                     rb_tree_map
1246                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1247                     <code class="classname">tree</code>
1248                   </td><td align="left">
1249                     <code class="classname">Tag</code>
1250                   </td><td align="left">
1251                     <code class="classname">rb_tree_tag</code>
1252                   </td></tr><tr><td align="left">
1253                     <code class="classname">Node_Update</code>
1254                   </td><td align="left">
1255                     <code class="classname">null_node_update</code>
1256                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1257                     ov_tree_map
1258                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1259                     <code class="classname">tree</code>
1260                   </td><td align="left">
1261                     <code class="classname">Tag</code>
1262                   </td><td align="left">
1263                     <code class="classname">ov_tree_tag</code>
1264                   </td></tr><tr><td align="left">
1265                     <code class="classname">Node_Update</code>
1266                   </td><td align="left">
1267                     <code class="classname">null_node_update</code>
1268                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1269                     pat_trie_map
1270                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1271                     <code class="classname">tree</code>
1272                   </td><td align="left">
1273                     <code class="classname">Tag</code>
1274                   </td><td align="left">
1275                     <code class="classname">pat_trie_tag</code>
1276                   </td></tr><tr><td align="left">
1277                     <code class="classname">Node_Update</code>
1278                   </td><td align="left">
1279                     <code class="classname">null_node_update</code>
1280                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.observations"></a>
1281             Observations
1282           </h6></div></div></div><p>For this setting, an ordered-vector tree
1283           (<code class="classname">tree</code> with <code class="classname">Tag</code>
1284           = <code class="classname">ov_tree_tag</code>), a red-black tree
1285           (<code class="classname">tree</code> with <code class="classname">Tag</code>
1286           = <code class="classname">rb_tree_tag</code>), and the native red-black
1287           tree all share approximately the same performance.</p><p>A splay tree (<code class="classname">tree</code>
1288           with <code class="classname">Tag</code> = <code class="classname">splay_tree_tag</code>) does
1289           much better, since each (successful) find "bubbles" the
1290           corresponding node to the root of the tree.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.split_join"></a>
1291           <code class="function">split</code> and <code class="function">join</code>
1292         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.info"></a>
1293             Description
1294           </h6></div></div></div><p>This test a container, inserts into a number of values, splits
1295           the container at the median, and joins the two containers. (If the
1296           containers are one of this library's trees,
1297           it splits and joins with the <code class="function">split</code> and
1298           <code class="function">join</code> method; otherwise, it uses the <code class="function">erase</code> and
1299           <code class="function">insert</code> methods.) It measures the time for splitting
1300           and joining the containers as a function of the number of
1301           values inserted.</p><p>
1302             It uses the test file:
1303             <code class="filename">performance/ext/pb_ds/tree_split_join_timing.cc</code>
1304           </p><p>The test checks the performance difference of <code class="function">join</code>
1305           as opposed to a sequence of <code class="function">insert</code> operations; by
1306           implication, this test checks the most efficient way to erase a
1307           sub-sequence from a tree-like-based container, since this can
1308           always be performed by a small sequence of splits and joins.
1309           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.results"></a>
1310             Results
1311           </h6></div></div></div><p>The graphic immediately below shows the results for the
1312           native tree type and several other tree types.
1313           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_split_join.png" align="middle" /></div></div><p>
1314             The abbreviated names in the legend of the graphic above are
1315             instantiated with the types in the following table.
1316           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1317                     n_set
1318                   </td></tr><tr><td align="left">
1319                     <code class="classname">std::set</code>
1320                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1321                     splay_tree_set
1322                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1323                     <code class="classname">tree</code>
1324                   </td><td align="left">
1325                     <code class="classname">Tag</code>
1326                   </td><td align="left">
1327                     <code class="classname">splay_tree_tag</code>
1328                   </td></tr><tr><td align="left">
1329                     <code class="classname">Node_Update</code>
1330                   </td><td align="left">
1331                     <code class="classname">null_node_update</code>
1332                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1333                     rb_tree_set
1334                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1335                     <code class="classname">tree</code>
1336                   </td><td align="left">
1337                     <code class="classname">Tag</code>
1338                   </td><td align="left">
1339                     <code class="classname">rb_tree_tag</code>
1340                   </td></tr><tr><td align="left">
1341                     <code class="classname">Node_Update</code>
1342                   </td><td align="left">
1343                     <code class="classname">null_node_update</code>
1344                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1345                     ov_tree_set
1346                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1347                     <code class="classname">tree</code>
1348                   </td><td align="left">
1349                     <code class="classname">Tag</code>
1350                   </td><td align="left">
1351                     <code class="classname">ov_tree_tag</code>
1352                   </td></tr><tr><td align="left">
1353                     <code class="classname">Node_Update</code>
1354                   </td><td align="left">
1355                     <code class="classname">null_node_update</code>
1356                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1357                     pat_trie_map
1358                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1359                     <code class="classname">tree</code>
1360                   </td><td align="left">
1361                     <code class="classname">Tag</code>
1362                   </td><td align="left">
1363                     <code class="classname">pat_trie_tag</code>
1364                   </td></tr><tr><td align="left">
1365                     <code class="classname">Node_Update</code>
1366                   </td><td align="left">
1367                     <code class="classname">null_node_update</code>
1368                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.observations"></a>
1369             Observations
1370           </h6></div></div></div><p>In this test, the native red-black trees must be split and
1371           joined externally, through a sequence of <code class="function">erase</code> and
1372           <code class="function">insert</code> operations. This is clearly
1373           super-linear, and it is not that surprising that the cost is
1374           high.</p><p>This library's tree-based containers use in this test the
1375           <code class="function">split</code> and <code class="function">join</code> methods,
1376           which have lower complexity: the <code class="function">join</code> method
1377           of a splay tree (<code class="classname">tree</code>
1378           with <code class="classname">Tag </code>
1379           = <code class="classname">splay_tree_tag</code>) is quadratic in the
1380           length of the longest root-leaf path, and linear in the total
1381           number of elements; the <code class="function">join</code> method of a
1382           red-black tree (<code class="classname">tree</code>
1383           with <code class="classname">Tag </code>
1384           = <code class="classname">rb_tree_tag</code>) or an ordered-vector tree
1385           (<code class="classname">tree</code> with <code class="classname">Tag </code>
1386           = <code class="classname">ov_tree_tag</code>) is linear in the number of
1387           elements.</p><p>Asides from orders of growth, this library's trees access their
1388           allocator very little in these operations, and some of them do not
1389           access it at all. This leads to lower constants in their
1390           complexity, and, for some containers, to exception-free splits and
1391           joins (which can be determined
1392           via <code class="classname">container_traits</code>).</p><p>It is important to note that <code class="function">split</code> and
1393           <code class="function">join</code> are not esoteric methods - they are the most
1394           efficient means of erasing a contiguous range of values from a
1395           tree based container.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.order_statistics"></a>
1396           Order-Statistics
1397         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.info"></a>
1398             Description
1399           </h6></div></div></div><p>This test creates a container, inserts random integers into the
1400           the container, and then checks the order-statistics of the
1401           container's values. (If the container is one of this
1402           library's trees, it does this with
1403           the <code class="function">order_of_key</code> method of
1404           <code class="classname">tree_order_statistics_node_update</code>
1405           ; otherwise, it uses the <code class="function">find</code> method and
1406           <code class="function">std::distance</code>.) It measures the average
1407           time for such queries as a function of the number of values
1408           inserted.</p><p>
1409             It uses the test file:
1410             <code class="filename">performance/ext/pb_ds/tree_order_statistics_timing.cc</code>
1411           </p><p>The test checks the performance difference of policies based
1412           on node-invariant as opposed to a external functions.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.results"></a>
1413             Results
1414           </h6></div></div></div><p>The graphic immediately below shows the results for the
1415           native tree type and several other tree types.
1416           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_order_statistics.png" align="middle" /></div></div><p>
1417             The abbreviated names in the legend of the graphic above are
1418             instantiated with the types in the following table.
1419           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1420                     n_set
1421                   </td></tr><tr><td align="left">
1422                     <code class="classname">std::set</code>
1423                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1424                     splay_tree_ost_set
1425                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1426                     <code class="classname">tree</code>
1427                   </td><td align="left">
1428                     <code class="classname">Tag</code>
1429                   </td><td align="left">
1430                     <code class="classname">splay_tree_tag</code>
1431                   </td></tr><tr><td align="left">
1432                     <code class="classname">Node_Update</code>
1433                   </td><td align="left">
1434                     <code class="classname">tree_order_statistics_node_update</code>
1435                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
1436                     rb_tree_ost_set
1437                   </td></tr><tr><td rowspan="2" align="left" valign="top">
1438                     <code class="classname">tree</code>
1439                   </td><td align="left">
1440                     <code class="classname">Tag</code>
1441                   </td><td align="left">
1442                     <code class="classname">rb_tree_tag</code>
1443                   </td></tr><tr><td align="left">
1444                     <code class="classname">Node_Update</code>
1445                   </td><td align="left">
1446                     <code class="classname">tree_order_statistics_node_update</code>
1447                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.observations"></a>
1448             Observations
1449           </h6></div></div></div><p>In this test, the native red-black tree can support
1450           order-statistics queries only externally, by performing a
1451           <code class="classname">find</code> (alternatively, <code class="classname">lower_bound</code> or
1452           <code class="classname">upper_bound</code> ) and then using <code class="classname">std::distance</code> .
1453           This is clearly linear, and it is not that surprising that the
1454           cost is high.</p><p>This library's tree-based containers use in this test the
1455           <code class="classname">order_of_key</code> method of <code class="classname">tree_order_statistics_node_update</code>.
1456           This method has only linear complexity in the length of the
1457           root-node path. Unfortunately, the average path of a splay tree
1458           (<code class="classname">tree</code>
1459           with <code class="classname">Tag =</code> <code class="classname">splay_tree_tag</code> ) can
1460           be higher than logarithmic; the longest path of a red-black
1461           tree (<code class="classname">tree</code>
1462           with <code class="classname">Tag =</code> <code class="classname">rb_tree_tag</code> ) is
1463           logarithmic in the number of elements. Consequently, the splay
1464           tree has worse performance than the red-black tree.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.multimap"></a>Multimap</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_find_small"></a>
1465           Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios
1466         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.info"></a>
1467             Description
1468           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1469           first item of each pair is a string from an arbitrary text
1470           [wickland96thirty], and
1471           the second is a uniform i.i.d.integer. The container is a
1472           "multimap" - it considers the first member of each pair as a
1473           primary key, and the second member of each pair as a secondary
1474           key (see Motivation::Associative
1475           Containers::Alternative to Multiple Equivalent Keys). There
1476           are 400 distinct primary keys, and the ratio of secondary keys
1477           to primary keys ranges from 1 to 5.</p><p>The test measures the average find-time as a function of the
1478           number of values inserted. For this library's containers, it
1479           finds the secondary key from a container obtained from finding
1480           a primary key. For the native multimaps, it searches a range
1481           obtained using <code class="classname">std::equal_range</code> on a primary key.</p><p>
1482             It uses the test file:
1483             <code class="filename">performance/ext/pb_ds/multimap_text_find_timing_small.cc</code>
1484           </p><p>The test checks the find-time scalability of different
1485           "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.results"></a>
1486             Results
1487           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
1488           use a tree-based container for primary keys.
1489           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_tree.png" align="middle" /></div></div><p>
1490             The abbreviated names in the legend of the graphic above are
1491             instantiated with the types in the following table.
1492           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1493                     n_mmap
1494                   </td></tr><tr><td align="left">
1495                     <code class="classname">std::multimap</code>
1496                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1497                     rb_tree_mmap_lu_mtf_set
1498                   </td></tr><tr><td rowspan="3" align="left" valign="top">
1499                     <code class="classname">tree</code>
1500                   </td><td align="left">
1501                     <code class="classname">Tag</code>
1502                   </td><td align="left">
1503                     <code class="classname">rb_tree_tag</code>
1504                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1505                     <code class="classname">Node_Update</code>
1506                   </td><td align="left">
1507                     <code class="classname">null_node_update</code>
1508                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1509                     <code class="classname">Mapped</code>
1510                   </td><td align="left">
1511                     <code class="classname">list_update</code>
1512                   </td><td align="left">
1513                     <code class="classname">Update_Policy</code>
1514                   </td><td align="left">
1515                     <code class="classname">lu_move_to_front_policy</code>
1516                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1517                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1518                   </td></tr><tr><td rowspan="5" align="left" valign="top">
1519                     <code class="classname">tree</code>
1520                   </td><td align="left">
1521                     <code class="classname">Tag</code>
1522                   </td><td align="left">
1523                     <code class="classname">rb_tree_tag</code>
1524                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1525                     <code class="classname">Node_Update</code>
1526                   </td><td align="left">
1527                     <code class="classname">null_node_update</code>
1528                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1529                     <code class="classname">Mapped</code>
1530                   </td><td rowspan="3" align="left" valign="top">
1531                     <code class="classname">cc_hash_table</code>
1532                   </td><td align="left">
1533                     <code class="classname">Comb_Hash_Fn</code>
1534                   </td><td align="left">
1535                     <code class="classname">direct_mask_range_hashing</code>
1536                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1537                     <code class="classname">Resize_Policy</code>
1538                   </td><td rowspan="2" align="left" valign="top">
1539                     <code class="classname">hash_standard_resize_policy</code>
1540                   </td><td align="left">
1541                     <code class="classname">Size_Policy</code>
1542                   </td><td align="left">
1543                     <code class="classname">hash_exponential_size_policy</code>
1544                   </td></tr><tr><td align="left" valign="top">
1545                     <code class="classname">Trigger_Policy</code>
1546                   </td><td align="left">
1547                     <code class="classname">hash_load_check_resize_trigger</code> with
1548                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1549                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
1550           use a hash-based container for primary keys.
1551           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" align="middle" /></div></div><p>
1552             The abbreviated names in the legend of the graphic above are
1553             instantiated with the types in the following table.
1554           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1555                     n_hash_mmap
1556                   </td></tr><tr><td align="left">
1557                     <code class="classname">std::tr1::unordered_multimap</code>
1558                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1559                     rb_tree_mmap_lu_mtf_set
1560                   </td></tr><tr><td rowspan="4" align="left" valign="top">
1561                     <code class="classname">
1562                       cc_hash_table
1563                     </code>
1564                   </td><td align="left">
1565                     <code class="classname">Comb_Hash_Fn</code>
1566                   </td><td align="left">
1567                     <code class="classname">direct_mask_range_hashing</code>
1568                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1569                     <code class="classname">Resize_Policy</code>
1570                   </td><td rowspan="2" align="left" valign="top">
1571                     <code class="classname">hash_standard_resize_policy</code>
1572                   </td><td align="left">
1573                     <code class="classname">Size_Policy</code>
1574                   </td><td align="left">
1575                     <code class="classname">hash_exponential_size_policy</code>
1576                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1577                     <code class="classname">Trigger_Policy</code>
1578                   </td><td align="left">
1579                     <code class="classname">hash_load_check_resize_trigger</code> with
1580                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1581                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
1582                     <code class="classname">Mapped</code>
1583                   </td><td align="left">
1584                     <code class="classname">list_update</code>
1585                   </td><td align="left">
1586                     <code class="classname">Update_Policy</code>
1587                   </td><td align="left">
1588                     <code class="classname">lu_move_to_front_policy</code>
1589                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1590                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1591                   </td></tr><tr><td rowspan="6" align="left" valign="top">
1592                     <code class="classname">
1593                       cc_hash_table
1594                     </code>
1595                   </td><td align="left">
1596                     <code class="classname">Comb_Hash_Fn</code>
1597                   </td><td align="left">
1598                     <code class="classname">direct_mask_range_hashing</code>
1599                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1600                     <code class="classname">Resize_Policy</code>
1601                   </td><td rowspan="2" align="left" valign="top">
1602                     <code class="classname">hash_standard_resize_policy</code>
1603                   </td><td align="left">
1604                     <code class="classname">Size_Policy</code>
1605                   </td><td align="left">
1606                     <code class="classname">hash_exponential_size_policy</code>
1607                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1608                     <code class="classname">Trigger_Policy</code>
1609                   </td><td align="left">
1610                     <code class="classname">hash_load_check_resize_trigger</code> with
1611                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1612                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1613                     <code class="classname">Mapped</code>
1614                   </td><td rowspan="3" align="left" valign="top">
1615                     <code class="classname">cc_hash_table</code>
1616                   </td><td align="left">
1617                     <code class="classname">Comb_Hash_Fn</code>
1618                   </td><td align="left">
1619                     <code class="classname">direct_mask_range_hashing</code>
1620                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1621                     <code class="classname">Resize_Policy</code>
1622                   </td><td rowspan="2" align="left" valign="top">
1623                     <code class="classname">hash_standard_resize_policy</code>
1624                   </td><td align="left">
1625                     <code class="classname">Size_Policy</code>
1626                   </td><td align="left">
1627                     <code class="classname">hash_exponential_size_policy</code>
1628                   </td></tr><tr><td align="left" valign="top">
1629                     <code class="classname">Trigger_Policy</code>
1630                   </td><td align="left">
1631                     <code class="classname">hash_load_check_resize_trigger</code> with
1632                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1633                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.observations"></a>
1634             Observations
1635           </h6></div></div></div><p>See Observations::Mapping-Semantics
1636           Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_find_large"></a>
1637           Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios
1638         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.info"></a>
1639             Description
1640           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1641           first item of each pair is a string from an arbitrary text
1642           [wickland96thirty], and
1643           the second is a uniform integer. The container is a
1644           "multimap" - it considers the first member of each pair as a
1645           primary key, and the second member of each pair as a secondary
1646           key. There
1647           are 400 distinct primary keys, and the ratio of secondary keys
1648           to primary keys ranges from 1 to 5.</p><p>The test measures the average find-time as a function of the
1649           number of values inserted. For this library's containers, it
1650           finds the secondary key from a container obtained from finding
1651           a primary key. For the native multimaps, it searches a range
1652           obtained using <code class="classname">std::equal_range</code> on a primary key.</p><p>
1653             It uses the test file:
1654             <code class="filename">performance/ext/pb_ds/multimap_text_find_timing_large.cc</code>
1655           </p><p>The test checks the find-time scalability of different
1656           "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.results"></a>
1657             Results
1658           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
1659           use a tree-based container for primary keys.
1660           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_tree.png" align="middle" /></div></div><p>
1661             The abbreviated names in the legend of the graphic above are
1662             instantiated with the types in the following table.
1663           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1664                     n_mmap
1665                   </td></tr><tr><td align="left">
1666                     <code class="classname">std::multimap</code>
1667                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1668                     rb_tree_mmap_lu_mtf_set
1669                   </td></tr><tr><td rowspan="3" align="left" valign="top">
1670                     <code class="classname">tree</code>
1671                   </td><td align="left">
1672                     <code class="classname">Tag</code>
1673                   </td><td align="left">
1674                     <code class="classname">rb_tree_tag</code>
1675                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1676                     <code class="classname">Node_Update</code>
1677                   </td><td align="left">
1678                     <code class="classname">null_node_update</code>
1679                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1680                     <code class="classname">Mapped</code>
1681                   </td><td align="left">
1682                     <code class="classname">list_update</code>
1683                   </td><td align="left">
1684                     <code class="classname">Update_Policy</code>
1685                   </td><td align="left">
1686                     <code class="classname">lu_move_to_front_policy</code>
1687                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1688                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1689                   </td></tr><tr><td rowspan="5" align="left" valign="top">
1690                     <code class="classname">tree</code>
1691                   </td><td align="left">
1692                     <code class="classname">Tag</code>
1693                   </td><td align="left">
1694                     <code class="classname">rb_tree_tag</code>
1695                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1696                     <code class="classname">Node_Update</code>
1697                   </td><td align="left">
1698                     <code class="classname">null_node_update</code>
1699                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1700                     <code class="classname">Mapped</code>
1701                   </td><td rowspan="3" align="left" valign="top">
1702                     <code class="classname">cc_hash_table</code>
1703                   </td><td align="left">
1704                     <code class="classname">Comb_Hash_Fn</code>
1705                   </td><td align="left">
1706                     <code class="classname">direct_mask_range_hashing</code>
1707                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1708                     <code class="classname">Resize_Policy</code>
1709                   </td><td rowspan="2" align="left" valign="top">
1710                     <code class="classname">hash_standard_resize_policy</code>
1711                   </td><td align="left">
1712                     <code class="classname">Size_Policy</code>
1713                   </td><td align="left">
1714                     <code class="classname">hash_exponential_size_policy</code>
1715                   </td></tr><tr><td align="left" valign="top">
1716                     <code class="classname">Trigger_Policy</code>
1717                   </td><td align="left">
1718                     <code class="classname">hash_load_check_resize_trigger</code> with
1719                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1720                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
1721           use a hash-based container for primary keys.
1722           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
1723             The abbreviated names in the legend of the graphic above are
1724             instantiated with the types in the following table.
1725           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1726                     n_hash_mmap
1727                   </td></tr><tr><td align="left">
1728                     <code class="classname">std::tr1::unordered_multimap</code>
1729                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1730                     rb_tree_mmap_lu_mtf_set
1731                   </td></tr><tr><td rowspan="4" align="left" valign="top">
1732                     <code class="classname">
1733                       cc_hash_table
1734                     </code>
1735                   </td><td align="left">
1736                     <code class="classname">Comb_Hash_Fn</code>
1737                   </td><td align="left">
1738                     <code class="classname">direct_mask_range_hashing</code>
1739                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1740                     <code class="classname">Resize_Policy</code>
1741                   </td><td rowspan="2" align="left" valign="top">
1742                     <code class="classname">hash_standard_resize_policy</code>
1743                   </td><td align="left">
1744                     <code class="classname">Size_Policy</code>
1745                   </td><td align="left">
1746                     <code class="classname">hash_exponential_size_policy</code>
1747                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1748                     <code class="classname">Trigger_Policy</code>
1749                   </td><td align="left">
1750                     <code class="classname">hash_load_check_resize_trigger</code> with
1751                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1752                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
1753                     <code class="classname">Mapped</code>
1754                   </td><td align="left">
1755                     <code class="classname">list_update</code>
1756                   </td><td align="left">
1757                     <code class="classname">Update_Policy</code>
1758                   </td><td align="left">
1759                     <code class="classname">lu_move_to_front_policy</code>
1760                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1761                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1762                   </td></tr><tr><td rowspan="6" align="left" valign="top">
1763                     <code class="classname">
1764                       cc_hash_table
1765                     </code>
1766                   </td><td align="left">
1767                     <code class="classname">Comb_Hash_Fn</code>
1768                   </td><td align="left">
1769                     <code class="classname">direct_mask_range_hashing</code>
1770                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1771                     <code class="classname">Resize_Policy</code>
1772                   </td><td rowspan="2" align="left" valign="top">
1773                     <code class="classname">hash_standard_resize_policy</code>
1774                   </td><td align="left">
1775                     <code class="classname">Size_Policy</code>
1776                   </td><td align="left">
1777                     <code class="classname">hash_exponential_size_policy</code>
1778                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1779                     <code class="classname">Trigger_Policy</code>
1780                   </td><td align="left">
1781                     <code class="classname">hash_load_check_resize_trigger</code> with
1782                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1783                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1784                     <code class="classname">Mapped</code>
1785                   </td><td rowspan="3" align="left" valign="top">
1786                     <code class="classname">cc_hash_table</code>
1787                   </td><td align="left">
1788                     <code class="classname">Comb_Hash_Fn</code>
1789                   </td><td align="left">
1790                     <code class="classname">direct_mask_range_hashing</code>
1791                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1792                     <code class="classname">Resize_Policy</code>
1793                   </td><td rowspan="2" align="left" valign="top">
1794                     <code class="classname">hash_standard_resize_policy</code>
1795                   </td><td align="left">
1796                     <code class="classname">Size_Policy</code>
1797                   </td><td align="left">
1798                     <code class="classname">hash_exponential_size_policy</code>
1799                   </td></tr><tr><td align="left" valign="top">
1800                     <code class="classname">Trigger_Policy</code>
1801                   </td><td align="left">
1802                     <code class="classname">hash_load_check_resize_trigger</code> with
1803                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1804                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.observations"></a>
1805             Observations
1806           </h6></div></div></div><p>See Observations::Mapping-Semantics
1807           Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_small"></a>
1808           Text <code class="function">insert</code> with Small
1809           Secondary-to-Primary Key Ratios
1810         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.info"></a>
1811             Description
1812           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1813           first item of each pair is a string from an arbitrary text
1814           [wickland96thirty], and
1815           the second is a uniform integer. The container is a
1816           "multimap" - it considers the first member of each pair as a
1817           primary key, and the second member of each pair as a secondary
1818           key. There
1819           are 400 distinct primary keys, and the ratio of secondary keys
1820           to primary keys ranges from 1 to 5.</p><p>The test measures the average insert-time as a function of
1821           the number of values inserted. For this library's containers,
1822           it inserts a primary key into the primary associative
1823           container, then a secondary key into the secondary associative
1824           container. For the native multimaps, it obtains a range using
1825           <code class="classname">std::equal_range</code>, and inserts a value only if it was
1826           not contained already.</p><p>
1827             It uses the test file:
1828             <code class="filename">performance/ext/pb_ds/multimap_text_insert_timing_small.cc</code>
1829           </p><p>The test checks the insert-time scalability of different
1830           "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.results"></a>
1831             Results
1832           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
1833           use a tree-based container for primary keys.
1834           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_small_s2p_tree.png" align="middle" /></div></div><p>
1835             The abbreviated names in the legend of the graphic above are
1836             instantiated with the types in the following table.
1837           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1838                     n_mmap
1839                   </td></tr><tr><td align="left">
1840                     <code class="classname">std::multimap</code>
1841                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1842                     rb_tree_mmap_lu_mtf_set
1843                   </td></tr><tr><td rowspan="3" align="left" valign="top">
1844                     <code class="classname">tree</code>
1845                   </td><td align="left">
1846                     <code class="classname">Tag</code>
1847                   </td><td align="left">
1848                     <code class="classname">rb_tree_tag</code>
1849                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1850                     <code class="classname">Node_Update</code>
1851                   </td><td align="left">
1852                     <code class="classname">null_node_update</code>
1853                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1854                     <code class="classname">Mapped</code>
1855                   </td><td align="left">
1856                     <code class="classname">list_update</code>
1857                   </td><td align="left">
1858                     <code class="classname">Update_Policy</code>
1859                   </td><td align="left">
1860                     <code class="classname">lu_move_to_front_policy</code>
1861                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1862                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1863                   </td></tr><tr><td rowspan="5" align="left" valign="top">
1864                     <code class="classname">tree</code>
1865                   </td><td align="left">
1866                     <code class="classname">Tag</code>
1867                   </td><td align="left">
1868                     <code class="classname">rb_tree_tag</code>
1869                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
1870                     <code class="classname">Node_Update</code>
1871                   </td><td align="left">
1872                     <code class="classname">null_node_update</code>
1873                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1874                     <code class="classname">Mapped</code>
1875                   </td><td rowspan="3" align="left" valign="top">
1876                     <code class="classname">cc_hash_table</code>
1877                   </td><td align="left">
1878                     <code class="classname">Comb_Hash_Fn</code>
1879                   </td><td align="left">
1880                     <code class="classname">direct_mask_range_hashing</code>
1881                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1882                     <code class="classname">Resize_Policy</code>
1883                   </td><td rowspan="2" align="left" valign="top">
1884                     <code class="classname">hash_standard_resize_policy</code>
1885                   </td><td align="left">
1886                     <code class="classname">Size_Policy</code>
1887                   </td><td align="left">
1888                     <code class="classname">hash_exponential_size_policy</code>
1889                   </td></tr><tr><td align="left" valign="top">
1890                     <code class="classname">Trigger_Policy</code>
1891                   </td><td align="left">
1892                     <code class="classname">hash_load_check_resize_trigger</code> with
1893                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1894                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
1895           use a hash-based container for primary keys.
1896           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" align="middle" /></div></div><p>
1897             The abbreviated names in the legend of the graphic above are
1898             instantiated with the types in the following table.
1899           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1900                     n_hash_mmap
1901                   </td></tr><tr><td align="left">
1902                     <code class="classname">std::tr1::unordered_multimap</code>
1903                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1904                     rb_tree_mmap_lu_mtf_set
1905                   </td></tr><tr><td rowspan="4" align="left" valign="top">
1906                     <code class="classname">
1907                       cc_hash_table
1908                     </code>
1909                   </td><td align="left">
1910                     <code class="classname">Comb_Hash_Fn</code>
1911                   </td><td align="left">
1912                     <code class="classname">direct_mask_range_hashing</code>
1913                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1914                     <code class="classname">Resize_Policy</code>
1915                   </td><td rowspan="2" align="left" valign="top">
1916                     <code class="classname">hash_standard_resize_policy</code>
1917                   </td><td align="left">
1918                     <code class="classname">Size_Policy</code>
1919                   </td><td align="left">
1920                     <code class="classname">hash_exponential_size_policy</code>
1921                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1922                     <code class="classname">Trigger_Policy</code>
1923                   </td><td align="left">
1924                     <code class="classname">hash_load_check_resize_trigger</code> with
1925                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1926                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
1927                     <code class="classname">Mapped</code>
1928                   </td><td align="left">
1929                     <code class="classname">list_update</code>
1930                   </td><td align="left">
1931                     <code class="classname">Update_Policy</code>
1932                   </td><td align="left">
1933                     <code class="classname">lu_move_to_front_policy</code>
1934                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
1935                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
1936                   </td></tr><tr><td rowspan="6" align="left" valign="top">
1937                     <code class="classname">
1938                       cc_hash_table
1939                     </code>
1940                   </td><td align="left">
1941                     <code class="classname">Comb_Hash_Fn</code>
1942                   </td><td align="left">
1943                     <code class="classname">direct_mask_range_hashing</code>
1944                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1945                     <code class="classname">Resize_Policy</code>
1946                   </td><td rowspan="2" align="left" valign="top">
1947                     <code class="classname">hash_standard_resize_policy</code>
1948                   </td><td align="left">
1949                     <code class="classname">Size_Policy</code>
1950                   </td><td align="left">
1951                     <code class="classname">hash_exponential_size_policy</code>
1952                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
1953                     <code class="classname">Trigger_Policy</code>
1954                   </td><td align="left">
1955                     <code class="classname">hash_load_check_resize_trigger</code> with
1956                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1957                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
1958                     <code class="classname">Mapped</code>
1959                   </td><td rowspan="3" align="left" valign="top">
1960                     <code class="classname">cc_hash_table</code>
1961                   </td><td align="left">
1962                     <code class="classname">Comb_Hash_Fn</code>
1963                   </td><td align="left">
1964                     <code class="classname">direct_mask_range_hashing</code>
1965                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
1966                     <code class="classname">Resize_Policy</code>
1967                   </td><td rowspan="2" align="left" valign="top">
1968                     <code class="classname">hash_standard_resize_policy</code>
1969                   </td><td align="left">
1970                     <code class="classname">Size_Policy</code>
1971                   </td><td align="left">
1972                     <code class="classname">hash_exponential_size_policy</code>
1973                   </td></tr><tr><td align="left" valign="top">
1974                     <code class="classname">Trigger_Policy</code>
1975                   </td><td align="left">
1976                     <code class="classname">hash_load_check_resize_trigger</code> with
1977                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
1978                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.observations"></a>
1979             Observations
1980           </h6></div></div></div><p>See Observations::Mapping-Semantics
1981           Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_large"></a>
1982           Text <code class="function">insert</code> with Small
1983           Secondary-to-Primary Key Ratios
1984         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.info"></a>
1985             Description
1986           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
1987           first item of each pair is a string from an arbitrary text
1988           [wickland96thirty], and
1989           the second is a uniform integer. The container is a
1990           "multimap" - it considers the first member of each pair as a
1991           primary key, and the second member of each pair as a secondary
1992           key. There
1993           are 400 distinct primary keys, and the ratio of secondary keys
1994           to primary keys ranges from 1 to 5.</p><p>The test measures the average insert-time as a function of
1995           the number of values inserted. For this library's containers,
1996           it inserts a primary key into the primary associative
1997           container, then a secondary key into the secondary associative
1998           container. For the native multimaps, it obtains a range using
1999           <code class="classname">std::equal_range</code>, and inserts a value only if it was
2000           not contained already.</p><p>
2001             It uses the test file:
2002             <code class="filename">performance/ext/pb_ds/multimap_text_insert_timing_large.cc</code>
2003           </p><p>The test checks the insert-time scalability of different
2004           "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.results"></a>
2005             Results
2006           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
2007           use a tree-based container for primary keys.
2008           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_large_s2p_tree.png" align="middle" /></div></div><p>
2009             The abbreviated names in the legend of the graphic above are
2010             instantiated with the types in the following table.
2011           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2012                     n_mmap
2013                   </td></tr><tr><td align="left">
2014                     <code class="classname">std::multimap</code>
2015                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2016                     rb_tree_mmap_lu_mtf_set
2017                   </td></tr><tr><td rowspan="3" align="left" valign="top">
2018                     <code class="classname">tree</code>
2019                   </td><td align="left">
2020                     <code class="classname">Tag</code>
2021                   </td><td align="left">
2022                     <code class="classname">rb_tree_tag</code>
2023                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2024                     <code class="classname">Node_Update</code>
2025                   </td><td align="left">
2026                     <code class="classname">null_node_update</code>
2027                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2028                     <code class="classname">Mapped</code>
2029                   </td><td align="left">
2030                     <code class="classname">list_update</code>
2031                   </td><td align="left">
2032                     <code class="classname">Update_Policy</code>
2033                   </td><td align="left">
2034                     <code class="classname">lu_move_to_front_policy</code>
2035                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2036                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2037                   </td></tr><tr><td rowspan="5" align="left" valign="top">
2038                     <code class="classname">tree</code>
2039                   </td><td align="left">
2040                     <code class="classname">Tag</code>
2041                   </td><td align="left">
2042                     <code class="classname">rb_tree_tag</code>
2043                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2044                     <code class="classname">Node_Update</code>
2045                   </td><td align="left">
2046                     <code class="classname">null_node_update</code>
2047                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2048                     <code class="classname">Mapped</code>
2049                   </td><td rowspan="3" align="left" valign="top">
2050                     <code class="classname">cc_hash_table</code>
2051                   </td><td align="left">
2052                     <code class="classname">Comb_Hash_Fn</code>
2053                   </td><td align="left">
2054                     <code class="classname">direct_mask_range_hashing</code>
2055                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2056                     <code class="classname">Resize_Policy</code>
2057                   </td><td rowspan="2" align="left" valign="top">
2058                     <code class="classname">hash_standard_resize_policy</code>
2059                   </td><td align="left">
2060                     <code class="classname">Size_Policy</code>
2061                   </td><td align="left">
2062                     <code class="classname">hash_exponential_size_policy</code>
2063                   </td></tr><tr><td align="left" valign="top">
2064                     <code class="classname">Trigger_Policy</code>
2065                   </td><td align="left">
2066                     <code class="classname">hash_load_check_resize_trigger</code> with
2067                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2068                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
2069           use a hash-based container for primary keys.
2070           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
2071             The abbreviated names in the legend of the graphic above are
2072             instantiated with the types in the following table.
2073           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2074                     n_hash_mmap
2075                   </td></tr><tr><td align="left">
2076                     <code class="classname">std::tr1::unordered_multimap</code>
2077                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2078                     rb_tree_mmap_lu_mtf_set
2079                   </td></tr><tr><td rowspan="4" align="left" valign="top">
2080                     <code class="classname">
2081                       cc_hash_table
2082                     </code>
2083                   </td><td align="left">
2084                     <code class="classname">Comb_Hash_Fn</code>
2085                   </td><td align="left">
2086                     <code class="classname">direct_mask_range_hashing</code>
2087                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2088                     <code class="classname">Resize_Policy</code>
2089                   </td><td rowspan="2" align="left" valign="top">
2090                     <code class="classname">hash_standard_resize_policy</code>
2091                   </td><td align="left">
2092                     <code class="classname">Size_Policy</code>
2093                   </td><td align="left">
2094                     <code class="classname">hash_exponential_size_policy</code>
2095                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2096                     <code class="classname">Trigger_Policy</code>
2097                   </td><td align="left">
2098                     <code class="classname">hash_load_check_resize_trigger</code> with
2099                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2100                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
2101                     <code class="classname">Mapped</code>
2102                   </td><td align="left">
2103                     <code class="classname">list_update</code>
2104                   </td><td align="left">
2105                     <code class="classname">Update_Policy</code>
2106                   </td><td align="left">
2107                     <code class="classname">lu_move_to_front_policy</code>
2108                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2109                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2110                   </td></tr><tr><td rowspan="6" align="left" valign="top">
2111                     <code class="classname">
2112                       cc_hash_table
2113                     </code>
2114                   </td><td align="left">
2115                     <code class="classname">Comb_Hash_Fn</code>
2116                   </td><td align="left">
2117                     <code class="classname">direct_mask_range_hashing</code>
2118                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2119                     <code class="classname">Resize_Policy</code>
2120                   </td><td rowspan="2" align="left" valign="top">
2121                     <code class="classname">hash_standard_resize_policy</code>
2122                   </td><td align="left">
2123                     <code class="classname">Size_Policy</code>
2124                   </td><td align="left">
2125                     <code class="classname">hash_exponential_size_policy</code>
2126                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2127                     <code class="classname">Trigger_Policy</code>
2128                   </td><td align="left">
2129                     <code class="classname">hash_load_check_resize_trigger</code> with
2130                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2131                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2132                     <code class="classname">Mapped</code>
2133                   </td><td rowspan="3" align="left" valign="top">
2134                     <code class="classname">cc_hash_table</code>
2135                   </td><td align="left">
2136                     <code class="classname">Comb_Hash_Fn</code>
2137                   </td><td align="left">
2138                     <code class="classname">direct_mask_range_hashing</code>
2139                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2140                     <code class="classname">Resize_Policy</code>
2141                   </td><td rowspan="2" align="left" valign="top">
2142                     <code class="classname">hash_standard_resize_policy</code>
2143                   </td><td align="left">
2144                     <code class="classname">Size_Policy</code>
2145                   </td><td align="left">
2146                     <code class="classname">hash_exponential_size_policy</code>
2147                   </td></tr><tr><td align="left" valign="top">
2148                     <code class="classname">Trigger_Policy</code>
2149                   </td><td align="left">
2150                     <code class="classname">hash_load_check_resize_trigger</code> with
2151                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2152                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.observations"></a>
2153             Observations
2154           </h6></div></div></div><p>See Observations::Mapping-Semantics
2155           Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_mem_small"></a>
2156           Text <code class="function">insert</code> with Small
2157           Secondary-to-Primary Key Ratios Memory Use
2158         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.info"></a>
2159             Description
2160           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
2161           first item of each pair is a string from an arbitrary text
2162           [wickland96thirty], and
2163           the second is a uniform integer. The container is a
2164           "multimap" - it considers the first member of each pair as a
2165           primary key, and the second member of each pair as a secondary
2166           key. There
2167           are 100 distinct primary keys, and the ratio of secondary keys
2168           to primary keys ranges to about 20.</p><p>The test measures the memory use as a function of the number
2169           of values inserted.</p><p>
2170             It uses the test file:
2171             <code class="filename">performance/ext/pb_ds/multimap_text_insert_mem_usage_small.cc</code>
2172           </p><p>The test checks the memory scalability of different
2173           "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.results"></a>
2174             Results
2175           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
2176           use a tree-based container for primary keys.
2177           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_mem_small_s2p_tree.png" align="middle" /></div></div><p>
2178             The abbreviated names in the legend of the graphic above are
2179             instantiated with the types in the following table.
2180           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2181                     n_mmap
2182                   </td></tr><tr><td align="left">
2183                     <code class="classname">std::multimap</code>
2184                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2185                     rb_tree_mmap_lu_mtf_set
2186                   </td></tr><tr><td rowspan="3" align="left" valign="top">
2187                     <code class="classname">tree</code>
2188                   </td><td align="left">
2189                     <code class="classname">Tag</code>
2190                   </td><td align="left">
2191                     <code class="classname">rb_tree_tag</code>
2192                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2193                     <code class="classname">Node_Update</code>
2194                   </td><td align="left">
2195                     <code class="classname">null_node_update</code>
2196                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2197                     <code class="classname">Mapped</code>
2198                   </td><td align="left">
2199                     <code class="classname">list_update</code>
2200                   </td><td align="left">
2201                     <code class="classname">Update_Policy</code>
2202                   </td><td align="left">
2203                     <code class="classname">lu_move_to_front_policy</code>
2204                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2205                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2206                   </td></tr><tr><td rowspan="5" align="left" valign="top">
2207                     <code class="classname">tree</code>
2208                   </td><td align="left">
2209                     <code class="classname">Tag</code>
2210                   </td><td align="left">
2211                     <code class="classname">rb_tree_tag</code>
2212                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2213                     <code class="classname">Node_Update</code>
2214                   </td><td align="left">
2215                     <code class="classname">null_node_update</code>
2216                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2217                     <code class="classname">Mapped</code>
2218                   </td><td rowspan="3" align="left" valign="top">
2219                     <code class="classname">cc_hash_table</code>
2220                   </td><td align="left">
2221                     <code class="classname">Comb_Hash_Fn</code>
2222                   </td><td align="left">
2223                     <code class="classname">direct_mask_range_hashing</code>
2224                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2225                     <code class="classname">Resize_Policy</code>
2226                   </td><td rowspan="2" align="left" valign="top">
2227                     <code class="classname">hash_standard_resize_policy</code>
2228                   </td><td align="left">
2229                     <code class="classname">Size_Policy</code>
2230                   </td><td align="left">
2231                     <code class="classname">hash_exponential_size_policy</code>
2232                   </td></tr><tr><td align="left" valign="top">
2233                     <code class="classname">Trigger_Policy</code>
2234                   </td><td align="left">
2235                     <code class="classname">hash_load_check_resize_trigger</code> with
2236                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2237                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
2238           use a hash-based container for primary keys.
2239           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
2240             The abbreviated names in the legend of the graphic above are
2241             instantiated with the types in the following table.
2242           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2243                     n_hash_mmap
2244                   </td></tr><tr><td align="left">
2245                     <code class="classname">std::tr1::unordered_multimap</code>
2246                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2247                     rb_tree_mmap_lu_mtf_set
2248                   </td></tr><tr><td rowspan="4" align="left" valign="top">
2249                     <code class="classname">
2250                       cc_hash_table
2251                     </code>
2252                   </td><td align="left">
2253                     <code class="classname">Comb_Hash_Fn</code>
2254                   </td><td align="left">
2255                     <code class="classname">direct_mask_range_hashing</code>
2256                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2257                     <code class="classname">Resize_Policy</code>
2258                   </td><td rowspan="2" align="left" valign="top">
2259                     <code class="classname">hash_standard_resize_policy</code>
2260                   </td><td align="left">
2261                     <code class="classname">Size_Policy</code>
2262                   </td><td align="left">
2263                     <code class="classname">hash_exponential_size_policy</code>
2264                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2265                     <code class="classname">Trigger_Policy</code>
2266                   </td><td align="left">
2267                     <code class="classname">hash_load_check_resize_trigger</code> with
2268                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2269                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
2270                     <code class="classname">Mapped</code>
2271                   </td><td align="left">
2272                     <code class="classname">list_update</code>
2273                   </td><td align="left">
2274                     <code class="classname">Update_Policy</code>
2275                   </td><td align="left">
2276                     <code class="classname">lu_move_to_front_policy</code>
2277                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2278                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2279                   </td></tr><tr><td rowspan="6" align="left" valign="top">
2280                     <code class="classname">
2281                       cc_hash_table
2282                     </code>
2283                   </td><td align="left">
2284                     <code class="classname">Comb_Hash_Fn</code>
2285                   </td><td align="left">
2286                     <code class="classname">direct_mask_range_hashing</code>
2287                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2288                     <code class="classname">Resize_Policy</code>
2289                   </td><td rowspan="2" align="left" valign="top">
2290                     <code class="classname">hash_standard_resize_policy</code>
2291                   </td><td align="left">
2292                     <code class="classname">Size_Policy</code>
2293                   </td><td align="left">
2294                     <code class="classname">hash_exponential_size_policy</code>
2295                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2296                     <code class="classname">Trigger_Policy</code>
2297                   </td><td align="left">
2298                     <code class="classname">hash_load_check_resize_trigger</code> with
2299                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2300                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2301                     <code class="classname">Mapped</code>
2302                   </td><td rowspan="3" align="left" valign="top">
2303                     <code class="classname">cc_hash_table</code>
2304                   </td><td align="left">
2305                     <code class="classname">Comb_Hash_Fn</code>
2306                   </td><td align="left">
2307                     <code class="classname">direct_mask_range_hashing</code>
2308                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2309                     <code class="classname">Resize_Policy</code>
2310                   </td><td rowspan="2" align="left" valign="top">
2311                     <code class="classname">hash_standard_resize_policy</code>
2312                   </td><td align="left">
2313                     <code class="classname">Size_Policy</code>
2314                   </td><td align="left">
2315                     <code class="classname">hash_exponential_size_policy</code>
2316                   </td></tr><tr><td align="left" valign="top">
2317                     <code class="classname">Trigger_Policy</code>
2318                   </td><td align="left">
2319                     <code class="classname">hash_load_check_resize_trigger</code> with
2320                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2321                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.observations"></a>
2322             Observations
2323           </h6></div></div></div><p>See Observations::Mapping-Semantics
2324           Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_mem_large"></a>
2325           Text <code class="function">insert</code> with Small
2326           Secondary-to-Primary Key Ratios Memory Use
2327         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.info"></a>
2328             Description
2329           </h6></div></div></div><p>This test inserts a number of pairs into a container. The
2330           first item of each pair is a string from an arbitrary text
2331           [wickland96thirty], and
2332           the second is a uniform integer. The container is a
2333           "multimap" - it considers the first member of each pair as a
2334           primary key, and the second member of each pair as a secondary
2335           key. There
2336           are 100 distinct primary keys, and the ratio of secondary keys
2337           to primary keys ranges to about 20.</p><p>The test measures the memory use as a function of the number
2338           of values inserted.</p><p>
2339             It uses the test file:
2340             <code class="filename">performance/ext/pb_ds/multimap_text_insert_mem_usage_large.cc</code>
2341           </p><p>The test checks the memory scalability of different
2342           "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.results"></a>
2343             Results
2344           </h6></div></div></div><p>The graphic below show the results for "multimaps" which
2345           use a tree-based container for primary keys.
2346           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_mem_large_s2p_tree.png" align="middle" /></div></div><p>
2347             The abbreviated names in the legend of the graphic above are
2348             instantiated with the types in the following table.
2349           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2350                     n_mmap
2351                   </td></tr><tr><td align="left">
2352                     <code class="classname">std::multimap</code>
2353                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2354                     rb_tree_mmap_lu_mtf_set
2355                   </td></tr><tr><td rowspan="3" align="left" valign="top">
2356                     <code class="classname">tree</code>
2357                   </td><td align="left">
2358                     <code class="classname">Tag</code>
2359                   </td><td align="left">
2360                     <code class="classname">rb_tree_tag</code>
2361                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2362                     <code class="classname">Node_Update</code>
2363                   </td><td align="left">
2364                     <code class="classname">null_node_update</code>
2365                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2366                     <code class="classname">Mapped</code>
2367                   </td><td align="left">
2368                     <code class="classname">list_update</code>
2369                   </td><td align="left">
2370                     <code class="classname">Update_Policy</code>
2371                   </td><td align="left">
2372                     <code class="classname">lu_move_to_front_policy</code>
2373                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2374                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2375                   </td></tr><tr><td rowspan="5" align="left" valign="top">
2376                     <code class="classname">tree</code>
2377                   </td><td align="left">
2378                     <code class="classname">Tag</code>
2379                   </td><td align="left">
2380                     <code class="classname">rb_tree_tag</code>
2381                   </td><td colspan="4" align="left"> </td></tr><tr><td align="left">
2382                     <code class="classname">Node_Update</code>
2383                   </td><td align="left">
2384                     <code class="classname">null_node_update</code>
2385                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2386                     <code class="classname">Mapped</code>
2387                   </td><td rowspan="3" align="left" valign="top">
2388                     <code class="classname">cc_hash_table</code>
2389                   </td><td align="left">
2390                     <code class="classname">Comb_Hash_Fn</code>
2391                   </td><td align="left">
2392                     <code class="classname">direct_mask_range_hashing</code>
2393                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2394                     <code class="classname">Resize_Policy</code>
2395                   </td><td rowspan="2" align="left" valign="top">
2396                     <code class="classname">hash_standard_resize_policy</code>
2397                   </td><td align="left">
2398                     <code class="classname">Size_Policy</code>
2399                   </td><td align="left">
2400                     <code class="classname">hash_exponential_size_policy</code>
2401                   </td></tr><tr><td align="left" valign="top">
2402                     <code class="classname">Trigger_Policy</code>
2403                   </td><td align="left">
2404                     <code class="classname">hash_load_check_resize_trigger</code> with
2405                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2406                   </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
2407           use a hash-based container for primary keys.
2408           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
2409             The abbreviated names in the legend of the graphic above are
2410             instantiated with the types in the following table.
2411           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2412                     n_hash_mmap
2413                   </td></tr><tr><td align="left">
2414                     <code class="classname">std::tr1::unordered_multimap</code>
2415                   </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2416                     rb_tree_mmap_lu_mtf_set
2417                   </td></tr><tr><td rowspan="4" align="left" valign="top">
2418                     <code class="classname">
2419                       cc_hash_table
2420                     </code>
2421                   </td><td align="left">
2422                     <code class="classname">Comb_Hash_Fn</code>
2423                   </td><td align="left">
2424                     <code class="classname">direct_mask_range_hashing</code>
2425                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2426                     <code class="classname">Resize_Policy</code>
2427                   </td><td rowspan="2" align="left" valign="top">
2428                     <code class="classname">hash_standard_resize_policy</code>
2429                   </td><td align="left">
2430                     <code class="classname">Size_Policy</code>
2431                   </td><td align="left">
2432                     <code class="classname">hash_exponential_size_policy</code>
2433                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2434                     <code class="classname">Trigger_Policy</code>
2435                   </td><td align="left">
2436                     <code class="classname">hash_load_check_resize_trigger</code> with
2437                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2438                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left">
2439                     <code class="classname">Mapped</code>
2440                   </td><td align="left">
2441                     <code class="classname">list_update</code>
2442                   </td><td align="left">
2443                     <code class="classname">Update_Policy</code>
2444                   </td><td align="left">
2445                     <code class="classname">lu_move_to_front_policy</code>
2446                   </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left">
2447                     rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set
2448                   </td></tr><tr><td rowspan="6" align="left" valign="top">
2449                     <code class="classname">
2450                       cc_hash_table
2451                     </code>
2452                   </td><td align="left">
2453                     <code class="classname">Comb_Hash_Fn</code>
2454                   </td><td align="left">
2455                     <code class="classname">direct_mask_range_hashing</code>
2456                   </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2457                     <code class="classname">Resize_Policy</code>
2458                   </td><td rowspan="2" align="left" valign="top">
2459                     <code class="classname">hash_standard_resize_policy</code>
2460                   </td><td align="left">
2461                     <code class="classname">Size_Policy</code>
2462                   </td><td align="left">
2463                     <code class="classname">hash_exponential_size_policy</code>
2464                   </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top">
2465                     <code class="classname">Trigger_Policy</code>
2466                   </td><td align="left">
2467                     <code class="classname">hash_load_check_resize_trigger</code> with
2468                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2469                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top">
2470                     <code class="classname">Mapped</code>
2471                   </td><td rowspan="3" align="left" valign="top">
2472                     <code class="classname">cc_hash_table</code>
2473                   </td><td align="left">
2474                     <code class="classname">Comb_Hash_Fn</code>
2475                   </td><td align="left">
2476                     <code class="classname">direct_mask_range_hashing</code>
2477                   </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top">
2478                     <code class="classname">Resize_Policy</code>
2479                   </td><td rowspan="2" align="left" valign="top">
2480                     <code class="classname">hash_standard_resize_policy</code>
2481                   </td><td align="left">
2482                     <code class="classname">Size_Policy</code>
2483                   </td><td align="left">
2484                     <code class="classname">hash_exponential_size_policy</code>
2485                   </td></tr><tr><td align="left" valign="top">
2486                     <code class="classname">Trigger_Policy</code>
2487                   </td><td align="left">
2488                     <code class="classname">hash_load_check_resize_trigger</code> with
2489                     α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
2490                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.observations"></a>
2491             Observations
2492           </h6></div></div></div><p>See Observations::Mapping-Semantics
2493           Considerations.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.priority_queue"></a>Priority Queue</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push"></a>
2494           Text <code class="function">push</code>
2495         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.info"></a>
2496             Description
2497           </h6></div></div></div><p>This test inserts a number of values with keys from an
2498           arbitrary text ([ wickland96thirty ]) into
2499           a container using <code class="function">push</code>. It measures the average time
2500           for <code class="function">push</code> as a function of the number of values
2501           pushed.</p><p>
2502             It uses the test file:
2503             <code class="filename">performance/ext/pb_ds/priority_queue_text_push_timing.cc</code>
2504           </p><p>The test checks the effect of different underlying data
2505           structures.
2506           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.results"></a>
2507             Results
2508           </h6></div></div></div><p>The two graphics below show the results for the native
2509           priority_queues and this library's priority_queues.
2510           </p><p>The graphic immediately below shows the results for the
2511           native priority_queue type instantiated with different underlying
2512           container types versus several different versions of library's
2513           priority_queues.
2514           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_push.png" align="middle" /></div></div><p>
2515             The abbreviated names in the legend of the graphic above are
2516             instantiated with the types in the following table.
2517           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2518                     n_pq_vector
2519                   </td></tr><tr><td align="left">
2520                     <code class="classname">std::priority_queue</code>
2521                   </td><td align="left">
2522                     <code class="classname">Sequence</code>
2523                   </td><td align="left">
2524                     <code class="classname">std::vector</code>
2525                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2526                     n_pq_deque
2527                   </td></tr><tr><td align="left">
2528                     <code class="classname">std::priority_queue</code>
2529                   </td><td align="left">
2530                     <code class="classname">Sequence</code>
2531                   </td><td align="left">
2532                     <code class="classname">std::deque</code>
2533                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2534                     binary_heap
2535                   </td></tr><tr><td align="left">
2536                     <code class="classname">priority_queue</code>
2537                   </td><td align="left">
2538                     <code class="classname">Tag</code>
2539                   </td><td align="left">
2540                     <code class="classname">binary_heap_tag</code>
2541                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2542                     binomial_heap
2543                   </td></tr><tr><td align="left">
2544                     <code class="classname">priority_queue</code>
2545                   </td><td align="left">
2546                     <code class="classname">Tag</code>
2547                   </td><td align="left">
2548                     <code class="classname">binomial_heap_tag</code>
2549                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2550                     rc_binomial_heap
2551                   </td></tr><tr><td align="left">
2552                     <code class="classname">priority_queue</code>
2553                   </td><td align="left">
2554                     <code class="classname">Tag</code>
2555                   </td><td align="left">
2556                     <code class="classname">rc_binomial_heap_tag</code>
2557                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2558                     thin_heap
2559                   </td></tr><tr><td align="left">
2560                     <code class="classname">priority_queue</code>
2561                   </td><td align="left">
2562                     <code class="classname">Tag</code>
2563                   </td><td align="left">
2564                     <code class="classname">thin_heap_tag</code>
2565                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2566                     pairing_heap
2567                   </td></tr><tr><td align="left">
2568                     <code class="classname">priority_queue</code>
2569                   </td><td align="left">
2570                     <code class="classname">Tag</code>
2571                   </td><td align="left">
2572                     <code class="classname">pairing_heap_tag</code>
2573                   </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap
2574           based native priority queues and this library's pairing-heap
2575           priority_queue data structures.
2576           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_push.png" align="middle" /></div></div><p>
2577             The abbreviated names in the legend of the graphic above are
2578             instantiated with the types in the following table.
2579           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2580                     n_pq_vector
2581                   </td></tr><tr><td align="left">
2582                     <code class="classname">std::priority_queue</code>
2583                   </td><td align="left">
2584                     <code class="classname">Sequence</code>
2585                   </td><td align="left">
2586                     <code class="classname">std::vector</code>
2587                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2588                     n_pq_deque
2589                   </td></tr><tr><td align="left">
2590                     <code class="classname">std::priority_queue</code>
2591                   </td><td align="left">
2592                     <code class="classname">Sequence</code>
2593                   </td><td align="left">
2594                     <code class="classname">std::deque</code>
2595                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2596                     thin_heap
2597                   </td></tr><tr><td align="left">
2598                     <code class="classname">priority_queue</code>
2599                   </td><td align="left">
2600                     <code class="classname">Tag</code>
2601                   </td><td align="left">
2602                     <code class="classname">thin_heap_tag</code>
2603                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2604                     pairing_heap
2605                   </td></tr><tr><td align="left">
2606                     <code class="classname">priority_queue</code>
2607                   </td><td align="left">
2608                     <code class="classname">Tag</code>
2609                   </td><td align="left">
2610                     <code class="classname">pairing_heap_tag</code>
2611                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.observations"></a>
2612             Observations
2613           </h6></div></div></div><p>Pairing heaps (<code class="classname">priority_queue</code> with
2614           <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>)
2615           are the most suited for sequences of <code class="function">push</code> and
2616           <code class="function">pop</code> operations of non-primitive types (e.g.
2617           <code class="classname">std::string</code>s). (See Priority Queue
2618           Text <code class="function">push</code> and <code class="function">pop</code> Timing Test.) They are
2619           less constrained than binomial heaps, e.g., and since
2620           they are node-based, they outperform binary heaps. (See
2621           Priority
2622           Queue Random Integer <code class="function">push</code> Timing Test for the case
2623           of primitive types.)</p><p>The standard's priority queues do not seem to perform well in
2624           this case: the <code class="classname">std::vector</code> implementation needs to
2625           perform a logarithmic sequence of string operations for each
2626           operation, and the deque implementation is possibly hampered by
2627           its need to manipulate a relatively-complex type (deques
2628           support a O(1) <code class="function">push_front</code>, even though it is
2629           not used by <code class="classname">std::priority_queue</code>.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push_pop"></a>
2630           Text <code class="function">push</code> and <code class="function">pop</code>
2631         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.info"></a>
2632             Description
2633           </h6></div></div></div><p>This test inserts a number of values with keys from an
2634           arbitrary text ([ wickland96thirty ]) into
2635           a container using <code class="classname">push</code> , then removes them using
2636           <code class="classname">pop</code> . It measures the average time for <code class="classname">push</code>
2637           as a function of the number of values.</p><p>
2638             It uses the test file:
2639             <code class="filename">performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc</code>
2640           </p><p>The test checks the effect of different underlying data
2641           structures.
2642           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.results"></a>
2643             Results
2644           </h6></div></div></div><p>The two graphics below show the results for the native
2645           priority_queues and this library's priority_queues.
2646           </p><p>The graphic immediately below shows the results for the
2647           native priority_queue type instantiated with different underlying
2648           container types versus several different versions of library's
2649           priority_queues.
2650           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_push_pop.png" align="middle" /></div></div><p>
2651             The abbreviated names in the legend of the graphic above are
2652             instantiated with the types in the following table.
2653           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2654                     n_pq_vector
2655                   </td></tr><tr><td align="left">
2656                     <code class="classname">std::priority_queue</code>
2657                   </td><td align="left">
2658                     <code class="classname">Sequence</code>
2659                   </td><td align="left">
2660                     <code class="classname">std::vector</code>
2661                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2662                     n_pq_deque
2663                   </td></tr><tr><td align="left">
2664                     <code class="classname">std::priority_queue</code>
2665                   </td><td align="left">
2666                     <code class="classname">Sequence</code>
2667                   </td><td align="left">
2668                     <code class="classname">std::deque</code>
2669                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2670                     binary_heap
2671                   </td></tr><tr><td align="left">
2672                     <code class="classname">priority_queue</code>
2673                   </td><td align="left">
2674                     <code class="classname">Tag</code>
2675                   </td><td align="left">
2676                     <code class="classname">binary_heap_tag</code>
2677                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2678                     binomial_heap
2679                   </td></tr><tr><td align="left">
2680                     <code class="classname">priority_queue</code>
2681                   </td><td align="left">
2682                     <code class="classname">Tag</code>
2683                   </td><td align="left">
2684                     <code class="classname">binomial_heap_tag</code>
2685                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2686                     rc_binomial_heap
2687                   </td></tr><tr><td align="left">
2688                     <code class="classname">priority_queue</code>
2689                   </td><td align="left">
2690                     <code class="classname">Tag</code>
2691                   </td><td align="left">
2692                     <code class="classname">rc_binomial_heap_tag</code>
2693                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2694                     thin_heap
2695                   </td></tr><tr><td align="left">
2696                     <code class="classname">priority_queue</code>
2697                   </td><td align="left">
2698                     <code class="classname">Tag</code>
2699                   </td><td align="left">
2700                     <code class="classname">thin_heap_tag</code>
2701                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2702                     pairing_heap
2703                   </td></tr><tr><td align="left">
2704                     <code class="classname">priority_queue</code>
2705                   </td><td align="left">
2706                     <code class="classname">Tag</code>
2707                   </td><td align="left">
2708                     <code class="classname">pairing_heap_tag</code>
2709                   </td></tr></tbody></table></div><p>The graphic below shows the results for the native priority
2710           queues and this library's pairing-heap priority_queue data
2711           structures.
2712           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_push_pop.png" align="middle" /></div></div><p>
2713             The abbreviated names in the legend of the graphic above are
2714             instantiated with the types in the following table.
2715           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2716                     n_pq_vector
2717                   </td></tr><tr><td align="left">
2718                     <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code>
2719                   </td><td align="left">
2720                     <code class="classname">Sequence</code>
2721                   </td><td align="left">
2722                     <code class="classname">std::vector</code>
2723                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2724                     n_pq_deque
2725                   </td></tr><tr><td align="left">
2726                     <code class="classname">std::priority_queue</code>
2727                   </td><td align="left">
2728                     <code class="classname">Sequence</code>
2729                   </td><td align="left">
2730                     <code class="classname">std::deque</code>
2731                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2732                     pairing_heap
2733                   </td></tr><tr><td align="left">
2734                     <code class="classname">priority_queue</code>
2735                   </td><td align="left">
2736                     <code class="classname">Tag</code>
2737                   </td><td align="left">
2738                     <code class="classname">pairing_heap_tag</code>
2739                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.observations"></a>
2740             Observations
2741           </h6></div></div></div><p>These results are very similar to Priority Queue Text
2742           <code class="function">push</code> Timing Test. As stated there, pairing heaps
2743           (<code class="classname">priority_queue</code> with
2744           <code class="classname">Tag</code>
2745           = <code class="classname">pairing_heap_tag</code>) are most suited
2746           for <code class="function">push</code> and <code class="function">pop</code>
2747           sequences of non-primitive types such as strings. Observing these
2748           two tests, one can note that a pairing heap outperforms the others
2749           in terms of <code class="function">push</code> operations, but equals
2750           binary heaps (<code class="classname">priority_queue</code> with
2751           <code class="classname">Tag</code>
2752           = <code class="classname">binary_heap_tag</code>) if the number
2753           of <code class="function">push</code> and <code class="function">pop</code>
2754           operations is equal. As the number of <code class="function">pop</code>
2755           operations is at most equal to the number
2756           of <code class="function">push</code> operations, pairing heaps are better
2757           in this case. See Priority Queue Random
2758           Integer <code class="function">push</code> and <code class="function">pop</code>
2759           Timing Test for a case which is different.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push"></a>
2760           Integer <code class="function">push</code>
2761         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.info"></a>
2762             Description
2763           </h6></div></div></div><p>This test inserts a number of values with integer keys
2764           into a container using <code class="function">push</code>. It
2765           measures the average time for <code class="function">push</code> as a
2766           function of the number of values.</p><p>
2767             It uses the test file:
2768             <code class="filename">performance/ext/pb_ds/priority_queue_random_int_push_timing.cc</code>
2769           </p><p>The test checks the effect of different underlying data
2770           structures.
2771           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.results"></a>
2772             Results
2773           </h6></div></div></div><p>The two graphics below show the results for the native
2774           priority_queues and this library's priority_queues.
2775           </p><p>The graphic immediately below shows the results for the
2776           native priority_queue type instantiated with different underlying
2777           container types versus several different versions of library's
2778           priority_queues.
2779           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_int_push.png" align="middle" /></div></div><p>
2780             The abbreviated names in the legend of the graphic above are
2781             instantiated with the types in the following table.
2782           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2783                     n_pq_vector
2784                   </td></tr><tr><td align="left">
2785                     <code class="classname">std::priority_queue</code>
2786                   </td><td align="left">
2787                     <code class="classname">Sequence</code>
2788                   </td><td align="left">
2789                     <code class="classname">std::vector</code>
2790                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2791                     n_pq_deque
2792                   </td></tr><tr><td align="left">
2793                     <code class="classname">std::priority_queue</code>
2794                   </td><td align="left">
2795                     <code class="classname">Sequence</code>
2796                   </td><td align="left">
2797                     <code class="classname">std::deque</code>
2798                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2799                     binary_heap
2800                   </td></tr><tr><td align="left">
2801                     <code class="classname">priority_queue</code>
2802                   </td><td align="left">
2803                     <code class="classname">Tag</code>
2804                   </td><td align="left">
2805                     <code class="classname">binary_heap_tag</code>
2806                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2807                     binomial_heap
2808                   </td></tr><tr><td align="left">
2809                     <code class="classname">priority_queue</code>
2810                   </td><td align="left">
2811                     <code class="classname">Tag</code>
2812                   </td><td align="left">
2813                     <code class="classname">binomial_heap_tag</code>
2814                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2815                     rc_binomial_heap
2816                   </td></tr><tr><td align="left">
2817                     <code class="classname">priority_queue</code>
2818                   </td><td align="left">
2819                     <code class="classname">Tag</code>
2820                   </td><td align="left">
2821                     <code class="classname">rc_binomial_heap_tag</code>
2822                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2823                     thin_heap
2824                   </td></tr><tr><td align="left">
2825                     <code class="classname">priority_queue</code>
2826                   </td><td align="left">
2827                     <code class="classname">Tag</code>
2828                   </td><td align="left">
2829                     <code class="classname">thin_heap_tag</code>
2830                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2831                     pairing_heap
2832                   </td></tr><tr><td align="left">
2833                     <code class="classname">priority_queue</code>
2834                   </td><td align="left">
2835                     <code class="classname">Tag</code>
2836                   </td><td align="left">
2837                     <code class="classname">pairing_heap_tag</code>
2838                   </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap
2839           based native priority queues and this library's
2840           priority_queue data structures.
2841           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_binary_priority_queue_int_push.png" align="middle" /></div></div><p>
2842             The abbreviated names in the legend of the graphic above are
2843             instantiated with the types in the following table.
2844           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2845                     n_pq_vector
2846                   </td></tr><tr><td align="left">
2847                     <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code>
2848                   </td><td align="left">
2849                     <code class="classname">Sequence</code>
2850                   </td><td align="left">
2851                     <code class="classname">std::vector</code>
2852                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2853                     n_pq_deque
2854                   </td></tr><tr><td align="left">
2855                     <code class="classname">std::priority_queue</code>
2856                   </td><td align="left">
2857                     <code class="classname">Sequence</code>
2858                   </td><td align="left">
2859                     <code class="classname">std::deque</code>
2860                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2861                     binary_heap
2862                   </td></tr><tr><td align="left">
2863                     <code class="classname">priority_queue</code>
2864                   </td><td align="left">
2865                     <code class="classname">Tag</code>
2866                   </td><td align="left">
2867                     <code class="classname">binary_heap_tag</code>
2868                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.observations"></a>
2869             Observations
2870           </h6></div></div></div><p>Binary heaps are the most suited for sequences of
2871           <code class="function">push</code> and <code class="function">pop</code> operations of primitive types
2872           (e.g. <span class="type">int</span>s). They are less constrained
2873           than any other type, and since it is very efficient to store
2874           such types in arrays, they outperform even pairing heaps. (See
2875           Priority
2876           Queue Text <code class="function">push</code> Timing Test for the case of
2877           non-primitive types.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push_pop"></a>
2878           Integer <code class="function">push</code>
2879         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.info"></a>
2880             Description
2881           </h6></div></div></div><p>This test inserts a number of values with integer keys
2882           into a container using <code class="function">push</code> , then removes them
2883           using <code class="function">pop</code> . It measures the average time for
2884           <code class="function">push</code> and <code class="function">pop</code> as a function
2885           of the number of values.</p><p>
2886             It uses the test file:
2887             <code class="filename">performance/ext/pb_ds/priority_queue_random_int_push_pop_timing.cc</code>
2888           </p><p>The test checks the effect of different underlying data
2889           structures.
2890           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.results"></a>
2891             Results
2892           </h6></div></div></div><p>The graphic immediately below shows the results for the
2893           native priority_queue type instantiated with different underlying
2894           container types versus several different versions of library's
2895           priority_queues.
2896           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_int_push_pop.png" align="middle" /></div></div><p>
2897             The abbreviated names in the legend of the graphic above are
2898             instantiated with the types in the following table.
2899           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2900                     n_pq_vector
2901                   </td></tr><tr><td align="left">
2902                     <code class="classname">std::priority_queue</code>
2903                   </td><td align="left">
2904                     <code class="classname">Sequence</code>
2905                   </td><td align="left">
2906                     <code class="classname">std::vector</code>
2907                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2908                     n_pq_deque
2909                   </td></tr><tr><td align="left">
2910                     <code class="classname">std::priority_queue</code>
2911                   </td><td align="left">
2912                     <code class="classname">Sequence</code>
2913                   </td><td align="left">
2914                     <code class="classname">std::deque</code>
2915                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2916                     binary_heap
2917                   </td></tr><tr><td align="left">
2918                     <code class="classname">priority_queue</code>
2919                   </td><td align="left">
2920                     <code class="classname">Tag</code>
2921                   </td><td align="left">
2922                     <code class="classname">binary_heap_tag</code>
2923                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2924                     binomial_heap
2925                   </td></tr><tr><td align="left">
2926                     <code class="classname">priority_queue</code>
2927                   </td><td align="left">
2928                     <code class="classname">Tag</code>
2929                   </td><td align="left">
2930                     <code class="classname">binomial_heap_tag</code>
2931                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2932                     rc_binomial_heap
2933                   </td></tr><tr><td align="left">
2934                     <code class="classname">priority_queue</code>
2935                   </td><td align="left">
2936                     <code class="classname">Tag</code>
2937                   </td><td align="left">
2938                     <code class="classname">rc_binomial_heap_tag</code>
2939                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2940                     thin_heap
2941                   </td></tr><tr><td align="left">
2942                     <code class="classname">priority_queue</code>
2943                   </td><td align="left">
2944                     <code class="classname">Tag</code>
2945                   </td><td align="left">
2946                     <code class="classname">thin_heap_tag</code>
2947                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
2948                     pairing_heap
2949                   </td></tr><tr><td align="left">
2950                     <code class="classname">priority_queue</code>
2951                   </td><td align="left">
2952                     <code class="classname">Tag</code>
2953                   </td><td align="left">
2954                     <code class="classname">pairing_heap_tag</code>
2955                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.observations"></a>
2956             Observations
2957           </h6></div></div></div><p>Binary heaps are the most suited for sequences of
2958           <code class="function">push</code> and <code class="function">pop</code> operations of primitive types
2959           (e.g. <span class="type">int</span>s). This is explained in
2960           Priority
2961           Queue Random Int <code class="function">push</code> Timing Test. (See Priority Queue
2962           Text <code class="function">push</code> Timing Test for the case of primitive
2963           types.)</p><p>At first glance it seems that the standard's vector-based
2964           priority queue is approximately on par with this
2965           library's corresponding priority queue. There are two
2966           differences however:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>The standard's priority queue does not downsize the underlying
2967             vector (or deque) as the priority queue becomes smaller
2968             (see Priority Queue
2969             Text <code class="function">pop</code> Memory Use Test). It is therefore
2970             gaining some speed at the expense of space.</p></li><li class="listitem"><p>From Priority Queue Random
2971             Integer <code class="function">push</code> and <code class="function">pop</code>
2972             Timing Test, it seems that the standard's priority queue is
2973             slower in terms of <code class="function">push</code> operations. Since
2974             the number of
2975             <code class="function">pop</code> operations is at most that of <code class="function">push</code>
2976             operations, the test here is the "best" for the standard's
2977             priority queue.</p></li></ol></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_pop"></a>
2978           Text <code class="function">pop</code> Memory Use
2979         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.info"></a>
2980             Description
2981           </h6></div></div></div><p>This test inserts a number of values with keys from an
2982           arbitrary text ([ wickland96thirty ]) into
2983           a container, then pops them until only one is left in the
2984           container. It measures the memory use as a function of the
2985           number of values pushed to the container.</p><p>
2986             It uses the test file:
2987             <code class="filename">performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc</code>
2988           </p><p>The test checks the effect of different underlying data
2989           structures.
2990           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.results"></a>
2991             Results
2992           </h6></div></div></div><p>The graphic immediately below shows the results for the
2993           native priority_queue type instantiated with different underlying
2994           container types versus several different versions of library's
2995           priority_queues.
2996           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_pop_mem.png" align="middle" /></div></div><p>
2997             The abbreviated names in the legend of the graphic above are
2998             instantiated with the types in the following table.
2999           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3000                     n_pq_vector
3001                   </td></tr><tr><td align="left">
3002                     <code class="classname">std::priority_queue</code>
3003                   </td><td align="left">
3004                     <code class="classname">Sequence</code>
3005                   </td><td align="left">
3006                     <code class="classname">std::vector</code>
3007                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3008                     n_pq_deque
3009                   </td></tr><tr><td align="left">
3010                     <code class="classname">std::priority_queue</code>
3011                   </td><td align="left">
3012                     <code class="classname">Sequence</code>
3013                   </td><td align="left">
3014                     <code class="classname">std::deque</code>
3015                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3016                     binary_heap
3017                   </td></tr><tr><td align="left">
3018                     <code class="classname">priority_queue</code>
3019                   </td><td align="left">
3020                     <code class="classname">Tag</code>
3021                   </td><td align="left">
3022                     <code class="classname">binary_heap_tag</code>
3023                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3024                     binomial_heap
3025                   </td></tr><tr><td align="left">
3026                     <code class="classname">priority_queue</code>
3027                   </td><td align="left">
3028                     <code class="classname">Tag</code>
3029                   </td><td align="left">
3030                     <code class="classname">binomial_heap_tag</code>
3031                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3032                     rc_binomial_heap
3033                   </td></tr><tr><td align="left">
3034                     <code class="classname">priority_queue</code>
3035                   </td><td align="left">
3036                     <code class="classname">Tag</code>
3037                   </td><td align="left">
3038                     <code class="classname">rc_binomial_heap_tag</code>
3039                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3040                     thin_heap
3041                   </td></tr><tr><td align="left">
3042                     <code class="classname">priority_queue</code>
3043                   </td><td align="left">
3044                     <code class="classname">Tag</code>
3045                   </td><td align="left">
3046                     <code class="classname">thin_heap_tag</code>
3047                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3048                     pairing_heap
3049                   </td></tr><tr><td align="left">
3050                     <code class="classname">priority_queue</code>
3051                   </td><td align="left">
3052                     <code class="classname">Tag</code>
3053                   </td><td align="left">
3054                     <code class="classname">pairing_heap_tag</code>
3055                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.observations"></a>
3056             Observations
3057           </h6></div></div></div><p>The priority queue implementations (excluding the standard's) use
3058           memory proportionally to the number of values they hold:
3059           node-based implementations (e.g., a pairing heap) do so
3060           naturally; this library's binary heap de-allocates memory when
3061           a certain lower threshold is exceeded.</p><p>Note from Priority Queue Text <code class="function">push</code>
3062           and <code class="function">pop</code> Timing Test and Priority Queue
3063           Random Integer <code class="function">push</code>
3064           and <code class="function">pop</code> Timing Test that this does not
3065           impede performance compared to the standard's priority
3066           queues.</p><p>See Hash-Based Erase
3067           Memory Use Test for a similar phenomenon regarding priority
3068           queues.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_join"></a>
3069           Text <code class="function">join</code>
3070         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.info"></a>
3071             Description
3072           </h6></div></div></div><p>This test inserts a number of values with keys from an
3073           arbitrary text ([ wickland96thirty ]) into
3074           two containers, then merges the containers. It uses
3075           <code class="function">join</code> for this library's priority queues; for
3076           the standard's priority queues, it successively pops values from
3077           one container and pushes them into the other. The test measures
3078           the average time as a function of the number of values.</p><p>
3079             It uses the test file:
3080             <code class="filename">performance/ext/pb_ds/priority_queue_text_join_timing.cc</code>
3081           </p><p>The test checks the effect of different underlying data
3082           structures.
3083           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.results"></a>
3084             Results
3085           </h6></div></div></div><p>The graphic immediately below shows the results for the
3086           native priority_queue type instantiated with different underlying
3087           container types versus several different versions of library's
3088           priority_queues.
3089           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_join.png" align="middle" /></div></div><p>
3090             The abbreviated names in the legend of the graphic above are
3091             instantiated with the types in the following table.
3092           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3093                     n_pq_vector
3094                   </td></tr><tr><td align="left">
3095                     <code class="classname">std::priority_queue</code>
3096                   </td><td align="left">
3097                     <code class="classname">Sequence</code>
3098                   </td><td align="left">
3099                     <code class="classname">std::vector</code>
3100                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3101                     n_pq_deque
3102                   </td></tr><tr><td align="left">
3103                     <code class="classname">std::priority_queue</code>
3104                   </td><td align="left">
3105                     <code class="classname">Sequence</code>
3106                   </td><td align="left">
3107                     <code class="classname">std::deque</code>
3108                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3109                     binary_heap
3110                   </td></tr><tr><td align="left">
3111                     <code class="classname">priority_queue</code>
3112                   </td><td align="left">
3113                     <code class="classname">Tag</code>
3114                   </td><td align="left">
3115                     <code class="classname">binary_heap_tag</code>
3116                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3117                     binomial_heap
3118                   </td></tr><tr><td align="left">
3119                     <code class="classname">priority_queue</code>
3120                   </td><td align="left">
3121                     <code class="classname">Tag</code>
3122                   </td><td align="left">
3123                     <code class="classname">binomial_heap_tag</code>
3124                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3125                     rc_binomial_heap
3126                   </td></tr><tr><td align="left">
3127                     <code class="classname">priority_queue</code>
3128                   </td><td align="left">
3129                     <code class="classname">Tag</code>
3130                   </td><td align="left">
3131                     <code class="classname">rc_binomial_heap_tag</code>
3132                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3133                     thin_heap
3134                   </td></tr><tr><td align="left">
3135                     <code class="classname">priority_queue</code>
3136                   </td><td align="left">
3137                     <code class="classname">Tag</code>
3138                   </td><td align="left">
3139                     <code class="classname">thin_heap_tag</code>
3140                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3141                     pairing_heap
3142                   </td></tr><tr><td align="left">
3143                     <code class="classname">priority_queue</code>
3144                   </td><td align="left">
3145                     <code class="classname">Tag</code>
3146                   </td><td align="left">
3147                     <code class="classname">pairing_heap_tag</code>
3148                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.observations"></a>
3149             Observations
3150           </h6></div></div></div><p>In this test the node-based heaps perform <code class="function">join</code> in
3151           either logarithmic or constant time. The binary heap requires
3152           linear time, since the well-known heapify algorithm [clrs2001] is linear.</p><p>It would be possible to apply the heapify algorithm to the
3153           standard containers, if they would support iteration (which they
3154           don't). Barring iterators, it is still somehow possible to perform
3155           linear-time merge on a <code class="classname">std::vector</code>-based
3156           standard priority queue, using <code class="function">top()</code>
3157           and <code class="function">size()</code> (since they are enough to expose
3158           the underlying array), but this is impossible for
3159           a <code class="classname">std::deque</code>-based standard priority queue.
3160           Without heapify, the cost is super-linear.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_up"></a>
3161           Text <code class="function">modify</code> Up
3162         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.info"></a>
3163             Description
3164           </h6></div></div></div><p>This test inserts a number of values with keys from an
3165           arbitrary text ([ wickland96thirty ]) into
3166           into a container then modifies each one "up" (i.e., it
3167           makes it larger). It uses <code class="function">modify</code> for this library's
3168           priority queues; for the standard's priority queues, it pops values
3169           from a container until it reaches the value that should be
3170           modified, then pushes values back in. It measures the average
3171           time for <code class="function">modify</code> as a function of the number of
3172           values.</p><p>
3173             It uses the test file:
3174             <code class="filename">performance/ext/pb_ds/priority_queue_text_modify_up_timing.cc</code>
3175           </p><p>The test checks the effect of different underlying data
3176           structures for graph algorithms settings.  Note that making an
3177           arbitrary value larger (in the sense of the priority queue's
3178           comparison functor) corresponds to decrease-key in standard graph
3179           algorithms [clrs2001].
3180           </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.results"></a>
3181             Results
3182           </h6></div></div></div><p>The two graphics below show the results for the native
3183           priority_queues and this library's priority_queues.
3184           </p><p>The graphic immediately below shows the results for the
3185           native priority_queue type instantiated with different underlying
3186           container types versus several different versions of library's
3187           priority_queues.
3188           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_modify_up.png" align="middle" /></div></div><p>
3189             The abbreviated names in the legend of the graphic above are
3190             instantiated with the types in the following table.
3191           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3192                     n_pq_vector
3193                   </td></tr><tr><td align="left">
3194                     <code class="classname">std::priority_queue</code>
3195                   </td><td align="left">
3196                     <code class="classname">Sequence</code>
3197                   </td><td align="left">
3198                     <code class="classname">std::vector</code>
3199                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3200                     n_pq_deque
3201                   </td></tr><tr><td align="left">
3202                     <code class="classname">std::priority_queue</code>
3203                   </td><td align="left">
3204                     <code class="classname">Sequence</code>
3205                   </td><td align="left">
3206                     <code class="classname">std::deque</code>
3207                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3208                     binary_heap
3209                   </td></tr><tr><td align="left">
3210                     <code class="classname">priority_queue</code>
3211                   </td><td align="left">
3212                     <code class="classname">Tag</code>
3213                   </td><td align="left">
3214                     <code class="classname">binary_heap_tag</code>
3215                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3216                     binomial_heap
3217                   </td></tr><tr><td align="left">
3218                     <code class="classname">priority_queue</code>
3219                   </td><td align="left">
3220                     <code class="classname">Tag</code>
3221                   </td><td align="left">
3222                     <code class="classname">binomial_heap_tag</code>
3223                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3224                     rc_binomial_heap
3225                   </td></tr><tr><td align="left">
3226                     <code class="classname">priority_queue</code>
3227                   </td><td align="left">
3228                     <code class="classname">Tag</code>
3229                   </td><td align="left">
3230                     <code class="classname">rc_binomial_heap_tag</code>
3231                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3232                     thin_heap
3233                   </td></tr><tr><td align="left">
3234                     <code class="classname">priority_queue</code>
3235                   </td><td align="left">
3236                     <code class="classname">Tag</code>
3237                   </td><td align="left">
3238                     <code class="classname">thin_heap_tag</code>
3239                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3240                     pairing_heap
3241                   </td></tr><tr><td align="left">
3242                     <code class="classname">priority_queue</code>
3243                   </td><td align="left">
3244                     <code class="classname">Tag</code>
3245                   </td><td align="left">
3246                     <code class="classname">pairing_heap_tag</code>
3247                   </td></tr></tbody></table></div><p>The graphic below shows the results for the
3248           native priority queues and this library's pairing and thin heap
3249           priority_queue data structures.
3250           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_modify_up_thin.png" align="middle" /></div></div><p>
3251             The abbreviated names in the legend of the graphic above are
3252             instantiated with the types in the following table.
3253           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3254                     thin_heap
3255                   </td></tr><tr><td align="left">
3256                     <code class="classname">priority_queue</code>
3257                   </td><td align="left">
3258                     <code class="classname">Tag</code>
3259                   </td><td align="left">
3260                     <code class="classname">thin_heap_tag</code>
3261                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3262                     pairing_heap
3263                   </td></tr><tr><td align="left">
3264                     <code class="classname">priority_queue</code>
3265                   </td><td align="left">
3266                     <code class="classname">Tag</code>
3267                   </td><td align="left">
3268                     <code class="classname">pairing_heap_tag</code>
3269                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.observations"></a>
3270             Observations
3271           </h6></div></div></div><p>As noted above, increasing an arbitrary value (in the sense of
3272           the priority queue's comparison functor) is very common in
3273           graph-related algorithms. In this case, a thin heap
3274           (<code class="classname">priority_queue</code> with
3275           <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>)
3276           outperforms a pairing heap (<code class="classname">priority_queue</code> with
3277           <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>).
3278           Conversely, Priority Queue Text
3279           <code class="function">push</code> Timing Test, Priority Queue
3280           Text <code class="function">push</code> and <code class="function">pop</code> Timing Test, Priority
3281           Queue Random Integer <code class="function">push</code> Timing Test, and
3282           Priority
3283           Queue Random Integer <code class="function">push</code> and <code class="function">pop</code> Timing
3284           Test show that the situation is reversed for other
3285           operations. It is not clear when to prefer one of these two
3286           different types.</p><p>In this test this library's binary heaps
3287           effectively perform modify in linear time. As explained in
3288           Priority Queue Design::Traits, given a valid point-type iterator,
3289           a binary heap can perform
3290           <code class="function">modify</code> logarithmically. The problem is that binary
3291           heaps invalidate their find iterators with each modifying
3292           operation, and so the only way to obtain a valid point-type
3293           iterator is to iterate using a range-type iterator until
3294           finding the appropriate value, then use the range-type iterator
3295           for the <code class="function">modify</code> operation.</p><p>The explanation for the standard's priority queues' performance
3296           is similar to that in Priority Queue Text
3297           <code class="function">join</code> Timing Test.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_down"></a>
3298           Text <code class="function">modify</code> Down
3299         </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.info"></a>
3300             Description
3301           </h6></div></div></div><p>This test inserts a number of values with keys from an
3302           arbitrary text ([ wickland96thirty ]) into
3303           into a container then modifies each one "down" (i.e., it
3304           makes it smaller). It uses <code class="function">modify</code> for this library's
3305           priority queues; for the standard's priority queues, it pops values
3306           from a container until it reaches the value that should be
3307           modified, then pushes values back in. It measures the average
3308           time for <code class="function">modify</code> as a function of the number of
3309           values.</p><p>
3310             It uses the test file:
3311             <code class="filename">performance/ext/pb_ds/priority_queue_text_modify_down_timing.cc</code>
3312           </p><p>The main purpose of this test is to contrast Priority Queue
3313           Text <code class="classname">modify</code> Up Timing Test.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.results"></a>
3314             Results
3315           </h6></div></div></div><p>The two graphics below show the results for the native
3316           priority_queues and this library's priority_queues.
3317           </p><p>The graphic immediately below shows the results for the
3318           native priority_queue type instantiated with different underlying
3319           container types versus several different versions of library's
3320           priority_queues.
3321           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_modify_down.png" align="middle" /></div></div><p>
3322             The abbreviated names in the legend of the graphic above are
3323             instantiated with the types in the following table.
3324           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3325                     n_pq_vector
3326                   </td></tr><tr><td align="left">
3327                     <code class="classname">std::priority_queue</code>
3328                   </td><td align="left">
3329                     <code class="classname">Sequence</code>
3330                   </td><td align="left">
3331                     <code class="classname">std::vector</code>
3332                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3333                     n_pq_deque
3334                   </td></tr><tr><td align="left">
3335                     <code class="classname">std::priority_queue</code>
3336                   </td><td align="left">
3337                     <code class="classname">Sequence</code>
3338                   </td><td align="left">
3339                     <code class="classname">std::deque</code>
3340                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3341                     binary_heap
3342                   </td></tr><tr><td align="left">
3343                     <code class="classname">priority_queue</code>
3344                   </td><td align="left">
3345                     <code class="classname">Tag</code>
3346                   </td><td align="left">
3347                     <code class="classname">binary_heap_tag</code>
3348                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3349                     binomial_heap
3350                   </td></tr><tr><td align="left">
3351                     <code class="classname">priority_queue</code>
3352                   </td><td align="left">
3353                     <code class="classname">Tag</code>
3354                   </td><td align="left">
3355                     <code class="classname">binomial_heap_tag</code>
3356                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3357                     rc_binomial_heap
3358                   </td></tr><tr><td align="left">
3359                     <code class="classname">priority_queue</code>
3360                   </td><td align="left">
3361                     <code class="classname">Tag</code>
3362                   </td><td align="left">
3363                     <code class="classname">rc_binomial_heap_tag</code>
3364                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3365                     thin_heap
3366                   </td></tr><tr><td align="left">
3367                     <code class="classname">priority_queue</code>
3368                   </td><td align="left">
3369                     <code class="classname">Tag</code>
3370                   </td><td align="left">
3371                     <code class="classname">thin_heap_tag</code>
3372                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3373                     pairing_heap
3374                   </td></tr><tr><td align="left">
3375                     <code class="classname">priority_queue</code>
3376                   </td><td align="left">
3377                     <code class="classname">Tag</code>
3378                   </td><td align="left">
3379                     <code class="classname">pairing_heap_tag</code>
3380                   </td></tr></tbody></table></div><p>The graphic below shows the results for the
3381           native priority queues and this library's pairing and thin heap
3382           priority_queue data structures.
3383           </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_modify_down_thin.png" align="middle" /></div></div><p>
3384             The abbreviated names in the legend of the graphic above are
3385             instantiated with the types in the following table.
3386           </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3387                     thin_heap
3388                   </td></tr><tr><td align="left">
3389                     <code class="classname">priority_queue</code>
3390                   </td><td align="left">
3391                     <code class="classname">Tag</code>
3392                   </td><td align="left">
3393                     <code class="classname">thin_heap_tag</code>
3394                   </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left">
3395                     pairing_heap
3396                   </td></tr><tr><td align="left">
3397                     <code class="classname">priority_queue</code>
3398                   </td><td align="left">
3399                     <code class="classname">Tag</code>
3400                   </td><td align="left">
3401                     <code class="classname">pairing_heap_tag</code>
3402                   </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.observations"></a>
3403             Observations
3404           </h6></div></div></div><p>Most points in these results are similar to Priority Queue
3405           Text <code class="function">modify</code> Up Timing Test.</p><p>It is interesting to note, however, that as opposed to that
3406           test, a thin heap (<code class="classname">priority_queue</code> with
3407           <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>) is
3408           outperformed by a pairing heap (<code class="classname">priority_queue</code> with
3409           <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>).
3410           In this case, both heaps essentially perform an <code class="function">erase</code>
3411           operation followed by a <code class="function">push</code> operation. As the other
3412           tests show, a pairing heap is usually far more efficient than a
3413           thin heap, so this is not surprising.</p><p>Most algorithms that involve priority queues increase values
3414           (in the sense of the priority queue's comparison functor), and
3415           so Priority Queue
3416           Text <code class="classname">modify</code> Up Timing Test - is more interesting
3417           than this test.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.test.performance.observations"></a>Observations</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="observations.associative"></a>Associative</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.underlying"></a>
3418             Underlying Data-Structure Families
3419           </h6></div></div></div><p>In general, hash-based containers have better timing performance
3420           than containers based on different underlying-data structures. The
3421           main reason to choose a tree-based or trie-based container is if a
3422           byproduct of the tree-like structure is required: either
3423           order-preservation, or the ability to utilize node invariants. If
3424           memory-use is the major factor, an ordered-vector tree gives
3425           optimal results (albeit with high modificiation costs), and a
3426           list-based container gives reasonable results.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash"></a>
3427             Hash-Based Containers
3428           </h6></div></div></div><p>Hash-based containers are typically either collision
3429           chaining or probing. Collision-chaining
3430           containers are more flexible internally, and so offer better
3431           timing performance. Probing containers, if used for simple
3432           value-types, manage memory more efficiently (they perform far
3433           fewer allocation-related calls). In general, therefore, a
3434           collision-chaining table should be used. A probing container,
3435           conversely, might be used efficiently for operations such as
3436           eliminating duplicates in a sequence, or counting the number of
3437           occurrences within a sequence. Probing containers might be more
3438           useful also in multithreaded applications where each thread
3439           manipulates a hash-based container: in the standard, allocators have
3440           class-wise semantics (see [meyers96more] - Item 10); a
3441           probing container might incur less contention in this case.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash_policies"></a>
3442             Hash Policies
3443           </h6></div></div></div><p>In hash-based containers, the range-hashing scheme seems to
3444           affect performance more than other considerations. In most
3445           settings, a mask-based scheme works well (or can be made to
3446           work well). If the key-distribution can be estimated a-priori,
3447           a simple hash function can produce nearly uniform hash-value
3448           distribution. In many other cases (e.g., text hashing,
3449           floating-point hashing), the hash function is powerful enough
3450           to generate hash values with good uniformity properties
3451           [knuth98sorting];
3452           a modulo-based scheme, taking into account all bits of the hash
3453           value, appears to overlap the hash function in its effort.</p><p>The range-hashing scheme determines many of the other
3454           policies. A mask-based scheme works
3455           well with an exponential-size policy; for
3456           probing-based containers, it goes well with a linear-probe
3457           function.</p><p>An orthogonal consideration is the trigger policy. This
3458           presents difficult tradeoffs. E.g., different load
3459           factors in a load-check trigger policy yield a
3460           space/amortized-cost tradeoff.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.branch"></a>
3461             Branch-Based Containers
3462           </h6></div></div></div><p>In general, there are several families of tree-based
3463           underlying data structures: balanced node-based trees
3464           (e.g., red-black or AVL trees), high-probability
3465           balanced node-based trees (e.g., random treaps or
3466           skip-lists), competitive node-based trees (e.g., splay
3467           trees), vector-based "trees", and tries. (Additionally, there
3468           are disk-residing or network-residing trees, such as B-Trees
3469           and their numerous variants. An interface for this would have
3470           to deal with the execution model and ACID guarantees; this is
3471           out of the scope of this library.) Following are some
3472           observations on their application to different settings.</p><p>Of the balanced node-based trees, this library includes a
3473           red-black tree, as does standard (in
3474           practice). This type of tree is the "workhorse" of tree-based
3475           containers: it offers both reasonable modification and
3476           reasonable lookup time. Unfortunately, this data structure
3477           stores a huge amount of metadata. Each node must contain,
3478           besides a value, three pointers and a boolean. This type might
3479           be avoided if space is at a premium [austern00noset].</p><p>High-probability balanced node-based trees suffer the
3480           drawbacks of deterministic balanced trees. Although they are
3481           fascinating data structures, preliminary tests with them showed
3482           their performance was worse than red-black trees. The library
3483           does not contain any such trees, therefore.</p><p>Competitive node-based trees have two drawbacks. They are
3484           usually somewhat unbalanced, and they perform a large number of
3485           comparisons. Balanced trees perform one comparison per each
3486           node they encounter on a search path; a splay tree performs two
3487           comparisons. If the keys are complex objects, e.g.,
3488           <code class="classname">std::string</code>, this can increase the running time.
3489           Conversely, such trees do well when there is much locality of
3490           reference. It is difficult to determine in which case to prefer
3491           such trees over balanced trees. This library includes a splay
3492           tree.</p><p>Ordered-vector trees use very little space
3493           [austern00noset].
3494           They do not have any other advantages (at least in this
3495           implementation).</p><p>Large-fan-out PATRICIA tries have excellent lookup
3496           performance, but they do so through maintaining, for each node,
3497           a miniature "hash-table". Their space efficiency is low, and
3498           their modification performance is bad. These tries might be
3499           used for semi-static settings, where order preservation is
3500           important. Alternatively, red-black trees cross-referenced with
3501           hash tables can be used. [okasaki98mereable]
3502           discusses small-fan-out PATRICIA tries for integers, but the
3503           cited results seem to indicate that the amortized cost of
3504           maintaining such trees is higher than that of balanced trees.
3505           Moderate-fan-out trees might be useful for sequences where each
3506           element has a limited number of choices, e.g., DNA
3507           strings.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.mapping_semantics"></a>
3508             Mapping-Semantics
3509           </h6></div></div></div><p>Different mapping semantics were discussed in the introduction and design sections.Here
3510           the focus will be on the case where a keys can be composed into
3511           primary keys and secondary keys. (In the case where some keys
3512           are completely identical, it is trivial that one should use an
3513           associative container mapping values to size types.) In this
3514           case there are (at least) five possibilities:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Use an associative container that allows equivalent-key
3515             values (such as <code class="classname">std::multimap</code>)</p></li><li class="listitem"><p>Use a unique-key value associative container that maps
3516             each primary key to some complex associative container of
3517             secondary keys, say a tree-based or hash-based container.
3518             </p></li><li class="listitem"><p>Use a unique-key value associative container that maps
3519             each primary key to some simple associative container of
3520             secondary keys, say a list-based container.</p></li><li class="listitem"><p>Use a unique-key value associative container that maps
3521             each primary key to some non-associative container
3522             (e.g., <code class="classname">std::vector</code>)</p></li><li class="listitem"><p>Use a unique-key value associative container that takes
3523             into account both primary and secondary keys.</p></li></ol></div><p>Stated simply: there is a simple answer for this. (Excluding
3524           option 1, which should be avoided in all cases).</p><p>If the expected ratio of secondary keys to primary keys is
3525           small, then 3 and 4 seem reasonable. Both types of secondary
3526           containers are relatively lightweight (in terms of memory use
3527           and construction time), and so creating an entire container
3528           object for each primary key is not too expensive. Option 4
3529           might be preferable to option 3 if changing the secondary key
3530           of some primary key is frequent - one cannot modify an
3531           associative container's key, and the only possibility,
3532           therefore, is erasing the secondary key and inserting another
3533           one instead; a non-associative container, conversely, can
3534           support in-place modification. The actual cost of erasing a
3535           secondary key and inserting another one depends also on the
3536           allocator used for secondary associative-containers (The tests
3537           above used the standard allocator, but in practice one might
3538           choose to use, e.g., [boost_pool]). Option 2 is
3539           definitely an overkill in this case. Option 1 loses out either
3540           immediately (when there is one secondary key per primary key)
3541           or almost immediately after that. Option 5 has the same
3542           drawbacks as option 2, but it has the additional drawback that
3543           finding all values whose primary key is equivalent to some key,
3544           might be linear in the total number of values stored (for
3545           example, if using a hash-based container).</p><p>If the expected ratio of secondary keys to primary keys is
3546           large, then the answer is more complicated. It depends on the
3547           distribution of secondary keys to primary keys, the
3548           distribution of accesses according to primary keys, and the
3549           types of operations most frequent.</p><p>To be more precise, assume there are m primary keys,
3550           primary key i is mapped to n<sub>i</sub>
3551           secondary keys, and each primary key is mapped, on average, to
3552           n secondary keys (i.e.,
3553           E(n<sub>i</sub>) = n).</p><p>Suppose one wants to find a specific pair of primary and
3554           secondary keys. Using 1 with a tree based container
3555           (<code class="classname">std::multimap</code>), the expected cost is
3556           E(Θ(log(m) + n<sub>i</sub>)) = Θ(log(m) +
3557           n); using 1 with a hash-based container
3558           (<code class="classname">std::tr1::unordered_multimap</code>), the expected cost is
3559           Θ(n). Using 2 with a primary hash-based container
3560           and secondary hash-based containers, the expected cost is
3561           O(1); using 2 with a primary tree-based container and
3562           secondary tree-based containers, the expected cost is (using
3563           the Jensen inequality [motwani95random])
3564           E(O(log(m) + log(n<sub>i</sub>)) = O(log(m)) +
3565           E(O(log(n<sub>i</sub>)) = O(log(m)) + O(log(n)),
3566           assuming that primary keys are accessed equiprobably. 3 and 4
3567           are similar to 1, but with lower constants. Using 5 with a
3568           hash-based container, the expected cost is O(1); using 5
3569           with a tree based container, the cost is
3570           E(Θ(log(mn))) = Θ(log(m) +
3571           log(n)).</p><p>Suppose one needs the values whose primary key matches some
3572           given key. Using 1 with a hash-based container, the expected
3573           cost is Θ(n), but the values will not be ordered
3574           by secondary keys (which may or may not be required); using 1
3575           with a tree-based container, the expected cost is
3576           Θ(log(m) + n), but with high constants; again the
3577           values will not be ordered by secondary keys. 2, 3, and 4 are
3578           similar to 1, but typically with lower constants (and,
3579           additionally, if one uses a tree-based container for secondary
3580           keys, they will be ordered). Using 5 with a hash-based
3581           container, the cost is Θ(mn).</p><p>Suppose one wants to assign to a primary key all secondary
3582           keys assigned to a different primary key. Using 1 with a
3583           hash-based container, the expected cost is Θ(n),
3584           but with very high constants; using 1 with a tree-based
3585           container, the cost is Θ(nlog(mn)). Using 2, 3,
3586           and 4, the expected cost is Θ(n), but typically
3587           with far lower costs than 1. 5 is similar to 1.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="observations.priority_queue"></a>Priority_Queue</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.complexity"></a>Complexity</h6></div></div></div><p>The following table shows the complexities of the different
3588           underlying data structures in terms of orders of growth. It is
3589           interesting to note that this table implies something about the
3590           constants of the operations as well (see Amortized <code class="function">push</code>
3591           and <code class="function">pop</code> operations).</p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /></colgroup><thead><tr><th align="left"> </th><th align="left"><span class="emphasis"><em><code class="function">push</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">pop</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">modify</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">erase</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">join</code></em></span></th></tr></thead><tbody><tr><td align="left">
3592                     <code class="classname">std::priority_queue</code>
3593                   </td><td align="left">
3594                     Θ(n) worst
3595                     Θ(log(n)) amortized
3596                   </td><td align="left">
3597                     Θ(log(n)) Worst
3598                   </td><td align="left">
3599                     Θ(n log(n)) Worst
3600                     <sub>[std note 1]</sub>
3601                   </td><td align="left">
3602                     Θ(n log(n))
3603                     <sub>[std note 2]</sub>
3604                   </td><td align="left">
3605                     Θ(n log(n))
3606                     <sub>[std note 1]</sub>
3607                   </td></tr><tr><td align="left">
3608                     <code class="classname">priority_queue</code>
3609                     &lt;<code class="classname">Tag</code> =
3610                     <code class="classname">pairing_heap_tag</code>&gt;
3611                   </td><td align="left">
3612                     O(1)
3613                   </td><td align="left">
3614                     Θ(n) worst
3615                     Θ(log(n)) amortized
3616                   </td><td align="left">
3617                     Θ(n) worst
3618                     Θ(log(n)) amortized
3619                   </td><td align="left">
3620                     Θ(n) worst
3621                     Θ(log(n)) amortized
3622                   </td><td align="left">
3623                     O(1)
3624                   </td></tr><tr><td align="left">
3625                     <code class="classname">priority_queue</code>
3626                     &lt;<code class="classname">Tag</code> =
3627                     <code class="classname">binary_heap_tag</code>&gt;
3628                   </td><td align="left">
3629                     Θ(n) worst
3630                     Θ(log(n)) amortized
3631                   </td><td align="left">
3632                     Θ(n) worst
3633                     Θ(log(n)) amortized
3634                   </td><td align="left">
3635                     Θ(n)
3636                   </td><td align="left">
3637                     Θ(n)
3638                   </td><td align="left">
3639                     Θ(n)
3640                   </td></tr><tr><td align="left">
3641                     <code class="classname">priority_queue</code>
3642                     &lt;<code class="classname">Tag</code> =
3643                     <code class="classname">binomial_heap_tag</code>&gt;
3644                   </td><td align="left">
3645                     Θ(log(n)) worst
3646                     O(1) amortized
3647                   </td><td align="left">
3648                     Θ(log(n))
3649                   </td><td align="left">
3650                     Θ(log(n))
3651                   </td><td align="left">
3652                     Θ(log(n))
3653                   </td><td align="left">
3654                     Θ(log(n))
3655                   </td></tr><tr><td align="left">
3656                     <code class="classname">priority_queue</code>
3657                     &lt;<code class="classname">Tag</code> =
3658                     <code class="classname">rc_binomial_heap_tag</code>&gt;
3659                   </td><td align="left">
3660                     O(1)
3661                   </td><td align="left">
3662                     Θ(log(n))
3663                   </td><td align="left">
3664                     Θ(log(n))
3665                   </td><td align="left">
3666                     Θ(log(n))
3667                   </td><td align="left">
3668                     Θ(log(n))
3669                   </td></tr><tr><td align="left">
3670                     <code class="classname">priority_queue</code>&lt;<code class="classname">Tag</code> =
3671                     <code class="classname">thin_heap_tag</code>&gt;
3672                   </td><td align="left">
3673                     O(1)
3674                   </td><td align="left">
3675                     Θ(n) worst
3676                     Θ(log(n)) amortized
3677                   </td><td align="left">
3678                     Θ(log(n)) worst
3679                     O(1) amortized,
3680                     or Θ(log(n)) amortized
3681                     <sub>[thin_heap_note]</sub>
3682                   </td><td align="left">
3683                     Θ(n) worst
3684                     Θ(log(n)) amortized
3685                   </td><td align="left">
3686                     Θ(n)
3687                   </td></tr></tbody></table></div><p>[std note 1] This
3688           is not a property of the algorithm, but rather due to the fact
3689           that the standard's priority queue implementation does not support
3690           iterators (and consequently the ability to access a specific
3691           value inside it). If the priority queue is adapting an
3692           <code class="classname">std::vector</code>, then it is still possible to reduce this
3693           to Θ(n) by adapting over the standard's adapter and
3694           using the fact that <code class="function">top</code> returns a reference to the
3695           first value; if, however, it is adapting an
3696           <code class="classname">std::deque</code>, then this is impossible.</p><p>[std note 2] As
3697           with [std note 1], this is not a
3698           property of the algorithm, but rather the standard's implementation.
3699           Again, if the priority queue is adapting an
3700           <code class="classname">std::vector</code> then it is possible to reduce this to
3701           Θ(n), but with a very high constant (one must call
3702           <code class="function">std::make_heap</code> which is an expensive linear
3703           operation); if the priority queue is adapting an
3704           <code class="classname">std::deque</code>, then this is impossible.</p><p>[thin_heap_note] A thin heap has
3705           Θ(log(n)) worst case <code class="function">modify</code> time
3706           always, but the amortized time depends on the nature of the
3707           operation: I) if the operation increases the key (in the sense
3708           of the priority queue's comparison functor), then the amortized
3709           time is O(1), but if II) it decreases it, then the
3710           amortized time is the same as the worst case time. Note that
3711           for most algorithms, I) is important and II) is not.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.amortized_ops"></a>
3712             Amortized <code class="function">push</code>
3713             and <code class="function">pop</code> operations
3714           </h6></div></div></div><p>In many cases, a priority queue is needed primarily for
3715           sequences of <code class="function">push</code> and <code class="function">pop</code> operations. All of
3716           the underlying data structures have the same amortized
3717           logarithmic complexity, but they differ in terms of
3718           constants.</p><p>The table above shows that the different data structures are
3719           "constrained" in some respects. In general, if a data structure
3720           has lower worst-case complexity than another, then it will
3721           perform slower in the amortized sense. Thus, for example a
3722           redundant-counter binomial heap (<code class="classname">priority_queue</code> with
3723           <code class="classname">Tag</code> = <code class="classname">rc_binomial_heap_tag</code>)
3724           has lower worst-case <code class="function">push</code> performance than a binomial
3725           heap (<code class="classname">priority_queue</code>
3726           with <code class="classname">Tag</code> = <code class="classname">binomial_heap_tag</code>),
3727           and so its amortized <code class="function">push</code> performance is slower in
3728           terms of constants.</p><p>As the table shows, the "least constrained" underlying
3729           data structures are binary heaps and pairing heaps.
3730           Consequently, it is not surprising that they perform best in
3731           terms of amortized constants.</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Pairing heaps seem to perform best for non-primitive
3732             types (e.g., <code class="classname">std::string</code>s), as shown by
3733             Priority
3734             Queue Text <code class="function">push</code> Timing Test and Priority
3735             Queue Text <code class="function">push</code> and <code class="function">pop</code> Timing
3736             Test</p></li><li class="listitem"><p>binary heaps seem to perform best for primitive types
3737             (e.g., <span class="type">int</span>s), as shown by Priority
3738             Queue Random Integer <code class="function">push</code> Timing Test and
3739             Priority
3740             Queue Random Integer <code class="function">push</code> and <code class="function">pop</code> Timing
3741             Test.</p></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.graphs"></a>
3742             Graph Algorithms
3743           </h6></div></div></div><p>In some graph algorithms, a decrease-key operation is
3744           required [clrs2001];
3745           this operation is identical to <code class="function">modify</code> if a value is
3746           increased (in the sense of the priority queue's comparison
3747           functor). The table above and Priority Queue
3748           Text <code class="function">modify</code> Up Timing Test show that a thin heap
3749           (<code class="classname">priority_queue</code> with
3750           <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>)
3751           outperforms a pairing heap (<code class="classname">priority_queue</code> with
3752           <code class="classname">Tag</code> = <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>),
3753           but the rest of the tests show otherwise.</p><p>This makes it difficult to decide which implementation to use in
3754           this case. Dijkstra's shortest-path algorithm, for example, requires
3755           Θ(n) <code class="function">push</code> and <code class="function">pop</code> operations
3756           (in the number of vertices), but O(n<sup>2</sup>)
3757           <code class="function">modify</code> operations, which can be in practice Θ(n)
3758           as well. It is difficult to find an a-priori characterization of
3759           graphs in which the actual number of <code class="function">modify</code>
3760           operations will dwarf the number of <code class="function">push</code> and
3761           <code class="function">pop</code> operations.</p></div></div></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="policy_data_structures_design.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="policy_data_structures.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="policy_data_structures_ack.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Design </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Acknowledgments</td></tr></table></div></body></html>