1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter 21. Policy-Based Data Structures</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><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="extensions.html" title="Part III. Extensions" /><link rel="prev" href="bitmap_allocator_impl.html" title="Implementation" /><link rel="next" href="policy_data_structures_using.html" title="Using" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 21. Policy-Based Data Structures</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bitmap_allocator_impl.html">Prev</a> </td><th width="60%" align="center">Part III. 3 Extensions 4 5</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr></table><hr /></div><div class="chapter"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.containers.pbds"></a>Chapter 21. Policy-Based Data Structures</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring"> 6 Configuring via Template Parameters 7 </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.traits"> 8 Querying Container Attributes 9 </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.point_range_iteration"> 10 Point and Range Iteration 11 </a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples">Examples</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.basic">Intermediate Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.query">Querying with <code class="classname">container_traits</code> </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container">By Container Method</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container.hash">Hash-Based</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container.branch">Branch-Based</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container.priority_queue">Priority Queues</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts">Concepts</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.null_type">Null Policy Classes</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.associative_semantics">Map and Set Semantics</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#concepts.associative_semantics.set_vs_map"> 12 Distinguishing Between Maps and Sets 13 </a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#concepts.associative_semantics.multi">Alternatives to <code class="classname">std::multiset</code> and <code class="classname">std::multimap</code></a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.iterator_semantics">Iterator Semantics</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#concepts.iterator_semantics.point_and_range">Point and Range Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#concepts.iterator_semantics.both">Distinguishing Point and Range Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.invalidation">Invalidation Guarantees</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.genericity">Genericity</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#concepts.genericity.tag">Tag</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#concepts.genericity.traits">Traits</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container">By Container</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.hash">hash</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.hash.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.hash.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.tree">tree</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.tree.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.tree.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.trie">Trie</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.trie.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.trie.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.list">List</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.list.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.list.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.priority_queue">Priority Queue</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.priority_queue.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.priority_queue.details">Details</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html">Testing</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#pbds.test.regression">Regression</a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#pbds.test.performance">Performance</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash">Hash-Based</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.text_find"> 14 Text <code class="function">find</code> 15 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_find"> 16 Integer <code class="function">find</code> 17 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_find"> 18 Integer Subscript <code class="function">find</code> 19 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_insert"> 20 Integer Subscript <code class="function">insert</code> 21 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.zlob_int_find"> 22 Integer <code class="function">find</code> with Skewed-Distribution 23 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.erase_mem"> 24 Erase Memory Use 25 </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch">Branch-Based</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_insert"> 26 Text <code class="function">insert</code> 27 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_find"> 28 Text <code class="function">find</code> 29 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_lor_find"> 30 Text <code class="function">find</code> with Locality-of-Reference 31 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.split_join"> 32 <code class="function">split</code> and <code class="function">join</code> 33 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.order_statistics"> 34 Order-Statistics 35 </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap">Multimap</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_find_small"> 36 Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios 37 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_find_large"> 38 Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios 39 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_small"> 40 Text <code class="function">insert</code> with Small 41 Secondary-to-Primary Key Ratios 42 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_large"> 43 Text <code class="function">insert</code> with Small 44 Secondary-to-Primary Key Ratios 45 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_small"> 46 Text <code class="function">insert</code> with Small 47 Secondary-to-Primary Key Ratios Memory Use 48 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_large"> 49 Text <code class="function">insert</code> with Small 50 Secondary-to-Primary Key Ratios Memory Use 51 </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue">Priority Queue</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_push"> 52 Text <code class="function">push</code> 53 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_push_pop"> 54 Text <code class="function">push</code> and <code class="function">pop</code> 55 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push"> 56 Integer <code class="function">push</code> 57 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push_pop"> 58 Integer <code class="function">push</code> 59 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_pop"> 60 Text <code class="function">pop</code> Memory Use 61 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_join"> 62 Text <code class="function">join</code> 63 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_up"> 64 Text <code class="function">modify</code> Up 65 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_down"> 66 Text <code class="function">modify</code> Down 67 </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#pbds.test.performance.observations">Observations</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#observations.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#observations.priority_queue">Priority_Queue</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_ack.html">Acknowledgments</a></span></dt><dt><span class="bibliography"><a href="policy_data_structures.html#pbds.biblio">Bibliography</a></span></dt></dl></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="pbds.intro"></a>Intro</h2></div></div></div><p> 68 This is a library of policy-based elementary data structures: 69 associative containers and priority queues. It is designed for 70 high-performance, flexibility, semantic safety, and conformance to 71 the corresponding containers in <code class="literal">std</code> and 72 <code class="literal">std::tr1</code> (except for some points where it differs 73 by design). 74 </p><p> 75 </p><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.intro.issues"></a>Performance Issues</h3></div></div></div><p> 76 </p><p> 77 An attempt is made to categorize the wide variety of possible 78 container designs in terms of performance-impacting factors. These 79 performance factors are translated into design policies and 80 incorporated into container design. 81 </p><p> 82 There is tension between unravelling factors into a coherent set of 83 policies. Every attempt is made to make a minimal set of 84 factors. However, in many cases multiple factors make for long 85 template names. Every attempt is made to alias and use typedefs in 86 the source files, but the generated names for external symbols can 87 be large for binary files or debuggers. 88 </p><p> 89 In many cases, the longer names allow capabilities and behaviours 90 controlled by macros to also be unamibiguously emitted as distinct 91 generated names. 92 </p><p> 93 Specific issues found while unraveling performance factors in the 94 design of associative containers and priority queues follow. 95 </p><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.associative"></a>Associative</h4></div></div></div><p> 96 Associative containers depend on their composite policies to a very 97 large extent. Implicitly hard-wiring policies can hamper their 98 performance and limit their functionality. An efficient hash-based 99 container, for example, requires policies for testing key 100 equivalence, hashing keys, translating hash values into positions 101 within the hash table, and determining when and how to resize the 102 table internally. A tree-based container can efficiently support 103 order statistics, i.e. the ability to query what is the order of 104 each key within the sequence of keys in the container, but only if 105 the container is supplied with a policy to internally update 106 meta-data. There are many other such examples. 107 </p><p> 108 Ideally, all associative containers would share the same 109 interface. Unfortunately, underlying data structures and mapping 110 semantics differentiate between different containers. For example, 111 suppose one writes a generic function manipulating an associative 112 container. 113 </p><pre class="programlisting"> 114 template<typename Cntnr> 115 void 116 some_op_sequence(Cntnr& r_cnt) 117 { 118 ... 119 } 120 </pre><p> 121 Given this, then what can one assume about the instantiating 122 container? The answer varies according to its underlying data 123 structure. If the underlying data structure of 124 <code class="literal">Cntnr</code> is based on a tree or trie, then the order 125 of elements is well defined; otherwise, it is not, in general. If 126 the underlying data structure of <code class="literal">Cntnr</code> is based 127 on a collision-chaining hash table, then modifying 128 r_<code class="literal">Cntnr</code> will not invalidate its iterators' order; 129 if the underlying data structure is a probing hash table, then this 130 is not the case. If the underlying data structure is based on a tree 131 or trie, then a reference to the container can efficiently be split; 132 otherwise, it cannot, in general. If the underlying data structure 133 is a red-black tree, then splitting a reference to the container is 134 exception-free; if it is an ordered-vector tree, exceptions can be 135 thrown. 136 </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.priority_queue"></a>Priority Que</h4></div></div></div><p> 137 Priority queues are useful when one needs to efficiently access a 138 minimum (or maximum) value as the set of values changes. 139 </p><p> 140 Most useful data structures for priority queues have a relatively 141 simple structure, as they are geared toward relatively simple 142 requirements. Unfortunately, these structures do not support access 143 to an arbitrary value, which turns out to be necessary in many 144 algorithms. Say, decreasing an arbitrary value in a graph 145 algorithm. Therefore, some extra mechanism is necessary and must be 146 invented for accessing arbitrary values. There are at least two 147 alternatives: embedding an associative container in a priority 148 queue, or allowing cross-referencing through iterators. The first 149 solution adds significant overhead; the second solution requires a 150 precise definition of iterator invalidation. Which is the next 151 point... 152 </p><p> 153 Priority queues, like hash-based containers, store values in an 154 order that is meaningless and undefined externally. For example, a 155 <code class="code">push</code> operation can internally reorganize the 156 values. Because of this characteristic, describing a priority 157 queues' iterator is difficult: on one hand, the values to which 158 iterators point can remain valid, but on the other, the logical 159 order of iterators can change unpredictably. 160 </p><p> 161 Roughly speaking, any element that is both inserted to a priority 162 queue (e.g. through <code class="code">push</code>) and removed 163 from it (e.g., through <code class="code">pop</code>), incurs a 164 logarithmic overhead (in the amortized sense). Different underlying 165 data structures place the actual cost differently: some are 166 optimized for amortized complexity, whereas others guarantee that 167 specific operations only have a constant cost. One underlying data 168 structure might be chosen if modifying a value is frequent 169 (Dijkstra's shortest-path algorithm), whereas a different one might 170 be chosen otherwise. Unfortunately, an array-based binary heap - an 171 underlying data structure that optimizes (in the amortized sense) 172 <code class="code">push</code> and <code class="code">pop</code> operations, differs from the 173 others in terms of its invalidation guarantees. Other design 174 decisions also impact the cost and placement of the overhead, at the 175 expense of more difference in the kinds of operations that the 176 underlying data structure can support. These differences pose a 177 challenge when creating a uniform interface for priority queues. 178 </p></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.intro.motivation"></a>Goals</h3></div></div></div><p> 179 Many fine associative-container libraries were already written, 180 most notably, the C++ standard's associative containers. Why 181 then write another library? This section shows some possible 182 advantages of this library, when considering the challenges in 183 the introduction. Many of these points stem from the fact that 184 the ISO C++ process introduced associative-containers in a 185 two-step process (first standardizing tree-based containers, 186 only then adding hash-based containers, which are fundamentally 187 different), did not standardize priority queues as containers, 188 and (in our opinion) overloads the iterator concept. 189 </p><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.motivation.associative"></a>Associative</h4></div></div></div><p> 190 </p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.policy"></a>Policy Choices</h5></div></div></div><p> 191 Associative containers require a relatively large number of 192 policies to function efficiently in various settings. In some 193 cases this is needed for making their common operations more 194 efficient, and in other cases this allows them to support a 195 larger set of operations 196 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 197 Hash-based containers, for example, support look-up and 198 insertion methods (<code class="function">find</code> and 199 <code class="function">insert</code>). In order to locate elements 200 quickly, they are supplied a hash functor, which instruct 201 how to transform a key object into some size type; a hash 202 functor might transform <code class="constant">"hello"</code> 203 into <code class="constant">1123002298</code>. A hash table, though, 204 requires transforming each key object into some size-type 205 type in some specific domain; a hash table with a 128-long 206 table might transform <code class="constant">"hello"</code> into 207 position <code class="constant">63</code>. The policy by which the 208 hash value is transformed into a position within the table 209 can dramatically affect performance. Hash-based containers 210 also do not resize naturally (as opposed to tree-based 211 containers, for example). The appropriate resize policy is 212 unfortunately intertwined with the policy that transforms 213 hash value into a position within the table. 214 </p></li><li class="listitem"><p> 215 Tree-based containers, for example, also support look-up and 216 insertion methods, and are primarily useful when maintaining 217 order between elements is important. In some cases, though, 218 one can utilize their balancing algorithms for completely 219 different purposes. 220 </p><p> 221 Figure A shows a tree whose each node contains two entries: 222 a floating-point key, and some size-type 223 <span class="emphasis"><em>metadata</em></span> (in bold beneath it) that is 224 the number of nodes in the sub-tree. (The root has key 0.99, 225 and has 5 nodes (including itself) in its sub-tree.) A 226 container based on this data structure can obviously answer 227 efficiently whether 0.3 is in the container object, but it 228 can also answer what is the order of 0.3 among all those in 229 the container object: see <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>. 230 231 </p><p> 232 As another example, Figure B shows a tree whose each node 233 contains two entries: a half-open geometric line interval, 234 and a number <span class="emphasis"><em>metadata</em></span> (in bold beneath 235 it) that is the largest endpoint of all intervals in its 236 sub-tree. (The root describes the interval <code class="constant">[20, 237 36)</code>, and the largest endpoint in its sub-tree is 238 99.) A container based on this data structure can obviously 239 answer efficiently whether <code class="constant">[3, 41)</code> is 240 in the container object, but it can also answer efficiently 241 whether the container object has intervals that intersect 242 <code class="constant">[3, 41)</code>. These types of queries are 243 very useful in geometric algorithms and lease-management 244 algorithms. 245 </p><p> 246 It is important to note, however, that as the trees are 247 modified, their internal structure changes. To maintain 248 these invariants, one must supply some policy that is aware 249 of these changes. Without this, it would be better to use a 250 linked list (in itself very efficient for these purposes). 251 </p></li></ol></div><div class="figure"><a id="id-1.3.5.8.2.5.3.3.4"></a><p class="title"><strong>Figure 21.1. Node Invariants</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_node_invariants.png" align="middle" alt="Node Invariants" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.underlying"></a>Underlying Data Structures</h5></div></div></div><p> 252 The standard C++ library contains associative containers based on 253 red-black trees and collision-chaining hash tables. These are 254 very useful, but they are not ideal for all types of 255 settings. 256 </p><p> 257 The figure below shows the different underlying data structures 258 currently supported in this library. 259 </p><div class="figure"><a id="id-1.3.5.8.2.5.3.4.4"></a><p class="title"><strong>Figure 21.2. Underlying Associative Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_different_underlying_dss_1.png" align="middle" alt="Underlying Associative Data Structures" /></div></div></div><br class="figure-break" /><p> 260 A shows a collision-chaining hash-table, B shows a probing 261 hash-table, C shows a red-black tree, D shows a splay tree, E shows 262 a tree based on an ordered vector(implicit in the order of the 263 elements), F shows a PATRICIA trie, and G shows a list-based 264 container with update policies. 265 </p><p> 266 Each of these data structures has some performance benefits, in 267 terms of speed, size or both. For now, note that vector-based trees 268 and probing hash tables manipulate memory more efficiently than 269 red-black trees and collision-chaining hash tables, and that 270 list-based associative containers are very useful for constructing 271 "multimaps". 272 </p><p> 273 Now consider a function manipulating a generic associative 274 container, 275 </p><pre class="programlisting"> 276 template<class Cntnr> 277 int 278 some_op_sequence(Cntnr &r_cnt) 279 { 280 ... 281 } 282 </pre><p> 283 Ideally, the underlying data structure 284 of <code class="classname">Cntnr</code> would not affect what can be 285 done with <code class="varname">r_cnt</code>. Unfortunately, this is not 286 the case. 287 </p><p> 288 For example, if <code class="classname">Cntnr</code> 289 is <code class="classname">std::map</code>, then the function can 290 use 291 </p><pre class="programlisting"> 292 std::for_each(r_cnt.find(foo), r_cnt.find(bar), foobar) 293 </pre><p> 294 in order to apply <code class="classname">foobar</code> to all 295 elements between <code class="classname">foo</code> and 296 <code class="classname">bar</code>. If 297 <code class="classname">Cntnr</code> is a hash-based container, 298 then this call's results are undefined. 299 </p><p> 300 Also, if <code class="classname">Cntnr</code> is tree-based, the type 301 and object of the comparison functor can be 302 accessed. If <code class="classname">Cntnr</code> is hash based, these 303 queries are nonsensical. 304 </p><p> 305 There are various other differences based on the container's 306 underlying data structure. For one, they can be constructed by, 307 and queried for, different policies. Furthermore: 308 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 309 Containers based on C, D, E and F store elements in a 310 meaningful order; the others store elements in a meaningless 311 (and probably time-varying) order. By implication, only 312 containers based on C, D, E and F can 313 support <code class="function">erase</code> operations taking an 314 iterator and returning an iterator to the following element 315 without performance loss. 316 </p></li><li class="listitem"><p> 317 Containers based on C, D, E, and F can be split and joined 318 efficiently, while the others cannot. Containers based on C 319 and D, furthermore, can guarantee that this is exception-free; 320 containers based on E cannot guarantee this. 321 </p></li><li class="listitem"><p> 322 Containers based on all but E can guarantee that 323 erasing an element is exception free; containers based on E 324 cannot guarantee this. Containers based on all but B and E 325 can guarantee that modifying an object of their type does 326 not invalidate iterators or references to their elements, 327 while containers based on B and E cannot. Containers based 328 on C, D, and E can furthermore make a stronger guarantee, 329 namely that modifying an object of their type does not 330 affect the order of iterators. 331 </p></li></ol></div><p> 332 A unified tag and traits system (as used for the C++ standard 333 library iterators, for example) can ease generic manipulation of 334 associative containers based on different underlying data 335 structures. 336 </p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.iterators"></a>Iterators</h5></div></div></div><p> 337 Iterators are centric to the design of the standard library 338 containers, because of the container/algorithm/iterator 339 decomposition that allows an algorithm to operate on a range 340 through iterators of some sequence. Iterators, then, are useful 341 because they allow going over a 342 specific <span class="emphasis"><em>sequence</em></span>. The standard library 343 also uses iterators for accessing a 344 specific <span class="emphasis"><em>element</em></span>: when an associative 345 container returns one through <code class="function">find</code>. The 346 standard library consistently uses the same types of iterators 347 for both purposes: going over a range, and accessing a specific 348 found element. Before the introduction of hash-based containers 349 to the standard library, this made sense (with the exception of 350 priority queues, which are discussed later). 351 </p><p> 352 Using the standard associative containers together with 353 non-order-preserving associative containers (and also because of 354 priority-queues container), there is a possible need for 355 different types of iterators for self-organizing containers: 356 the iterator concept seems overloaded to mean two different 357 things (in some cases). 358 </p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="associative.iterators.using"></a>Using Point Iterators for Range Operations</h6></div></div></div><p> 359 Suppose <code class="classname">cntnr</code> is some associative 360 container, and say <code class="varname">c</code> is an object of 361 type <code class="classname">cntnr</code>. Then what will be the outcome 362 of 363 </p><pre class="programlisting"> 364 std::for_each(c.find(1), c.find(5), foo); 365 </pre><p> 366 If <code class="classname">cntnr</code> is a tree-based container 367 object, then an in-order walk will 368 apply <code class="classname">foo</code> to the relevant elements, 369 as in the graphic below, label A. If <code class="varname">c</code> is 370 a hash-based container, then the order of elements between any 371 two elements is undefined (and probably time-varying); there is 372 no guarantee that the elements traversed will coincide with the 373 <span class="emphasis"><em>logical</em></span> elements between 1 and 5, as in 374 label B. 375 </p><div class="figure"><a id="id-1.3.5.8.2.5.3.5.4.5"></a><p class="title"><strong>Figure 21.3. Range Iteration in Different Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_point_iterators_range_ops_1.png" align="middle" alt="Node Invariants" /></div></div></div><br class="figure-break" /><p> 376 In our opinion, this problem is not caused just because 377 red-black trees are order preserving while 378 collision-chaining hash tables are (generally) not - it 379 is more fundamental. Most of the standard's containers 380 order sequences in a well-defined manner that is 381 determined by their <span class="emphasis"><em>interface</em></span>: 382 calling <code class="function">insert</code> on a tree-based 383 container modifies its sequence in a predictable way, as 384 does calling <code class="function">push_back</code> on a list or 385 a vector. Conversely, collision-chaining hash tables, 386 probing hash tables, priority queues, and list-based 387 containers (which are very useful for "multimaps") are 388 self-organizing data structures; the effect of each 389 operation modifies their sequences in a manner that is 390 (practically) determined by their 391 <span class="emphasis"><em>implementation</em></span>. 392 </p><p> 393 Consequently, applying an algorithm to a sequence obtained from most 394 containers may or may not make sense, but applying it to a 395 sub-sequence of a self-organizing container does not. 396 </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="associative.iterators.cost"></a>Cost to Point Iterators to Enable Range Operations</h6></div></div></div><p> 397 Suppose <code class="varname">c</code> is some collision-chaining 398 hash-based container object, and one calls 399 </p><pre class="programlisting">c.find(3)</pre><p> 400 Then what composes the returned iterator? 401 </p><p> 402 In the graphic below, label A shows the simplest (and 403 most efficient) implementation of a collision-chaining 404 hash table. The little box marked 405 <code class="classname">point_iterator</code> shows an object 406 that contains a pointer to the element's node. Note that 407 this "iterator" has no way to move to the next element ( 408 it cannot support 409 <code class="function">operator++</code>). Conversely, the little 410 box marked <code class="classname">iterator</code> stores both a 411 pointer to the element, as well as some other 412 information (the bucket number of the element). the 413 second iterator, then, is "heavier" than the first one- 414 it requires more time and space. If we were to use a 415 different container to cross-reference into this 416 hash-table using these iterators - it would take much 417 more space. As noted above, nothing much can be done by 418 incrementing these iterators, so why is this extra 419 information needed? 420 </p><p> 421 Alternatively, one might create a collision-chaining hash-table 422 where the lists might be linked, forming a monolithic total-element 423 list, as in the graphic below, label B. Here the iterators are as 424 light as can be, but the hash-table's operations are more 425 complicated. 426 </p><div class="figure"><a id="id-1.3.5.8.2.5.3.5.5.7"></a><p class="title"><strong>Figure 21.4. Point Iteration in Hash Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_point_iterators_range_ops_2.png" align="middle" alt="Point Iteration in Hash Data Structures" /></div></div></div><br class="figure-break" /><p> 427 It should be noted that containers based on collision-chaining 428 hash-tables are not the only ones with this type of behavior; 429 many other self-organizing data structures display it as well. 430 </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="associative.iterators.invalidation"></a>Invalidation Guarantees</h6></div></div></div><p>Consider the following snippet:</p><pre class="programlisting"> 431 it = c.find(3); 432 c.erase(5); 433 </pre><p> 434 Following the call to <code class="classname">erase</code>, what is the 435 validity of <code class="classname">it</code>: can it be de-referenced? 436 can it be incremented? 437 </p><p> 438 The answer depends on the underlying data structure of the 439 container. The graphic below shows three cases: A1 and A2 show 440 a red-black tree; B1 and B2 show a probing hash-table; C1 and C2 441 show a collision-chaining hash table. 442 </p><div class="figure"><a id="id-1.3.5.8.2.5.3.5.6.6"></a><p class="title"><strong>Figure 21.5. Effect of erase in different underlying data structures</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_invalidation_guarantee_erase.png" align="middle" alt="Effect of erase in different underlying data structures" /></div></div></div><br class="figure-break" /><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 443 Erasing 5 from A1 yields A2. Clearly, an iterator to 3 can 444 be de-referenced and incremented. The sequence of iterators 445 changed, but in a way that is well-defined by the interface. 446 </p></li><li class="listitem"><p> 447 Erasing 5 from B1 yields B2. Clearly, an iterator to 3 is 448 not valid at all - it cannot be de-referenced or 449 incremented; the order of iterators changed in a way that is 450 (practically) determined by the implementation and not by 451 the interface. 452 </p></li><li class="listitem"><p> 453 Erasing 5 from C1 yields C2. Here the situation is more 454 complicated. On the one hand, there is no problem in 455 de-referencing <code class="classname">it</code>. On the other hand, 456 the order of iterators changed in a way that is 457 (practically) determined by the implementation and not by 458 the interface. 459 </p></li></ol></div><p> 460 So in the standard library containers, it is not always possible 461 to express whether <code class="varname">it</code> is valid or not. This 462 is true also for <code class="function">insert</code>. Again, the 463 iterator concept seems overloaded. 464 </p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.functions"></a>Functional</h5></div></div></div><p> 465 </p><p> 466 The design of the functional overlay to the underlying data 467 structures differs slightly from some of the conventions used in 468 the C++ standard. A strict public interface of methods that 469 comprise only operations which depend on the class's internal 470 structure; other operations are best designed as external 471 functions. (See <a class="xref" href="policy_data_structures.html#biblio.meyers02both" title="Class Template, Member Template - or Both?">[biblio.meyers02both]</a>).With this 472 rubric, the standard associative containers lack some useful 473 methods, and provide other methods which would be better 474 removed. 475 </p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.erase"></a><code class="function">erase</code></h6></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 476 Order-preserving standard associative containers provide the 477 method 478 </p><pre class="programlisting"> 479 iterator 480 erase(iterator it) 481 </pre><p> 482 which takes an iterator, erases the corresponding 483 element, and returns an iterator to the following 484 element. Also standardd hash-based associative 485 containers provide this method. This seemingly 486 increasesgenericity between associative containers, 487 since it is possible to use 488 </p><pre class="programlisting"> 489 typename C::iterator it = c.begin(); 490 typename C::iterator e_it = c.end(); 491 492 while(it != e_it) 493 it = pred(*it)? c.erase(it) : ++it; 494 </pre><p> 495 in order to erase from a container object <code class="varname"> 496 c</code> all element which match a 497 predicate <code class="classname">pred</code>. However, in a 498 different sense this actually decreases genericity: an 499 integral implication of this method is that tree-based 500 associative containers' memory use is linear in the total 501 number of elements they store, while hash-based 502 containers' memory use is unbounded in the total number of 503 elements they store. Assume a hash-based container is 504 allowed to decrease its size when an element is 505 erased. Then the elements might be rehashed, which means 506 that there is no "next" element - it is simply 507 undefined. Consequently, it is possible to infer from the 508 fact that the standard library's hash-based containers 509 provide this method that they cannot downsize when 510 elements are erased. As a consequence, different code is 511 needed to manipulate different containers, assuming that 512 memory should be conserved. Therefor, this library's 513 non-order preserving associative containers omit this 514 method. 515 </p></li><li class="listitem"><p> 516 All associative containers include a conditional-erase method 517 </p><pre class="programlisting"> 518 template< 519 class Pred> 520 size_type 521 erase_if 522 (Pred pred) 523 </pre><p> 524 which erases all elements matching a predicate. This is probably the 525 only way to ensure linear-time multiple-item erase which can 526 actually downsize a container. 527 </p></li><li class="listitem"><p> 528 The standard associative containers provide methods for 529 multiple-item erase of the form 530 </p><pre class="programlisting"> 531 size_type 532 erase(It b, It e) 533 </pre><p> 534 erasing a range of elements given by a pair of 535 iterators. For tree-based or trie-based containers, this can 536 implemented more efficiently as a (small) sequence of split 537 and join operations. For other, unordered, containers, this 538 method isn't much better than an external loop. Moreover, 539 if <code class="varname">c</code> is a hash-based container, 540 then 541 </p><pre class="programlisting"> 542 c.erase(c.find(2), c.find(5)) 543 </pre><p> 544 is almost certain to do something 545 different than erasing all elements whose keys are between 2 546 and 5, and is likely to produce other undefined behavior. 547 </p></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.split"></a> 548 <code class="function">split</code> and <code class="function">join</code> 549 </h6></div></div></div><p> 550 It is well-known that tree-based and trie-based container 551 objects can be efficiently split or joined (See 552 <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>). Externally splitting or 553 joining trees is super-linear, and, furthermore, can throw 554 exceptions. Split and join methods, consequently, seem good 555 choices for tree-based container methods, especially, since as 556 noted just before, they are efficient replacements for erasing 557 sub-sequences. 558 </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.insert"></a> 559 <code class="function">insert</code> 560 </h6></div></div></div><p> 561 The standard associative containers provide methods of the form 562 </p><pre class="programlisting"> 563 template<class It> 564 size_type 565 insert(It b, It e); 566 </pre><p> 567 for inserting a range of elements given by a pair of 568 iterators. At best, this can be implemented as an external loop, 569 or, even more efficiently, as a join operation (for the case of 570 tree-based or trie-based containers). Moreover, these methods seem 571 similar to constructors taking a range given by a pair of 572 iterators; the constructors, however, are transactional, whereas 573 the insert methods are not; this is possibly confusing. 574 </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.compare"></a> 575 <code class="function">operator==</code> and <code class="function">operator<=</code> 576 </h6></div></div></div><p> 577 Associative containers are parametrized by policies allowing to 578 test key equivalence: a hash-based container can do this through 579 its equivalence functor, and a tree-based container can do this 580 through its comparison functor. In addition, some standard 581 associative containers have global function operators, like 582 <code class="function">operator==</code> and <code class="function">operator<=</code>, 583 that allow comparing entire associative containers. 584 </p><p> 585 In our opinion, these functions are better left out. To begin 586 with, they do not significantly improve over an external 587 loop. More importantly, however, they are possibly misleading - 588 <code class="function">operator==</code>, for example, usually checks for 589 equivalence, or interchangeability, but the associative 590 container cannot check for values' equivalence, only keys' 591 equivalence; also, are two containers considered equivalent if 592 they store the same values in different order? this is an 593 arbitrary decision. 594 </p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.motivation.priority_queue"></a>Priority Queues</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.policy"></a>Policy Choices</h5></div></div></div><p> 595 Priority queues are containers that allow efficiently inserting 596 values and accessing the maximal value (in the sense of the 597 container's comparison functor). Their interface 598 supports <code class="function">push</code> 599 and <code class="function">pop</code>. The standard 600 container <code class="classname">std::priorityqueue</code> indeed support 601 these methods, but little else. For algorithmic and 602 software-engineering purposes, other methods are needed: 603 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 604 Many graph algorithms (see 605 <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>) require increasing a 606 value in a priority queue (again, in the sense of the 607 container's comparison functor), or joining two 608 priority-queue objects. 609 </p></li><li class="listitem"><p>The return type of <code class="classname">priority_queue</code>'s 610 <code class="function">push</code> method is a point-type iterator, which can 611 be used for modifying or erasing arbitrary values. For 612 example:</p><pre class="programlisting"> 613 priority_queue<int> p; 614 priority_queue<int>::point_iterator it = p.push(3); 615 p.modify(it, 4); 616 </pre><p>These types of cross-referencing operations are necessary 617 for making priority queues useful for different applications, 618 especially graph applications.</p></li><li class="listitem"><p> 619 It is sometimes necessary to erase an arbitrary value in a 620 priority queue. For example, consider 621 the <code class="function">select</code> function for monitoring 622 file descriptors: 623 </p><pre class="programlisting"> 624 int 625 select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds, 626 struct timeval *timeout); 627 </pre><p> 628 then, as the select documentation states: 629 </p><p> 630 <span class="quote">“<span class="quote"> 631 The nfds argument specifies the range of file 632 descriptors to be tested. The select() function tests file 633 descriptors in the range of 0 to nfds-1.</span>”</span> 634 </p><p> 635 It stands to reason, therefore, that we might wish to 636 maintain a minimal value for <code class="varname">nfds</code>, and 637 priority queues immediately come to mind. Note, though, that 638 when a socket is closed, the minimal file description might 639 change; in the absence of an efficient means to erase an 640 arbitrary value from a priority queue, we might as well 641 avoid its use altogether. 642 </p><p> 643 The standard containers typically support iterators. It is 644 somewhat unusual 645 for <code class="classname">std::priority_queue</code> to omit them 646 (See <a class="xref" href="policy_data_structures.html#biblio.meyers01stl" title="Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library">[biblio.meyers01stl]</a>). One might 647 ask why do priority queues need to support iterators, since 648 they are self-organizing containers with a different purpose 649 than abstracting sequences. There are several reasons: 650 </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p> 651 Iterators (even in self-organizing containers) are 652 useful for many purposes: cross-referencing 653 containers, serialization, and debugging code that uses 654 these containers. 655 </p></li><li class="listitem"><p> 656 The standard library's hash-based containers support 657 iterators, even though they too are self-organizing 658 containers with a different purpose than abstracting 659 sequences. 660 </p></li><li class="listitem"><p> 661 In standard-library-like containers, it is natural to specify the 662 interface of operations for modifying a value or erasing 663 a value (discussed previously) in terms of a iterators. 664 It should be noted that the standard 665 containers also use iterators for accessing and 666 manipulating a specific value. In hash-based 667 containers, one checks the existence of a key by 668 comparing the iterator returned by <code class="function">find</code> to the 669 iterator returned by <code class="function">end</code>, and not by comparing a 670 pointer returned by <code class="function">find</code> to <span class="type">NULL</span>. 671 </p></li></ol></div></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.underlying"></a>Underlying Data Structures</h5></div></div></div><p> 672 There are three main implementations of priority queues: the 673 first employs a binary heap, typically one which uses a 674 sequence; the second uses a tree (or forest of trees), which is 675 typically less structured than an associative container's tree; 676 the third simply uses an associative container. These are 677 shown in the figure below with labels A1 and A2, B, and C. 678 </p><div class="figure"><a id="id-1.3.5.8.2.5.4.3.3"></a><p class="title"><strong>Figure 21.6. Underlying Priority Queue Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_different_underlying_dss_2.png" align="middle" alt="Underlying Priority Queue Data Structures" /></div></div></div><br class="figure-break" /><p> 679 No single implementation can completely replace any of the 680 others. Some have better <code class="function">push</code> 681 and <code class="function">pop</code> amortized performance, some have 682 better bounded (worst case) response time than others, some 683 optimize a single method at the expense of others, etc. In 684 general the "best" implementation is dictated by the specific 685 problem. 686 </p><p> 687 As with associative containers, the more implementations 688 co-exist, the more necessary a traits mechanism is for handling 689 generic containers safely and efficiently. This is especially 690 important for priority queues, since the invalidation guarantees 691 of one of the most useful data structures - binary heaps - is 692 markedly different than those of most of the others. 693 </p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.binary_heap"></a>Binary Heaps</h5></div></div></div><p> 694 Binary heaps are one of the most useful underlying 695 data structures for priority queues. They are very efficient in 696 terms of memory (since they don't require per-value structure 697 metadata), and have the best amortized <code class="function">push</code> and 698 <code class="function">pop</code> performance for primitive types like 699 <span class="type">int</span>. 700 </p><p> 701 The standard library's <code class="classname">priority_queue</code> 702 implements this data structure as an adapter over a sequence, 703 typically 704 <code class="classname">std::vector</code> 705 or <code class="classname">std::deque</code>, which correspond to labels 706 A1 and A2 respectively in the graphic above. 707 </p><p> 708 This is indeed an elegant example of the adapter concept and 709 the algorithm/container/iterator decomposition. (See <a class="xref" href="policy_data_structures.html#biblio.nelson96stlpq" title="Priority Queues and the STL">[biblio.nelson96stlpq]</a>). There are 710 several reasons why a binary-heap priority queue 711 may be better implemented as a container instead of a 712 sequence adapter: 713 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 714 <code class="classname">std::priority_queue</code> cannot erase values 715 from its adapted sequence (irrespective of the sequence 716 type). This means that the memory use of 717 an <code class="classname">std::priority_queue</code> object is always 718 proportional to the maximal number of values it ever contained, 719 and not to the number of values that it currently 720 contains. (See <code class="filename">performance/priority_queue_text_pop_mem_usage.cc</code>.) 721 This implementation of binary heaps acts very differently than 722 other underlying data structures (See also pairing heaps). 723 </p></li><li class="listitem"><p> 724 Some combinations of adapted sequences and value types 725 are very inefficient or just don't make sense. If one uses 726 <code class="classname">std::priority_queue<std::vector<std::string> 727 > ></code>, for example, then not only will each 728 operation perform a logarithmic number of 729 <code class="classname">std::string</code> assignments, but, furthermore, any 730 operation (including <code class="function">pop</code>) can render the container 731 useless due to exceptions. Conversely, if one uses 732 <code class="classname">std::priority_queue<std::deque<int> > 733 ></code>, then each operation uses incurs a logarithmic 734 number of indirect accesses (through pointers) unnecessarily. 735 It might be better to let the container make a conservative 736 deduction whether to use the structure in the graphic above, labels A1 or A2. 737 </p></li><li class="listitem"><p> 738 There does not seem to be a systematic way to determine 739 what exactly can be done with the priority queue. 740 </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p> 741 If <code class="classname">p</code> is a priority queue adapting an 742 <code class="classname">std::vector</code>, then it is possible to iterate over 743 all values by using <code class="function">&p.top()</code> and 744 <code class="function">&p.top() + p.size()</code>, but this will not work 745 if <code class="varname">p</code> is adapting an <code class="classname">std::deque</code>; in any 746 case, one cannot use <code class="classname">p.begin()</code> and 747 <code class="classname">p.end()</code>. If a different sequence is adapted, it 748 is even more difficult to determine what can be 749 done. 750 </p></li><li class="listitem"><p> 751 If <code class="varname">p</code> is a priority queue adapting an 752 <code class="classname">std::deque</code>, then the reference return by 753 </p><pre class="programlisting"> 754 p.top() 755 </pre><p> 756 will remain valid until it is popped, 757 but if <code class="varname">p</code> adapts an <code class="classname">std::vector</code>, the 758 next <code class="function">push</code> will invalidate it. If a different 759 sequence is adapted, it is even more difficult to 760 determine what can be done. 761 </p></li></ol></div></li><li class="listitem"><p> 762 Sequence-based binary heaps can still implement 763 linear-time <code class="function">erase</code> and <code class="function">modify</code> operations. 764 This means that if one needs to erase a small 765 (say logarithmic) number of values, then one might still 766 choose this underlying data structure. Using 767 <code class="classname">std::priority_queue</code>, however, this will generally 768 change the order of growth of the entire sequence of 769 operations. 770 </p></li></ol></div></div></div></div></div><div class="bibliography"><div class="titlepage"><div><div><h2 class="title"><a id="pbds.biblio"></a>Bibliography</h2></div></div></div><div class="biblioentry"><a id="biblio.abrahams97exception"></a><p>[biblio.abrahams97exception] <span class="title"><em> 771 <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1075.pdf" target="_top"> 772 STL Exception Handling Contract 773 </a> 774 </em>. </span><span class="date">1997. </span><span class="author"><span class="firstname"> 775 Dave 776 </span> <span class="surname"> 777 Abrahams 778 </span>. </span><span class="publisher"><span class="publishername"> 779 ISO SC22/WG21 780 . </span></span></p></div><div class="biblioentry"><a id="biblio.alexandrescu01modern"></a><p>[biblio.alexandrescu01modern] <span class="title"><em> 781 Modern C++ Design: Generic Programming and Design Patterns Applied 782 </em>. </span><span class="date"> 783 2001 784 . </span><span class="author"><span class="firstname"> 785 Andrei 786 </span> <span class="surname"> 787 Alexandrescu 788 </span>. </span><span class="publisher"><span class="publishername"> 789 Addison-Wesley Publishing Company 790 . </span></span></p></div><div class="biblioentry"><a id="biblio.andrew04mtf"></a><p>[biblio.andrew04mtf] <span class="title"><em> 791 MTF, Bit, and COMB: A Guide to Deterministic and Randomized 792 Algorithms for the List Update Problem 793 </em>. </span><span class="authorgroup"><span class="firstname"> 794 K. 795 </span> <span class="surname"> 796 Andrew 797 </span> and <span class="firstname"> 798 D. 799 </span> <span class="surname"> 800 Gleich 801 </span>. </span></p></div><div class="biblioentry"><a id="biblio.austern00noset"></a><p>[biblio.austern00noset] <span class="title"><em> 802 Why You Shouldn't Use set - and What You Should Use Instead 803 </em>. </span><span class="date"> 804 April, 2000 805 . </span><span class="author"><span class="firstname"> 806 Matthew 807 </span> <span class="surname"> 808 Austern 809 </span>. </span><span class="publisher"><span class="publishername"> 810 C++ Report 811 . </span></span></p></div><div class="biblioentry"><a id="biblio.austern01htprop"></a><p>[biblio.austern01htprop] <span class="title"><em> 812 <a class="link" href="http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2001/n1326.html" target="_top"> 813 A Proposal to Add Hashtables to the Standard Library 814 </a> 815 </em>. </span><span class="date"> 816 2001 817 . </span><span class="author"><span class="firstname"> 818 Matthew 819 </span> <span class="surname"> 820 Austern 821 </span>. </span><span class="publisher"><span class="publishername"> 822 ISO SC22/WG21 823 . </span></span></p></div><div class="biblioentry"><a id="biblio.austern98segmentedit"></a><p>[biblio.austern98segmentedit] <span class="title"><em> 824 Segmented iterators and hierarchical algorithms 825 </em>. </span><span class="date"> 826 April, 1998 827 . </span><span class="author"><span class="firstname"> 828 Matthew 829 </span> <span class="surname"> 830 Austern 831 </span>. </span><span class="publisher"><span class="publishername"> 832 Generic Programming 833 . </span></span></p></div><div class="biblioentry"><a id="biblio.dawestimer"></a><p>[biblio.dawestimer] <span class="title"><em> 834 <a class="link" href="http://www.boost.org/libs/timer/" target="_top"> 835 Boost Timer Library 836 </a> 837 </em>. </span><span class="author"><span class="firstname"> 838 Beeman 839 </span> <span class="surname"> 840 Dawes 841 </span>. </span><span class="publisher"><span class="publishername"> 842 Boost 843 . </span></span></p></div><div class="biblioentry"><a id="biblio.clearypool"></a><p>[biblio.clearypool] <span class="title"><em> 844 <a class="link" href="http://www.boost.org/libs/pool/" target="_top"> 845 Boost Pool Library 846 </a> 847 </em>. </span><span class="author"><span class="firstname"> 848 Stephen 849 </span> <span class="surname"> 850 Cleary 851 </span>. </span><span class="publisher"><span class="publishername"> 852 Boost 853 . </span></span></p></div><div class="biblioentry"><a id="biblio.maddocktraits"></a><p>[biblio.maddocktraits] <span class="title"><em> 854 <a class="link" href="http://www.boost.org/libs/type_traits/" target="_top"> 855 Boost Type Traits Library 856 </a> 857 </em>. </span><span class="authorgroup"><span class="firstname"> 858 Maddock 859 </span> <span class="surname"> 860 John 861 </span> and <span class="firstname"> 862 Stephen 863 </span> <span class="surname"> 864 Cleary 865 </span>. </span><span class="publisher"><span class="publishername"> 866 Boost 867 . </span></span></p></div><div class="biblioentry"><a id="biblio.brodal96priority"></a><p>[biblio.brodal96priority] <span class="title"><em> 868 <a class="link" href="https://dl.acm.org/citation.cfm?id=313883" target="_top"> 869 Worst-case efficient priority queues 870 </a> 871 </em>. </span><span class="author"><span class="firstname"> 872 Gerth 873 </span> <span class="surname"> 874 Stolting Brodal 875 </span>. </span></p></div><div class="biblioentry"><a id="biblio.bulkamayheweff"></a><p>[biblio.bulkamayheweff] <span class="title"><em> 876 Efficient C++ Programming Techniques 877 </em>. </span><span class="date"> 878 1997 879 . </span><span class="authorgroup"><span class="firstname"> 880 D. 881 </span> <span class="surname"> 882 Bulka 883 </span> and <span class="firstname"> 884 D. 885 </span> <span class="surname"> 886 Mayhew 887 </span>. </span><span class="publisher"><span class="publishername"> 888 Addison-Wesley Publishing Company 889 . </span></span></p></div><div class="biblioentry"><a id="biblio.clrs2001"></a><p>[biblio.clrs2001] <span class="title"><em> 890 Introduction to Algorithms, 2nd edition 891 </em>. </span><span class="date"> 892 2001 893 . </span><span class="authorgroup"><span class="firstname"> 894 T. H. 895 </span> <span class="surname"> 896 Cormen 897 </span>, <span class="firstname"> 898 C. E. 899 </span> <span class="surname"> 900 Leiserson 901 </span>, <span class="firstname"> 902 R. L. 903 </span> <span class="surname"> 904 Rivest 905 </span>, and <span class="firstname"> 906 C. 907 </span> <span class="surname"> 908 Stein 909 </span>. </span><span class="publisher"><span class="publishername"> 910 MIT Press 911 . </span></span></p></div><div class="biblioentry"><a id="biblio.dubhashi98neg"></a><p>[biblio.dubhashi98neg] <span class="title"><em> 912 Balls and bins: A study in negative dependence 913 </em>. </span><span class="date"> 914 1998 915 . </span><span class="authorgroup"><span class="firstname"> 916 D. 917 </span> <span class="surname"> 918 Dubashi 919 </span> and <span class="firstname"> 920 D. 921 </span> <span class="surname"> 922 Ranjan 923 </span>. </span><span class="publisher"><span class="publishername"> 924 Random Structures and Algorithms 13 925 . </span></span></p></div><div class="biblioentry"><a id="biblio.fagin79extendible"></a><p>[biblio.fagin79extendible] <span class="title"><em> 926 Extendible hashing - a fast access method for dynamic files 927 </em>. </span><span class="date"> 928 1979 929 . </span><span class="authorgroup"><span class="firstname"> 930 R. 931 </span> <span class="surname"> 932 Fagin 933 </span>, <span class="firstname"> 934 J. 935 </span> <span class="surname"> 936 Nievergelt 937 </span>, <span class="firstname"> 938 N. 939 </span> <span class="surname"> 940 Pippenger 941 </span>, and <span class="firstname"> 942 H. R. 943 </span> <span class="surname"> 944 Strong 945 </span>. </span><span class="publisher"><span class="publishername"> 946 ACM Trans. Database Syst. 4 947 . </span></span></p></div><div class="biblioentry"><a id="biblio.filliatre2000ptset"></a><p>[biblio.filliatre2000ptset] <span class="title"><em> 948 <a class="link" href="http://cristal.inria.fr/~frisch/icfp06_contest/advtr/applyOmatic/ptset.ml" target="_top"> 949 Ptset: Sets of integers implemented as Patricia trees 950 </a> 951 </em>. </span><span class="date"> 952 2000 953 . </span><span class="author"><span class="firstname"> 954 Jean-Christophe 955 </span> <span class="surname"> 956 Filliatre 957 </span>. </span></p></div><div class="biblioentry"><a id="biblio.fredman86pairing"></a><p>[biblio.fredman86pairing] <span class="title"><em> 958 <a class="link" href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf" target="_top"> 959 The pairing heap: a new form of self-adjusting heap 960 </a> 961 </em>. </span><span class="date"> 962 1986 963 . </span><span class="authorgroup"><span class="firstname"> 964 M. L. 965 </span> <span class="surname"> 966 Fredman 967 </span>, <span class="firstname"> 968 R. 969 </span> <span class="surname"> 970 Sedgewick 971 </span>, <span class="firstname"> 972 D. D. 973 </span> <span class="surname"> 974 Sleator 975 </span>, and <span class="firstname"> 976 R. E. 977 </span> <span class="surname"> 978 Tarjan 979 </span>. </span></p></div><div class="biblioentry"><a id="biblio.gof"></a><p>[biblio.gof] <span class="title"><em> 980 Design Patterns - Elements of Reusable Object-Oriented Software 981 </em>. </span><span class="date"> 982 1995 983 . </span><span class="authorgroup"><span class="firstname"> 984 E. 985 </span> <span class="surname"> 986 Gamma 987 </span>, <span class="firstname"> 988 R. 989 </span> <span class="surname"> 990 Helm 991 </span>, <span class="firstname"> 992 R. 993 </span> <span class="surname"> 994 Johnson 995 </span>, and <span class="firstname"> 996 J. 997 </span> <span class="surname"> 998 Vlissides 999 </span>. </span><span class="publisher"><span class="publishername"> 1000 Addison-Wesley Publishing Company 1001 . </span></span></p></div><div class="biblioentry"><a id="biblio.garg86order"></a><p>[biblio.garg86order] <span class="title"><em> 1002 Order-preserving key transformations 1003 </em>. </span><span class="date"> 1004 1986 1005 . </span><span class="authorgroup"><span class="firstname"> 1006 A. K. 1007 </span> <span class="surname"> 1008 Garg 1009 </span> and <span class="firstname"> 1010 C. C. 1011 </span> <span class="surname"> 1012 Gotlieb 1013 </span>. </span><span class="publisher"><span class="publishername"> 1014 Trans. Database Syst. 11 1015 . </span></span></p></div><div class="biblioentry"><a id="biblio.hyslop02making"></a><p>[biblio.hyslop02making] <span class="title"><em> 1016 Making a real hash of things 1017 </em>. </span><span class="date"> 1018 May 2002 1019 . </span><span class="authorgroup"><span class="firstname"> 1020 J. 1021 </span> <span class="surname"> 1022 Hyslop 1023 </span> and <span class="firstname"> 1024 Herb 1025 </span> <span class="surname"> 1026 Sutter 1027 </span>. </span><span class="publisher"><span class="publishername"> 1028 C++ Report 1029 . </span></span></p></div><div class="biblioentry"><a id="biblio.jossutis01stl"></a><p>[biblio.jossutis01stl] <span class="title"><em> 1030 The C++ Standard Library - A Tutorial and Reference 1031 </em>. </span><span class="date"> 1032 2001 1033 . </span><span class="author"><span class="firstname"> 1034 N. M. 1035 </span> <span class="surname"> 1036 Jossutis 1037 </span>. </span><span class="publisher"><span class="publishername"> 1038 Addison-Wesley Publishing Company 1039 . </span></span></p></div><div class="biblioentry"><a id="biblio.kt99fat_heaps"></a><p>[biblio.kt99fat_heaps] <span class="title"><em> 1040 <a class="link" href="http://www.cs.princeton.edu/research/techreps/TR-597-99" target="_top"> 1041 New Heap Data Structures 1042 </a> 1043 </em>. </span><span class="date"> 1044 1999 1045 . </span><span class="authorgroup"><span class="firstname"> 1046 Haim 1047 </span> <span class="surname"> 1048 Kaplan 1049 </span> and <span class="firstname"> 1050 Robert E. 1051 </span> <span class="surname"> 1052 Tarjan 1053 </span>. </span></p></div><div class="biblioentry"><a id="biblio.kleft00sets"></a><p>[biblio.kleft00sets] <span class="title"><em> 1054 Are Set Iterators Mutable or Immutable? 1055 </em>. </span><span class="date"> 1056 October 2000 1057 . </span><span class="authorgroup"><span class="firstname"> 1058 Angelika 1059 </span> <span class="surname"> 1060 Langer 1061 </span> and <span class="firstname"> 1062 Klaus 1063 </span> <span class="surname"> 1064 Kleft 1065 </span>. </span><span class="publisher"><span class="publishername"> 1066 C/C++ Users Jornal 1067 . </span></span></p></div><div class="biblioentry"><a id="biblio.knuth98sorting"></a><p>[biblio.knuth98sorting] <span class="title"><em> 1068 The Art of Computer Programming - Sorting and Searching 1069 </em>. </span><span class="date"> 1070 1998 1071 . </span><span class="author"><span class="firstname"> 1072 D. E. 1073 </span> <span class="surname"> 1074 Knuth 1075 </span>. </span><span class="publisher"><span class="publishername"> 1076 Addison-Wesley Publishing Company 1077 . </span></span></p></div><div class="biblioentry"><a id="biblio.liskov98data"></a><p>[biblio.liskov98data] <span class="title"><em> 1078 Data abstraction and hierarchy 1079 </em>. </span><span class="date"> 1080 May 1998 1081 . </span><span class="author"><span class="firstname"> 1082 B. 1083 </span> <span class="surname"> 1084 Liskov 1085 </span>. </span><span class="publisher"><span class="publishername"> 1086 SIGPLAN Notices 23 1087 . </span></span></p></div><div class="biblioentry"><a id="biblio.litwin80lh"></a><p>[biblio.litwin80lh] <span class="title"><em> 1088 Linear hashing: A new tool for file and table addressing 1089 </em>. </span><span class="date"> 1090 June 1980 1091 . </span><span class="author"><span class="firstname"> 1092 W. 1093 </span> <span class="surname"> 1094 Litwin 1095 </span>. </span><span class="publisher"><span class="publishername"> 1096 Proceedings of International Conference on Very Large Data Bases 1097 . </span></span></p></div><div class="biblioentry"><a id="biblio.maverick_lowerbounds"></a><p>[biblio.maverick_lowerbounds] <span class="title"><em> 1098 Deamortization - Part 2: Binomial Heaps 1099 </em>. </span><span class="date"> 1100 2005 1101 . </span><span class="author"><span class="firstname"> 1102 Maverick 1103 </span> <span class="surname"> 1104 Woo 1105 </span>. </span></p></div><div class="biblioentry"><a id="biblio.meyers96more"></a><p>[biblio.meyers96more] <span class="title"><em> 1106 More Effective C++: 35 New Ways to Improve Your Programs and Designs 1107 </em>. </span><span class="date"> 1108 1996 1109 . </span><span class="author"><span class="firstname"> 1110 Scott 1111 </span> <span class="surname"> 1112 Meyers 1113 </span>. </span><span class="publisher"><span class="publishername"> 1114 Addison-Wesley Publishing Company 1115 . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers00nonmember"></a><p>[biblio.meyers00nonmember] <span class="title"><em> 1116 How Non-Member Functions Improve Encapsulation 1117 </em>. </span><span class="date"> 1118 2000 1119 . </span><span class="author"><span class="firstname"> 1120 Scott 1121 </span> <span class="surname"> 1122 Meyers 1123 </span>. </span><span class="publisher"><span class="publishername"> 1124 C/C++ Users Journal 1125 . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers01stl"></a><p>[biblio.meyers01stl] <span class="title"><em> 1126 Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library 1127 </em>. </span><span class="date"> 1128 2001 1129 . </span><span class="author"><span class="firstname"> 1130 Scott 1131 </span> <span class="surname"> 1132 Meyers 1133 </span>. </span><span class="publisher"><span class="publishername"> 1134 Addison-Wesley Publishing Company 1135 . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers02both"></a><p>[biblio.meyers02both] <span class="title"><em> 1136 Class Template, Member Template - or Both? 1137 </em>. </span><span class="date"> 1138 2003 1139 . </span><span class="author"><span class="firstname"> 1140 Scott 1141 </span> <span class="surname"> 1142 Meyers 1143 </span>. </span><span class="publisher"><span class="publishername"> 1144 C/C++ Users Journal 1145 . </span></span></p></div><div class="biblioentry"><a id="biblio.motwani95random"></a><p>[biblio.motwani95random] <span class="title"><em> 1146 Randomized Algorithms 1147 </em>. </span><span class="date"> 1148 2003 1149 . </span><span class="authorgroup"><span class="firstname"> 1150 R. 1151 </span> <span class="surname"> 1152 Motwani 1153 </span> and <span class="firstname"> 1154 P. 1155 </span> <span class="surname"> 1156 Raghavan 1157 </span>. </span><span class="publisher"><span class="publishername"> 1158 Cambridge University Press 1159 . </span></span></p></div><div class="biblioentry"><a id="biblio.mscom"></a><p>[biblio.mscom] <span class="title"><em> 1160 <a class="link" href="https://docs.microsoft.com/en-us/windows/win32/com/the-component-object-model" target="_top"> 1161 COM: Component Model Object Technologies 1162 </a> 1163 </em>. </span><span class="publisher"><span class="publishername"> 1164 Microsoft 1165 . </span></span></p></div><div class="biblioentry"><a id="biblio.musser95rationale"></a><p>[biblio.musser95rationale] <span class="title"><em> 1166 Rationale for Adding Hash Tables to the C++ Standard Template Library 1167 </em>. </span><span class="date"> 1168 1995 1169 . </span><span class="author"><span class="firstname"> 1170 David R. 1171 </span> <span class="surname"> 1172 Musser 1173 </span>. </span></p></div><div class="biblioentry"><a id="biblio.musser96stltutorial"></a><p>[biblio.musser96stltutorial] <span class="title"><em> 1174 STL Tutorial and Reference Guide 1175 </em>. </span><span class="date"> 1176 1996 1177 . </span><span class="authorgroup"><span class="firstname"> 1178 David R. 1179 </span> <span class="surname"> 1180 Musser 1181 </span> and <span class="firstname"> 1182 A. 1183 </span> <span class="surname"> 1184 Saini 1185 </span>. </span><span class="publisher"><span class="publishername"> 1186 Addison-Wesley Publishing Company 1187 . </span></span></p></div><div class="biblioentry"><a id="biblio.nelson96stlpq"></a><p>[biblio.nelson96stlpq] <span class="title"><em> 1188 <a class="link" href="https://marknelson.us/posts/1996/01/01/priority-queues.html" target="_top">Priority Queues and the STL 1189 </a> 1190 </em>. </span><span class="date"> 1191 January 1996 1192 . </span><span class="author"><span class="firstname"> 1193 Mark 1194 </span> <span class="surname"> 1195 Nelson 1196 </span>. </span><span class="publisher"><span class="publishername"> 1197 Dr. Dobbs Journal 1198 . </span></span></p></div><div class="biblioentry"><a id="biblio.okasaki98mereable"></a><p>[biblio.okasaki98mereable] <span class="title"><em> 1199 Fast mergeable integer maps 1200 </em>. </span><span class="date"> 1201 September 1998 1202 . </span><span class="authorgroup"><span class="firstname"> 1203 C. 1204 </span> <span class="surname"> 1205 Okasaki 1206 </span> and <span class="firstname"> 1207 A. 1208 </span> <span class="surname"> 1209 Gill 1210 </span>. </span><span class="publisher"><span class="publishername"> 1211 In Workshop on ML 1212 . </span></span></p></div><div class="biblioentry"><a id="biblio.sgi_stl"></a><p>[biblio.sgi_stl] <span class="title"><em> 1213 <a class="link" href="https://web.archive.org/web/20171225062613/http://www.sgi.com/tech/stl/" target="_top"> 1214 Standard Template Library Programmer's Guide 1215 </a> 1216 </em>. </span><span class="author"><span class="firstname"> 1217 Matt 1218 </span> <span class="surname"> 1219 Austern 1220 </span>. </span><span class="publisher"><span class="publishername"> 1221 SGI 1222 . </span></span></p></div><div class="biblioentry"><a id="biblio.select_man"></a><p>[biblio.select_man] <span class="title"><em> 1223 <a class="link" href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/select.html" target="_top"> 1224 select 1225 </a> 1226 </em>. </span></p></div><div class="biblioentry"><a id="biblio.sleator84amortized"></a><p>[biblio.sleator84amortized] <span class="title"><em> 1227 Amortized Efficiency of List Update Problems 1228 </em>. </span><span class="date"> 1229 1984 1230 . </span><span class="authorgroup"><span class="firstname"> 1231 D. D. 1232 </span> <span class="surname"> 1233 Sleator 1234 </span> and <span class="firstname"> 1235 R. E. 1236 </span> <span class="surname"> 1237 Tarjan 1238 </span>. </span><span class="publisher"><span class="publishername"> 1239 ACM Symposium on Theory of Computing 1240 . </span></span></p></div><div class="biblioentry"><a id="biblio.sleator85self"></a><p>[biblio.sleator85self] <span class="title"><em> 1241 Self-Adjusting Binary Search Trees 1242 </em>. </span><span class="date"> 1243 1985 1244 . </span><span class="authorgroup"><span class="firstname"> 1245 D. D. 1246 </span> <span class="surname"> 1247 Sleator 1248 </span> and <span class="firstname"> 1249 R. E. 1250 </span> <span class="surname"> 1251 Tarjan 1252 </span>. </span><span class="publisher"><span class="publishername"> 1253 ACM Symposium on Theory of Computing 1254 . </span></span></p></div><div class="biblioentry"><a id="biblio.stepanov94standard"></a><p>[biblio.stepanov94standard] <span class="title"><em> 1255 The Standard Template Library 1256 </em>. </span><span class="date"> 1257 1984 1258 . </span><span class="authorgroup"><span class="firstname"> 1259 A. A. 1260 </span> <span class="surname"> 1261 Stepanov 1262 </span> and <span class="firstname"> 1263 M. 1264 </span> <span class="surname"> 1265 Lee 1266 </span>. </span></p></div><div class="biblioentry"><a id="biblio.stroustrup97cpp"></a><p>[biblio.stroustrup97cpp] <span class="title"><em> 1267 The C++ Programming Langugage 1268 </em>. </span><span class="date"> 1269 1997 1270 . </span><span class="author"><span class="firstname"> 1271 Bjarne 1272 </span> <span class="surname"> 1273 Stroustrup 1274 </span>. </span><span class="publisher"><span class="publishername"> 1275 Addison-Wesley Publishing Company 1276 . </span></span></p></div><div class="biblioentry"><a id="biblio.vandevoorde2002cpptemplates"></a><p>[biblio.vandevoorde2002cpptemplates] <span class="title"><em> 1277 C++ Templates: The Complete Guide 1278 </em>. </span><span class="date"> 1279 2002 1280 . </span><span class="authorgroup"><span class="firstname"> 1281 D. 1282 </span> <span class="surname"> 1283 Vandevoorde 1284 </span> and <span class="firstname"> 1285 N. M. 1286 </span> <span class="surname"> 1287 Josuttis 1288 </span>. </span><span class="publisher"><span class="publishername"> 1289 Addison-Wesley Publishing Company 1290 . </span></span></p></div><div class="biblioentry"><a id="biblio.wickland96thirty"></a><p>[biblio.wickland96thirty] <span class="title"><em> 1291 Thirty Years Among the Dead 1292 </em>. </span><span class="date"> 1293 1996 1294 . </span><span class="author"><span class="firstname"> 1295 C. A. 1296 </span> <span class="surname"> 1297 Wickland 1298 </span>. </span><span class="publisher"><span class="publishername"> 1299 National Psychological Institute 1300 . </span></span></p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bitmap_allocator_impl.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="extensions.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Implementation </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Using</td></tr></table></div></body></html>
