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