Merge branches/gcc-4_9-branch rev 225109.
[official-gcc.git] / gcc-4_9-branch / libstdc++-v3 / doc / html / manual / policy_data_structures.html
blob86cf2e81f68d20e761ea67af2168eebddb42dc18
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 22. Policy-Based Data Structures</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.78.1" /><meta name="keywords" content="ISO C++, policy, container, data, structure, associated, tree, trie, hash, metaprogramming" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="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 22. 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
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 22. 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&lt;typename Cntnr&gt;
115 void
116 some_op_sequence(Cntnr&amp; r_cnt)
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 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>.
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="idm270862658832"></a><p class="title"><strong>Figure 22.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="idm270862652112"></a><p class="title"><strong>Figure 22.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&lt;class Cntnr&gt;
278 some_op_sequence(Cntnr &amp;r_cnt)
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
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). <em><span class="remark"> XXX
358 "ds_gen.html#find_range"&gt;Design::Associative
359 Containers::Data-Structure Genericity::Point-Type and Range-Type
360 Methods</span></em>.
361 </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>
362 Suppose <code class="classname">cntnr</code> is some associative
363 container, and say <code class="varname">c</code> is an object of
364 type <code class="classname">cntnr</code>. Then what will be the outcome
366 </p><pre class="programlisting">
367 std::for_each(c.find(1), c.find(5), foo);
368 </pre><p>
369 If <code class="classname">cntnr</code> is a tree-based container
370 object, then an in-order walk will
371 apply <code class="classname">foo</code> to the relevant elements,
372 as in the graphic below, label A. If <code class="varname">c</code> is
373 a hash-based container, then the order of elements between any
374 two elements is undefined (and probably time-varying); there is
375 no guarantee that the elements traversed will coincide with the
376 <span class="emphasis"><em>logical</em></span> elements between 1 and 5, as in
377 label B.
378 </p><div class="figure"><a id="idm270862620480"></a><p class="title"><strong>Figure 22.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>
379 In our opinion, this problem is not caused just because
380 red-black trees are order preserving while
381 collision-chaining hash tables are (generally) not - it
382 is more fundamental. Most of the standard's containers
383 order sequences in a well-defined manner that is
384 determined by their <span class="emphasis"><em>interface</em></span>:
385 calling <code class="function">insert</code> on a tree-based
386 container modifies its sequence in a predictable way, as
387 does calling <code class="function">push_back</code> on a list or
388 a vector. Conversely, collision-chaining hash tables,
389 probing hash tables, priority queues, and list-based
390 containers (which are very useful for "multimaps") are
391 self-organizing data structures; the effect of each
392 operation modifies their sequences in a manner that is
393 (practically) determined by their
394 <span class="emphasis"><em>implementation</em></span>.
395 </p><p>
396 Consequently, applying an algorithm to a sequence obtained from most
397 containers may or may not make sense, but applying it to a
398 sub-sequence of a self-organizing container does not.
399 </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>
400 Suppose <code class="varname">c</code> is some collision-chaining
401 hash-based container object, and one calls
402 </p><pre class="programlisting">c.find(3)</pre><p>
403 Then what composes the returned iterator?
404 </p><p>
405 In the graphic below, label A shows the simplest (and
406 most efficient) implementation of a collision-chaining
407 hash table. The little box marked
408 <code class="classname">point_iterator</code> shows an object
409 that contains a pointer to the element's node. Note that
410 this "iterator" has no way to move to the next element (
411 it cannot support
412 <code class="function">operator++</code>). Conversely, the little
413 box marked <code class="classname">iterator</code> stores both a
414 pointer to the element, as well as some other
415 information (the bucket number of the element). the
416 second iterator, then, is "heavier" than the first one-
417 it requires more time and space. If we were to use a
418 different container to cross-reference into this
419 hash-table using these iterators - it would take much
420 more space. As noted above, nothing much can be done by
421 incrementing these iterators, so why is this extra
422 information needed?
423 </p><p>
424 Alternatively, one might create a collision-chaining hash-table
425 where the lists might be linked, forming a monolithic total-element
426 list, as in the graphic below, label B. Here the iterators are as
427 light as can be, but the hash-table's operations are more
428 complicated.
429 </p><div class="figure"><a id="idm270862605568"></a><p class="title"><strong>Figure 22.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>
430 It should be noted that containers based on collision-chaining
431 hash-tables are not the only ones with this type of behavior;
432 many other self-organizing data structures display it as well.
433 </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">
434 it = c.find(3);
435 c.erase(5);
436 </pre><p>
437 Following the call to <code class="classname">erase</code>, what is the
438 validity of <code class="classname">it</code>: can it be de-referenced?
439 can it be incremented?
440 </p><p>
441 The answer depends on the underlying data structure of the
442 container. The graphic below shows three cases: A1 and A2 show
443 a red-black tree; B1 and B2 show a probing hash-table; C1 and C2
444 show a collision-chaining hash table.
445 </p><div class="figure"><a id="idm270862596304"></a><p class="title"><strong>Figure 22.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>
446 Erasing 5 from A1 yields A2. Clearly, an iterator to 3 can
447 be de-referenced and incremented. The sequence of iterators
448 changed, but in a way that is well-defined by the interface.
449 </p></li><li class="listitem"><p>
450 Erasing 5 from B1 yields B2. Clearly, an iterator to 3 is
451 not valid at all - it cannot be de-referenced or
452 incremented; the order of iterators changed in a way that is
453 (practically) determined by the implementation and not by
454 the interface.
455 </p></li><li class="listitem"><p>
456 Erasing 5 from C1 yields C2. Here the situation is more
457 complicated. On the one hand, there is no problem in
458 de-referencing <code class="classname">it</code>. On the other hand,
459 the order of iterators changed in a way that is
460 (practically) determined by the implementation and not by
461 the interface.
462 </p></li></ol></div><p>
463 So in the standard library containers, it is not always possible
464 to express whether <code class="varname">it</code> is valid or not. This
465 is true also for <code class="function">insert</code>. Again, the
466 iterator concept seems overloaded.
467 </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>
468 </p><p>
469 The design of the functional overlay to the underlying data
470 structures differs slightly from some of the conventions used in
471 the C++ standard. A strict public interface of methods that
472 comprise only operations which depend on the class's internal
473 structure; other operations are best designed as external
474 functions. (See <a class="xref" href="policy_data_structures.html#biblio.meyers02both" title="Class Template, Member Template - or Both?">[biblio.meyers02both]</a>).With this
475 rubric, the standard associative containers lack some useful
476 methods, and provide other methods which would be better
477 removed.
478 </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>
479 Order-preserving standard associative containers provide the
480 method
481 </p><pre class="programlisting">
482 iterator
483 erase(iterator it)
484 </pre><p>
485 which takes an iterator, erases the corresponding
486 element, and returns an iterator to the following
487 element. Also standardd hash-based associative
488 containers provide this method. This seemingly
489 increasesgenericity between associative containers,
490 since it is possible to use
491 </p><pre class="programlisting">
492 typename C::iterator it = c.begin();
493 typename C::iterator e_it = c.end();
495 while(it != e_it)
496 it = pred(*it)? c.erase(it) : ++it;
497 </pre><p>
498 in order to erase from a container object <code class="varname">
499 c</code> all element which match a
500 predicate <code class="classname">pred</code>. However, in a
501 different sense this actually decreases genericity: an
502 integral implication of this method is that tree-based
503 associative containers' memory use is linear in the total
504 number of elements they store, while hash-based
505 containers' memory use is unbounded in the total number of
506 elements they store. Assume a hash-based container is
507 allowed to decrease its size when an element is
508 erased. Then the elements might be rehashed, which means
509 that there is no "next" element - it is simply
510 undefined. Consequently, it is possible to infer from the
511 fact that the standard library's hash-based containers
512 provide this method that they cannot downsize when
513 elements are erased. As a consequence, different code is
514 needed to manipulate different containers, assuming that
515 memory should be conserved. Therefor, this library's
516 non-order preserving associative containers omit this
517 method.
518 </p></li><li class="listitem"><p>
519 All associative containers include a conditional-erase method
520 </p><pre class="programlisting">
521 template&lt;
522 class Pred&gt;
523 size_type
524 erase_if
525 (Pred pred)
526 </pre><p>
527 which erases all elements matching a predicate. This is probably the
528 only way to ensure linear-time multiple-item erase which can
529 actually downsize a container.
530 </p></li><li class="listitem"><p>
531 The standard associative containers provide methods for
532 multiple-item erase of the form
533 </p><pre class="programlisting">
534 size_type
535 erase(It b, It e)
536 </pre><p>
537 erasing a range of elements given by a pair of
538 iterators. For tree-based or trie-based containers, this can
539 implemented more efficiently as a (small) sequence of split
540 and join operations. For other, unordered, containers, this
541 method isn't much better than an external loop. Moreover,
542 if <code class="varname">c</code> is a hash-based container,
543 then
544 </p><pre class="programlisting">
545 c.erase(c.find(2), c.find(5))
546 </pre><p>
547 is almost certain to do something
548 different than erasing all elements whose keys are between 2
549 and 5, and is likely to produce other undefined behavior.
550 </p></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.split"></a>
551 <code class="function">split</code> and <code class="function">join</code>
552 </h6></div></div></div><p>
553 It is well-known that tree-based and trie-based container
554 objects can be efficiently split or joined (See
555 <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>). Externally splitting or
556 joining trees is super-linear, and, furthermore, can throw
557 exceptions. Split and join methods, consequently, seem good
558 choices for tree-based container methods, especially, since as
559 noted just before, they are efficient replacements for erasing
560 sub-sequences.
561 </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.insert"></a>
562 <code class="function">insert</code>
563 </h6></div></div></div><p>
564 The standard associative containers provide methods of the form
565 </p><pre class="programlisting">
566 template&lt;class It&gt;
567 size_type
568 insert(It b, It e);
569 </pre><p>
570 for inserting a range of elements given by a pair of
571 iterators. At best, this can be implemented as an external loop,
572 or, even more efficiently, as a join operation (for the case of
573 tree-based or trie-based containers). Moreover, these methods seem
574 similar to constructors taking a range given by a pair of
575 iterators; the constructors, however, are transactional, whereas
576 the insert methods are not; this is possibly confusing.
577 </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.compare"></a>
578 <code class="function">operator==</code> and <code class="function">operator&lt;=</code>
579 </h6></div></div></div><p>
580 Associative containers are parametrized by policies allowing to
581 test key equivalence: a hash-based container can do this through
582 its equivalence functor, and a tree-based container can do this
583 through its comparison functor. In addition, some standard
584 associative containers have global function operators, like
585 <code class="function">operator==</code> and <code class="function">operator&lt;=</code>,
586 that allow comparing entire associative containers.
587 </p><p>
588 In our opinion, these functions are better left out. To begin
589 with, they do not significantly improve over an external
590 loop. More importantly, however, they are possibly misleading -
591 <code class="function">operator==</code>, for example, usually checks for
592 equivalence, or interchangeability, but the associative
593 container cannot check for values' equivalence, only keys'
594 equivalence; also, are two containers considered equivalent if
595 they store the same values in different order? this is an
596 arbitrary decision.
597 </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>
598 Priority queues are containers that allow efficiently inserting
599 values and accessing the maximal value (in the sense of the
600 container's comparison functor). Their interface
601 supports <code class="function">push</code>
602 and <code class="function">pop</code>. The standard
603 container <code class="classname">std::priorityqueue</code> indeed support
604 these methods, but little else. For algorithmic and
605 software-engineering purposes, other methods are needed:
606 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
607 Many graph algorithms (see
608 <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>) require increasing a
609 value in a priority queue (again, in the sense of the
610 container's comparison functor), or joining two
611 priority-queue objects.
612 </p></li><li class="listitem"><p>The return type of <code class="classname">priority_queue</code>'s
613 <code class="function">push</code> method is a point-type iterator, which can
614 be used for modifying or erasing arbitrary values. For
615 example:</p><pre class="programlisting">
616 priority_queue&lt;int&gt; p;
617 priority_queue&lt;int&gt;::point_iterator it = p.push(3);
618 p.modify(it, 4);
619 </pre><p>These types of cross-referencing operations are necessary
620 for making priority queues useful for different applications,
621 especially graph applications.</p></li><li class="listitem"><p>
622 It is sometimes necessary to erase an arbitrary value in a
623 priority queue. For example, consider
624 the <code class="function">select</code> function for monitoring
625 file descriptors:
626 </p><pre class="programlisting">
628 select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds,
629 struct timeval *timeout);
630 </pre><p>
631 then, as the select documentation states:
632 </p><p>
633 <span class="quote"><span class="quote">
634 The nfds argument specifies the range of file
635 descriptors to be tested. The select() function tests file
636 descriptors in the range of 0 to nfds-1.</span></span>
637 </p><p>
638 It stands to reason, therefore, that we might wish to
639 maintain a minimal value for <code class="varname">nfds</code>, and
640 priority queues immediately come to mind. Note, though, that
641 when a socket is closed, the minimal file description might
642 change; in the absence of an efficient means to erase an
643 arbitrary value from a priority queue, we might as well
644 avoid its use altogether.
645 </p><p>
646 The standard containers typically support iterators. It is
647 somewhat unusual
648 for <code class="classname">std::priority_queue</code> to omit them
649 (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
650 ask why do priority queues need to support iterators, since
651 they are self-organizing containers with a different purpose
652 than abstracting sequences. There are several reasons:
653 </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p>
654 Iterators (even in self-organizing containers) are
655 useful for many purposes: cross-referencing
656 containers, serialization, and debugging code that uses
657 these containers.
658 </p></li><li class="listitem"><p>
659 The standard library's hash-based containers support
660 iterators, even though they too are self-organizing
661 containers with a different purpose than abstracting
662 sequences.
663 </p></li><li class="listitem"><p>
664 In standard-library-like containers, it is natural to specify the
665 interface of operations for modifying a value or erasing
666 a value (discussed previously) in terms of a iterators.
667 It should be noted that the standard
668 containers also use iterators for accessing and
669 manipulating a specific value. In hash-based
670 containers, one checks the existence of a key by
671 comparing the iterator returned by <code class="function">find</code> to the
672 iterator returned by <code class="function">end</code>, and not by comparing a
673 pointer returned by <code class="function">find</code> to <span class="type">NULL</span>.
674 </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>
675 There are three main implementations of priority queues: the
676 first employs a binary heap, typically one which uses a
677 sequence; the second uses a tree (or forest of trees), which is
678 typically less structured than an associative container's tree;
679 the third simply uses an associative container. These are
680 shown in the figure below with labels A1 and A2, B, and C.
681 </p><div class="figure"><a id="idm270862528720"></a><p class="title"><strong>Figure 22.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>
682 No single implementation can completely replace any of the
683 others. Some have better <code class="function">push</code>
684 and <code class="function">pop</code> amortized performance, some have
685 better bounded (worst case) response time than others, some
686 optimize a single method at the expense of others, etc. In
687 general the "best" implementation is dictated by the specific
688 problem.
689 </p><p>
690 As with associative containers, the more implementations
691 co-exist, the more necessary a traits mechanism is for handling
692 generic containers safely and efficiently. This is especially
693 important for priority queues, since the invalidation guarantees
694 of one of the most useful data structures - binary heaps - is
695 markedly different than those of most of the others.
696 </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>
697 Binary heaps are one of the most useful underlying
698 data structures for priority queues. They are very efficient in
699 terms of memory (since they don't require per-value structure
700 metadata), and have the best amortized <code class="function">push</code> and
701 <code class="function">pop</code> performance for primitive types like
702 <span class="type">int</span>.
703 </p><p>
704 The standard library's <code class="classname">priority_queue</code>
705 implements this data structure as an adapter over a sequence,
706 typically
707 <code class="classname">std::vector</code>
708 or <code class="classname">std::deque</code>, which correspond to labels
709 A1 and A2 respectively in the graphic above.
710 </p><p>
711 This is indeed an elegant example of the adapter concept and
712 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
713 several reasons why a binary-heap priority queue
714 may be better implemented as a container instead of a
715 sequence adapter:
716 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
717 <code class="classname">std::priority_queue</code> cannot erase values
718 from its adapted sequence (irrespective of the sequence
719 type). This means that the memory use of
720 an <code class="classname">std::priority_queue</code> object is always
721 proportional to the maximal number of values it ever contained,
722 and not to the number of values that it currently
723 contains. (See <code class="filename">performance/priority_queue_text_pop_mem_usage.cc</code>.)
724 This implementation of binary heaps acts very differently than
725 other underlying data structures (See also pairing heaps).
726 </p></li><li class="listitem"><p>
727 Some combinations of adapted sequences and value types
728 are very inefficient or just don't make sense. If one uses
729 <code class="classname">std::priority_queue&lt;std::vector&lt;std::string&gt;
730 &gt; &gt;</code>, for example, then not only will each
731 operation perform a logarithmic number of
732 <code class="classname">std::string</code> assignments, but, furthermore, any
733 operation (including <code class="function">pop</code>) can render the container
734 useless due to exceptions. Conversely, if one uses
735 <code class="classname">std::priority_queue&lt;std::deque&lt;int&gt; &gt;
736 &gt;</code>, then each operation uses incurs a logarithmic
737 number of indirect accesses (through pointers) unnecessarily.
738 It might be better to let the container make a conservative
739 deduction whether to use the structure in the graphic above, labels A1 or A2.
740 </p></li><li class="listitem"><p>
741 There does not seem to be a systematic way to determine
742 what exactly can be done with the priority queue.
743 </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p>
744 If <code class="classname">p</code> is a priority queue adapting an
745 <code class="classname">std::vector</code>, then it is possible to iterate over
746 all values by using <code class="function">&amp;p.top()</code> and
747 <code class="function">&amp;p.top() + p.size()</code>, but this will not work
748 if <code class="varname">p</code> is adapting an <code class="classname">std::deque</code>; in any
749 case, one cannot use <code class="classname">p.begin()</code> and
750 <code class="classname">p.end()</code>. If a different sequence is adapted, it
751 is even more difficult to determine what can be
752 done.
753 </p></li><li class="listitem"><p>
754 If <code class="varname">p</code> is a priority queue adapting an
755 <code class="classname">std::deque</code>, then the reference return by
756 </p><pre class="programlisting">
757 p.top()
758 </pre><p>
759 will remain valid until it is popped,
760 but if <code class="varname">p</code> adapts an <code class="classname">std::vector</code>, the
761 next <code class="function">push</code> will invalidate it. If a different
762 sequence is adapted, it is even more difficult to
763 determine what can be done.
764 </p></li></ol></div></li><li class="listitem"><p>
765 Sequence-based binary heaps can still implement
766 linear-time <code class="function">erase</code> and <code class="function">modify</code> operations.
767 This means that if one needs to erase a small
768 (say logarithmic) number of values, then one might still
769 choose this underlying data structure. Using
770 <code class="classname">std::priority_queue</code>, however, this will generally
771 change the order of growth of the entire sequence of
772 operations.
773 </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>
774 <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1075.pdf" target="_top">
775 STL Exception Handling Contract
776 </a>
777 </em>. </span><span class="date">1997. </span><span class="author"><span class="firstname">
778 Dave
779 </span> <span class="surname">
780 Abrahams
781 </span>. </span><span class="publisher"><span class="publishername">
782 ISO SC22/WG21
783 . </span></span></p></div><div class="biblioentry"><a id="biblio.alexandrescu01modern"></a><p>[biblio.alexandrescu01modern] <span class="title"><em>
784 Modern C++ Design: Generic Programming and Design Patterns Applied
785 </em>. </span><span class="date">
786 2001
787 . </span><span class="author"><span class="firstname">
788 Andrei
789 </span> <span class="surname">
790 Alexandrescu
791 </span>. </span><span class="publisher"><span class="publishername">
792 Addison-Wesley Publishing Company
793 . </span></span></p></div><div class="biblioentry"><a id="biblio.andrew04mtf"></a><p>[biblio.andrew04mtf] <span class="title"><em>
794 MTF, Bit, and COMB: A Guide to Deterministic and Randomized
795 Algorithms for the List Update Problem
796 </em>. </span><span class="authorgroup"><span class="firstname">
798 </span> <span class="surname">
799 Andrew
800 </span> and <span class="firstname">
802 </span> <span class="surname">
803 Gleich
804 </span>. </span></p></div><div class="biblioentry"><a id="biblio.austern00noset"></a><p>[biblio.austern00noset] <span class="title"><em>
805 Why You Shouldn't Use set - and What You Should Use Instead
806 </em>. </span><span class="date">
807 April, 2000
808 . </span><span class="author"><span class="firstname">
809 Matthew
810 </span> <span class="surname">
811 Austern
812 </span>. </span><span class="publisher"><span class="publishername">
813 C++ Report
814 . </span></span></p></div><div class="biblioentry"><a id="biblio.austern01htprop"></a><p>[biblio.austern01htprop] <span class="title"><em>
815 <a class="link" href="http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2001/n1326.html" target="_top">
816 A Proposal to Add Hashtables to the Standard Library
817 </a>
818 </em>. </span><span class="date">
819 2001
820 . </span><span class="author"><span class="firstname">
821 Matthew
822 </span> <span class="surname">
823 Austern
824 </span>. </span><span class="publisher"><span class="publishername">
825 ISO SC22/WG21
826 . </span></span></p></div><div class="biblioentry"><a id="biblio.austern98segmentedit"></a><p>[biblio.austern98segmentedit] <span class="title"><em>
827 Segmented iterators and hierarchical algorithms
828 </em>. </span><span class="date">
829 April, 1998
830 . </span><span class="author"><span class="firstname">
831 Matthew
832 </span> <span class="surname">
833 Austern
834 </span>. </span><span class="publisher"><span class="publishername">
835 Generic Programming
836 . </span></span></p></div><div class="biblioentry"><a id="biblio.dawestimer"></a><p>[biblio.dawestimer] <span class="title"><em>
837 <a class="link" href="http://www.boost.org/doc/libs/release/libs/timer/" target="_top">
838 Boost Timer Library
839 </a>
840 </em>. </span><span class="author"><span class="firstname">
841 Beeman
842 </span> <span class="surname">
843 Dawes
844 </span>. </span><span class="publisher"><span class="publishername">
845 Boost
846 . </span></span></p></div><div class="biblioentry"><a id="biblio.clearypool"></a><p>[biblio.clearypool] <span class="title"><em>
847 <a class="link" href="http://www.boost.org/doc/libs/release/libs/pool/" target="_top">
848 Boost Pool Library
849 </a>
850 </em>. </span><span class="author"><span class="firstname">
851 Stephen
852 </span> <span class="surname">
853 Cleary
854 </span>. </span><span class="publisher"><span class="publishername">
855 Boost
856 . </span></span></p></div><div class="biblioentry"><a id="biblio.maddocktraits"></a><p>[biblio.maddocktraits] <span class="title"><em>
857 <a class="link" href="http://www.boost.org/doc/libs/release/libs/type_traits/" target="_top">
858 Boost Type Traits Library
859 </a>
860 </em>. </span><span class="authorgroup"><span class="firstname">
861 Maddock
862 </span> <span class="surname">
863 John
864 </span> and <span class="firstname">
865 Stephen
866 </span> <span class="surname">
867 Cleary
868 </span>. </span><span class="publisher"><span class="publishername">
869 Boost
870 . </span></span></p></div><div class="biblioentry"><a id="biblio.brodal96priority"></a><p>[biblio.brodal96priority] <span class="title"><em>
871 <a class="link" href="https://dl.acm.org/citation.cfm?id=313883" target="_top">
872 Worst-case efficient priority queues
873 </a>
874 </em>. </span><span class="author"><span class="firstname">
875 Gerth
876 </span> <span class="surname">
877 Stolting Brodal
878 </span>. </span></p></div><div class="biblioentry"><a id="biblio.bulkamayheweff"></a><p>[biblio.bulkamayheweff] <span class="title"><em>
879 Efficient C++ Programming Techniques
880 </em>. </span><span class="date">
881 1997
882 . </span><span class="authorgroup"><span class="firstname">
884 </span> <span class="surname">
885 Bulka
886 </span> and <span class="firstname">
888 </span> <span class="surname">
889 Mayhew
890 </span>. </span><span class="publisher"><span class="publishername">
891 Addison-Wesley Publishing Company
892 . </span></span></p></div><div class="biblioentry"><a id="biblio.clrs2001"></a><p>[biblio.clrs2001] <span class="title"><em>
893 Introduction to Algorithms, 2nd edition
894 </em>. </span><span class="date">
895 2001
896 . </span><span class="authorgroup"><span class="firstname">
897 T. H.
898 </span> <span class="surname">
899 Cormen
900 </span>, <span class="firstname">
901 C. E.
902 </span> <span class="surname">
903 Leiserson
904 </span>, <span class="firstname">
905 R. L.
906 </span> <span class="surname">
907 Rivest
908 </span>, and <span class="firstname">
910 </span> <span class="surname">
911 Stein
912 </span>. </span><span class="publisher"><span class="publishername">
913 MIT Press
914 . </span></span></p></div><div class="biblioentry"><a id="biblio.dubhashi98neg"></a><p>[biblio.dubhashi98neg] <span class="title"><em>
915 Balls and bins: A study in negative dependence
916 </em>. </span><span class="date">
917 1998
918 . </span><span class="authorgroup"><span class="firstname">
920 </span> <span class="surname">
921 Dubashi
922 </span> and <span class="firstname">
924 </span> <span class="surname">
925 Ranjan
926 </span>. </span><span class="publisher"><span class="publishername">
927 Random Structures and Algorithms 13
928 . </span></span></p></div><div class="biblioentry"><a id="biblio.fagin79extendible"></a><p>[biblio.fagin79extendible] <span class="title"><em>
929 Extendible hashing - a fast access method for dynamic files
930 </em>. </span><span class="date">
931 1979
932 . </span><span class="authorgroup"><span class="firstname">
934 </span> <span class="surname">
935 Fagin
936 </span>, <span class="firstname">
938 </span> <span class="surname">
939 Nievergelt
940 </span>, <span class="firstname">
942 </span> <span class="surname">
943 Pippenger
944 </span>, and <span class="firstname">
945 H. R.
946 </span> <span class="surname">
947 Strong
948 </span>. </span><span class="publisher"><span class="publishername">
949 ACM Trans. Database Syst. 4
950 . </span></span></p></div><div class="biblioentry"><a id="biblio.filliatre2000ptset"></a><p>[biblio.filliatre2000ptset] <span class="title"><em>
951 <a class="link" href="http://cristal.inria.fr/~frisch/icfp06_contest/advtr/applyOmatic/ptset.ml" target="_top">
952 Ptset: Sets of integers implemented as Patricia trees
953 </a>
954 </em>. </span><span class="date">
955 2000
956 . </span><span class="author"><span class="firstname">
957 Jean-Christophe
958 </span> <span class="surname">
959 Filliatre
960 </span>. </span></p></div><div class="biblioentry"><a id="biblio.fredman86pairing"></a><p>[biblio.fredman86pairing] <span class="title"><em>
961 <a class="link" href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf" target="_top">
962 The pairing heap: a new form of self-adjusting heap
963 </a>
964 </em>. </span><span class="date">
965 1986
966 . </span><span class="authorgroup"><span class="firstname">
967 M. L.
968 </span> <span class="surname">
969 Fredman
970 </span>, <span class="firstname">
972 </span> <span class="surname">
973 Sedgewick
974 </span>, <span class="firstname">
975 D. D.
976 </span> <span class="surname">
977 Sleator
978 </span>, and <span class="firstname">
979 R. E.
980 </span> <span class="surname">
981 Tarjan
982 </span>. </span></p></div><div class="biblioentry"><a id="biblio.gof"></a><p>[biblio.gof] <span class="title"><em>
983 Design Patterns - Elements of Reusable Object-Oriented Software
984 </em>. </span><span class="date">
985 1995
986 . </span><span class="authorgroup"><span class="firstname">
988 </span> <span class="surname">
989 Gamma
990 </span>, <span class="firstname">
992 </span> <span class="surname">
993 Helm
994 </span>, <span class="firstname">
996 </span> <span class="surname">
997 Johnson
998 </span>, and <span class="firstname">
1000 </span> <span class="surname">
1001 Vlissides
1002 </span>. </span><span class="publisher"><span class="publishername">
1003 Addison-Wesley Publishing Company
1004 . </span></span></p></div><div class="biblioentry"><a id="biblio.garg86order"></a><p>[biblio.garg86order] <span class="title"><em>
1005 Order-preserving key transformations
1006 </em>. </span><span class="date">
1007 1986
1008 . </span><span class="authorgroup"><span class="firstname">
1009 A. K.
1010 </span> <span class="surname">
1011 Garg
1012 </span> and <span class="firstname">
1013 C. C.
1014 </span> <span class="surname">
1015 Gotlieb
1016 </span>. </span><span class="publisher"><span class="publishername">
1017 Trans. Database Syst. 11
1018 . </span></span></p></div><div class="biblioentry"><a id="biblio.hyslop02making"></a><p>[biblio.hyslop02making] <span class="title"><em>
1019 Making a real hash of things
1020 </em>. </span><span class="date">
1021 May 2002
1022 . </span><span class="authorgroup"><span class="firstname">
1024 </span> <span class="surname">
1025 Hyslop
1026 </span> and <span class="firstname">
1027 Herb
1028 </span> <span class="surname">
1029 Sutter
1030 </span>. </span><span class="publisher"><span class="publishername">
1031 C++ Report
1032 . </span></span></p></div><div class="biblioentry"><a id="biblio.jossutis01stl"></a><p>[biblio.jossutis01stl] <span class="title"><em>
1033 The C++ Standard Library - A Tutorial and Reference
1034 </em>. </span><span class="date">
1035 2001
1036 . </span><span class="author"><span class="firstname">
1037 N. M.
1038 </span> <span class="surname">
1039 Jossutis
1040 </span>. </span><span class="publisher"><span class="publishername">
1041 Addison-Wesley Publishing Company
1042 . </span></span></p></div><div class="biblioentry"><a id="biblio.kt99fat_heaps"></a><p>[biblio.kt99fat_heaps] <span class="title"><em>
1043 <a class="link" href="http://www.cs.princeton.edu/research/techreps/TR-597-99" target="_top">
1044 New Heap Data Structures
1045 </a>
1046 </em>. </span><span class="date">
1047 1999
1048 . </span><span class="authorgroup"><span class="firstname">
1049 Haim
1050 </span> <span class="surname">
1051 Kaplan
1052 </span> and <span class="firstname">
1053 Robert E.
1054 </span> <span class="surname">
1055 Tarjan
1056 </span>. </span></p></div><div class="biblioentry"><a id="biblio.kleft00sets"></a><p>[biblio.kleft00sets] <span class="title"><em>
1057 Are Set Iterators Mutable or Immutable?
1058 </em>. </span><span class="date">
1059 October 2000
1060 . </span><span class="authorgroup"><span class="firstname">
1061 Angelika
1062 </span> <span class="surname">
1063 Langer
1064 </span> and <span class="firstname">
1065 Klaus
1066 </span> <span class="surname">
1067 Kleft
1068 </span>. </span><span class="publisher"><span class="publishername">
1069 C/C++ Users Jornal
1070 . </span></span></p></div><div class="biblioentry"><a id="biblio.knuth98sorting"></a><p>[biblio.knuth98sorting] <span class="title"><em>
1071 The Art of Computer Programming - Sorting and Searching
1072 </em>. </span><span class="date">
1073 1998
1074 . </span><span class="author"><span class="firstname">
1075 D. E.
1076 </span> <span class="surname">
1077 Knuth
1078 </span>. </span><span class="publisher"><span class="publishername">
1079 Addison-Wesley Publishing Company
1080 . </span></span></p></div><div class="biblioentry"><a id="biblio.liskov98data"></a><p>[biblio.liskov98data] <span class="title"><em>
1081 Data abstraction and hierarchy
1082 </em>. </span><span class="date">
1083 May 1998
1084 . </span><span class="author"><span class="firstname">
1086 </span> <span class="surname">
1087 Liskov
1088 </span>. </span><span class="publisher"><span class="publishername">
1089 SIGPLAN Notices 23
1090 . </span></span></p></div><div class="biblioentry"><a id="biblio.litwin80lh"></a><p>[biblio.litwin80lh] <span class="title"><em>
1091 Linear hashing: A new tool for file and table addressing
1092 </em>. </span><span class="date">
1093 June 1980
1094 . </span><span class="author"><span class="firstname">
1096 </span> <span class="surname">
1097 Litwin
1098 </span>. </span><span class="publisher"><span class="publishername">
1099 Proceedings of International Conference on Very Large Data Bases
1100 . </span></span></p></div><div class="biblioentry"><a id="biblio.maverik_lowerbounds"></a><p>[biblio.maverik_lowerbounds] <span class="title"><em>
1101 <a class="link" href="http://magic.aladdin.cs.cmu.edu/2005/08/01/deamortization-part-2-binomial-heaps/" target="_top">
1102 Deamortization - Part 2: Binomial Heaps
1103 </a>
1104 </em>. </span><span class="date">
1105 2005
1106 . </span><span class="author"><span class="firstname">
1107 Maverik
1108 </span> <span class="surname">
1110 </span>. </span></p></div><div class="biblioentry"><a id="biblio.meyers96more"></a><p>[biblio.meyers96more] <span class="title"><em>
1111 More Effective C++: 35 New Ways to Improve Your Programs and Designs
1112 </em>. </span><span class="date">
1113 1996
1114 . </span><span class="author"><span class="firstname">
1115 Scott
1116 </span> <span class="surname">
1117 Meyers
1118 </span>. </span><span class="publisher"><span class="publishername">
1119 Addison-Wesley Publishing Company
1120 . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers00nonmember"></a><p>[biblio.meyers00nonmember] <span class="title"><em>
1121 How Non-Member Functions Improve Encapsulation
1122 </em>. </span><span class="date">
1123 2000
1124 . </span><span class="author"><span class="firstname">
1125 Scott
1126 </span> <span class="surname">
1127 Meyers
1128 </span>. </span><span class="publisher"><span class="publishername">
1129 C/C++ Users Journal
1130 . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers01stl"></a><p>[biblio.meyers01stl] <span class="title"><em>
1131 Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library
1132 </em>. </span><span class="date">
1133 2001
1134 . </span><span class="author"><span class="firstname">
1135 Scott
1136 </span> <span class="surname">
1137 Meyers
1138 </span>. </span><span class="publisher"><span class="publishername">
1139 Addison-Wesley Publishing Company
1140 . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers02both"></a><p>[biblio.meyers02both] <span class="title"><em>
1141 Class Template, Member Template - or Both?
1142 </em>. </span><span class="date">
1143 2003
1144 . </span><span class="author"><span class="firstname">
1145 Scott
1146 </span> <span class="surname">
1147 Meyers
1148 </span>. </span><span class="publisher"><span class="publishername">
1149 C/C++ Users Journal
1150 . </span></span></p></div><div class="biblioentry"><a id="biblio.motwani95random"></a><p>[biblio.motwani95random] <span class="title"><em>
1151 Randomized Algorithms
1152 </em>. </span><span class="date">
1153 2003
1154 . </span><span class="authorgroup"><span class="firstname">
1156 </span> <span class="surname">
1157 Motwani
1158 </span> and <span class="firstname">
1160 </span> <span class="surname">
1161 Raghavan
1162 </span>. </span><span class="publisher"><span class="publishername">
1163 Cambridge University Press
1164 . </span></span></p></div><div class="biblioentry"><a id="biblio.mscom"></a><p>[biblio.mscom] <span class="title"><em>
1165 <a class="link" href="https://www.microsoft.com/com/" target="_top">
1166 COM: Component Model Object Technologies
1167 </a>
1168 </em>. </span><span class="publisher"><span class="publishername">
1169 Microsoft
1170 . </span></span></p></div><div class="biblioentry"><a id="biblio.musser95rationale"></a><p>[biblio.musser95rationale] <span class="title"><em>
1171 Rationale for Adding Hash Tables to the C++ Standard Template Library
1172 </em>. </span><span class="date">
1173 1995
1174 . </span><span class="author"><span class="firstname">
1175 David R.
1176 </span> <span class="surname">
1177 Musser
1178 </span>. </span></p></div><div class="biblioentry"><a id="biblio.musser96stltutorial"></a><p>[biblio.musser96stltutorial] <span class="title"><em>
1179 STL Tutorial and Reference Guide
1180 </em>. </span><span class="date">
1181 1996
1182 . </span><span class="authorgroup"><span class="firstname">
1183 David R.
1184 </span> <span class="surname">
1185 Musser
1186 </span> and <span class="firstname">
1188 </span> <span class="surname">
1189 Saini
1190 </span>. </span><span class="publisher"><span class="publishername">
1191 Addison-Wesley Publishing Company
1192 . </span></span></p></div><div class="biblioentry"><a id="biblio.nelson96stlpq"></a><p>[biblio.nelson96stlpq] <span class="title"><em>
1193 <a class="link" href="http://marknelson.us/1996/01/01/priority-queues/" target="_top">Priority Queues and the STL
1194 </a>
1195 </em>. </span><span class="date">
1196 January 1996
1197 . </span><span class="author"><span class="firstname">
1198 Mark
1199 </span> <span class="surname">
1200 Nelson
1201 </span>. </span><span class="publisher"><span class="publishername">
1202 Dr. Dobbs Journal
1203 . </span></span></p></div><div class="biblioentry"><a id="biblio.okasaki98mereable"></a><p>[biblio.okasaki98mereable] <span class="title"><em>
1204 Fast mergeable integer maps
1205 </em>. </span><span class="date">
1206 September 1998
1207 . </span><span class="authorgroup"><span class="firstname">
1209 </span> <span class="surname">
1210 Okasaki
1211 </span> and <span class="firstname">
1213 </span> <span class="surname">
1214 Gill
1215 </span>. </span><span class="publisher"><span class="publishername">
1216 In Workshop on ML
1217 . </span></span></p></div><div class="biblioentry"><a id="biblio.sgi_stl"></a><p>[biblio.sgi_stl] <span class="title"><em>
1218 <a class="link" href="http://www.sgi.com/tech/stl/" target="_top">
1219 Standard Template Library Programmer's Guide
1220 </a>
1221 </em>. </span><span class="author"><span class="firstname">
1222 Matt
1223 </span> <span class="surname">
1224 Austern
1225 </span>. </span><span class="publisher"><span class="publishername">
1227 . </span></span></p></div><div class="biblioentry"><a id="biblio.select_man"></a><p>[biblio.select_man] <span class="title"><em>
1228 <a class="link" href="http://pubs.opengroup.org/onlinepubs/9699919799/functions/select.html" target="_top">
1229 select
1230 </a>
1231 </em>. </span></p></div><div class="biblioentry"><a id="biblio.sleator84amortized"></a><p>[biblio.sleator84amortized] <span class="title"><em>
1232 Amortized Efficiency of List Update Problems
1233 </em>. </span><span class="date">
1234 1984
1235 . </span><span class="authorgroup"><span class="firstname">
1236 D. D.
1237 </span> <span class="surname">
1238 Sleator
1239 </span> and <span class="firstname">
1240 R. E.
1241 </span> <span class="surname">
1242 Tarjan
1243 </span>. </span><span class="publisher"><span class="publishername">
1244 ACM Symposium on Theory of Computing
1245 . </span></span></p></div><div class="biblioentry"><a id="biblio.sleator85self"></a><p>[biblio.sleator85self] <span class="title"><em>
1246 Self-Adjusting Binary Search Trees
1247 </em>. </span><span class="date">
1248 1985
1249 . </span><span class="authorgroup"><span class="firstname">
1250 D. D.
1251 </span> <span class="surname">
1252 Sleator
1253 </span> and <span class="firstname">
1254 R. E.
1255 </span> <span class="surname">
1256 Tarjan
1257 </span>. </span><span class="publisher"><span class="publishername">
1258 ACM Symposium on Theory of Computing
1259 . </span></span></p></div><div class="biblioentry"><a id="biblio.stepanov94standard"></a><p>[biblio.stepanov94standard] <span class="title"><em>
1260 The Standard Template Library
1261 </em>. </span><span class="date">
1262 1984
1263 . </span><span class="authorgroup"><span class="firstname">
1264 A. A.
1265 </span> <span class="surname">
1266 Stepanov
1267 </span> and <span class="firstname">
1269 </span> <span class="surname">
1271 </span>. </span></p></div><div class="biblioentry"><a id="biblio.stroustrup97cpp"></a><p>[biblio.stroustrup97cpp] <span class="title"><em>
1272 The C++ Programming Langugage
1273 </em>. </span><span class="date">
1274 1997
1275 . </span><span class="author"><span class="firstname">
1276 Bjarne
1277 </span> <span class="surname">
1278 Stroustrup
1279 </span>. </span><span class="publisher"><span class="publishername">
1280 Addison-Wesley Publishing Company
1281 . </span></span></p></div><div class="biblioentry"><a id="biblio.vandevoorde2002cpptemplates"></a><p>[biblio.vandevoorde2002cpptemplates] <span class="title"><em>
1282 C++ Templates: The Complete Guide
1283 </em>. </span><span class="date">
1284 2002
1285 . </span><span class="authorgroup"><span class="firstname">
1287 </span> <span class="surname">
1288 Vandevoorde
1289 </span> and <span class="firstname">
1290 N. M.
1291 </span> <span class="surname">
1292 Josuttis
1293 </span>. </span><span class="publisher"><span class="publishername">
1294 Addison-Wesley Publishing Company
1295 . </span></span></p></div><div class="biblioentry"><a id="biblio.wickland96thirty"></a><p>[biblio.wickland96thirty] <span class="title"><em>
1296 <a class="link" href="http://myweb.wvnet.edu/~gsa00121/books/amongdead30.zip" target="_top">
1297 Thirty Years Among the Dead
1298 </a>
1299 </em>. </span><span class="date">
1300 1996
1301 . </span><span class="author"><span class="firstname">
1302 C. A.
1303 </span> <span class="surname">
1304 Wickland
1305 </span>. </span><span class="publisher"><span class="publishername">
1306 National Psychological Institute
1307 . </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>