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">
3 <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.76.1" /><meta name="keywords" content=" 	ISO C++ , 	policy , 	container , 	data , 	structure , 	associated , 	tree , 	trie , 	hash , 	metaprogramming " /><meta name="keywords" content=" ISO C++ , library " /><meta name="keywords" content=" ISO C++ , runtime , library " /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="extensions.html" title="Part III. Extensions" /><link rel="prev" href="bk01pt03ch21s02.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="bk01pt03ch21s02.html">Prev</a> </td><th width="60%" align="center">Part III.
6 </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" title="Chapter 22. Policy-Based Data Structures"><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><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">
7 Configuring via Template Parameters
8 </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.traits">
9 Querying Container Attributes
10 </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.point_range_iteration">
11 Point and Range Iteration
12 </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">
13 Distinguishing Between Maps and Sets
14 </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">
15 Text <code class="function">find</code>
16 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_find">
17 Integer <code class="function">find</code>
18 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_find">
19 Integer Subscript <code class="function">find</code>
20 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_insert">
21 Integer Subscript <code class="function">insert</code>
22 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.zlob_int_find">
23 Integer <code class="function">find</code> with Skewed-Distribution
24 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.erase_mem">
26 </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">
27 Text <code class="function">insert</code>
28 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_find">
29 Text <code class="function">find</code>
30 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_lor_find">
31 Text <code class="function">find</code> with Locality-of-Reference
32 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.split_join">
33 <code class="function">split</code> and <code class="function">join</code>
34 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.order_statistics">
36 </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">
37 Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios
38 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_find_large">
39 Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios
40 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_small">
41 Text <code class="function">insert</code> with Small
42 Secondary-to-Primary Key Ratios
43 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_large">
44 Text <code class="function">insert</code> with Small
45 Secondary-to-Primary Key Ratios
46 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_small">
47 Text <code class="function">insert</code> with Small
48 Secondary-to-Primary Key Ratios Memory Use
49 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_large">
50 Text <code class="function">insert</code> with Small
51 Secondary-to-Primary Key Ratios Memory Use
52 </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">
53 Text <code class="function">push</code>
54 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_push_pop">
55 Text <code class="function">push</code> and <code class="function">pop</code>
56 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push">
57 Integer <code class="function">push</code>
58 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push_pop">
59 Integer <code class="function">push</code>
60 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_pop">
61 Text <code class="function">pop</code> Memory Use
62 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_join">
63 Text <code class="function">join</code>
64 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_up">
65 Text <code class="function">modify</code> Up
66 </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_down">
67 Text <code class="function">modify</code> Down
68 </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" title="Intro"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="pbds.intro"></a>Intro</h2></div></div></div><p>
69 This is a library of policy-based elementary data structures:
70 associative containers and priority queues. It is designed for
71 high-performance, flexibility, semantic safety, and conformance to
72 the corresponding containers in <code class="literal">std</code> and
73 <code class="literal">std::tr1</code> (except for some points where it differs
76 </p><div class="section" title="Performance Issues"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.intro.issues"></a>Performance Issues</h3></div></div></div><p>
78 An attempt is made to categorize the wide variety of possible
79 container designs in terms of performance-impacting factors. These
80 performance factors are translated into design policies and
81 incorporated into container design.
83 There is tension between unravelling factors into a coherent set of
84 policies. Every attempt is made to make a minimal set of
85 factors. However, in many cases multiple factors make for long
86 template names. Every attempt is made to alias and use typedefs in
87 the source files, but the generated names for external symbols can
88 be large for binary files or debuggers.
90 In many cases, the longer names allow capabilities and behaviours
91 controlled by macros to also be unamibiguously emitted as distinct
94 Specific issues found while unraveling performance factors in the
95 design of associative containers and priority queues follow.
96 </p><div class="section" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.associative"></a>Associative</h4></div></div></div><p>
97 Associative containers depend on their composite policies to a very
98 large extent. Implicitly hard-wiring policies can hamper their
99 performance and limit their functionality. An efficient hash-based
100 container, for example, requires policies for testing key
101 equivalence, hashing keys, translating hash values into positions
102 within the hash table, and determining when and how to resize the
103 table internally. A tree-based container can efficiently support
104 order statistics, i.e. the ability to query what is the order of
105 each key within the sequence of keys in the container, but only if
106 the container is supplied with a policy to internally update
107 meta-data. There are many other such examples.
109 Ideally, all associative containers would share the same
110 interface. Unfortunately, underlying data structures and mapping
111 semantics differentiate between different containers. For example,
112 suppose one writes a generic function manipulating an associative
114 </p><pre class="programlisting">
115 template<typename Cntnr>
117 some_op_sequence(Cntnr& r_cnt)
122 Given this, then what can one assume about the instantiating
123 container? The answer varies according to its underlying data
124 structure. If the underlying data structure of
125 <code class="literal">Cntnr</code> is based on a tree or trie, then the order
126 of elements is well defined; otherwise, it is not, in general. If
127 the underlying data structure of <code class="literal">Cntnr</code> is based
128 on a collision-chaining hash table, then modifying
129 r_<code class="literal">Cntnr</code> will not invalidate its iterators' order;
130 if the underlying data structure is a probing hash table, then this
131 is not the case. If the underlying data structure is based on a tree
132 or trie, then a reference to the container can efficiently be split;
133 otherwise, it cannot, in general. If the underlying data structure
134 is a red-black tree, then splitting a reference to the container is
135 exception-free; if it is an ordered-vector tree, exceptions can be
137 </p></div><div class="section" title="Priority Que"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.priority_queue"></a>Priority Que</h4></div></div></div><p>
138 Priority queues are useful when one needs to efficiently access a
139 minimum (or maximum) value as the set of values changes.
141 Most useful data structures for priority queues have a relatively
142 simple structure, as they are geared toward relatively simple
143 requirements. Unfortunately, these structures do not support access
144 to an arbitrary value, which turns out to be necessary in many
145 algorithms. Say, decreasing an arbitrary value in a graph
146 algorithm. Therefore, some extra mechanism is necessary and must be
147 invented for accessing arbitrary values. There are at least two
148 alternatives: embedding an associative container in a priority
149 queue, or allowing cross-referencing through iterators. The first
150 solution adds significant overhead; the second solution requires a
151 precise definition of iterator invalidation. Which is the next
154 Priority queues, like hash-based containers, store values in an
155 order that is meaningless and undefined externally. For example, a
156 <code class="code">push</code> operation can internally reorganize the
157 values. Because of this characteristic, describing a priority
158 queues' iterator is difficult: on one hand, the values to which
159 iterators point can remain valid, but on the other, the logical
160 order of iterators can change unpredictably.
162 Roughly speaking, any element that is both inserted to a priority
163 queue (e.g. through <code class="code">push</code>) and removed
164 from it (e.g., through <code class="code">pop</code>), incurs a
165 logarithmic overhead (in the amortized sense). Different underlying
166 data structures place the actual cost differently: some are
167 optimized for amortized complexity, whereas others guarantee that
168 specific operations only have a constant cost. One underlying data
169 structure might be chosen if modifying a value is frequent
170 (Dijkstra's shortest-path algorithm), whereas a different one might
171 be chosen otherwise. Unfortunately, an array-based binary heap - an
172 underlying data structure that optimizes (in the amortized sense)
173 <code class="code">push</code> and <code class="code">pop</code> operations, differs from the
174 others in terms of its invalidation guarantees. Other design
175 decisions also impact the cost and placement of the overhead, at the
176 expense of more difference in the the kinds of operations that the
177 underlying data structure can support. These differences pose a
178 challenge when creating a uniform interface for priority queues.
179 </p></div></div><div class="section" title="Goals"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.intro.motivation"></a>Goals</h3></div></div></div><p>
180 Many fine associative-container libraries were already written,
181 most notably, the C++ standard's associative containers. Why
182 then write another library? This section shows some possible
183 advantages of this library, when considering the challenges in
184 the introduction. Many of these points stem from the fact that
185 the ISO C++ process introduced associative-containers in a
186 two-step process (first standardizing tree-based containers,
187 only then adding hash-based containers, which are fundamentally
188 different), did not standardize priority queues as containers,
189 and (in our opinion) overloads the iterator concept.
190 </p><div class="section" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.motivation.associative"></a>Associative</h4></div></div></div><p>
191 </p><div class="section" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.policy"></a>Policy Choices</h5></div></div></div><p>
192 Associative containers require a relatively large number of
193 policies to function efficiently in various settings. In some
194 cases this is needed for making their common operations more
195 efficient, and in other cases this allows them to support a
196 larger set of operations
197 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
198 Hash-based containers, for example, support look-up and
199 insertion methods (<code class="function">find</code> and
200 <code class="function">insert</code>). In order to locate elements
201 quickly, they are supplied a hash functor, which instruct
202 how to transform a key object into some size type; a hash
203 functor might transform <code class="constant">"hello"</code>
204 into <code class="constant">1123002298</code>. A hash table, though,
205 requires transforming each key object into some size-type
206 type in some specific domain; a hash table with a 128-long
207 table might transform <code class="constant">"hello"</code> into
208 position <code class="constant">63</code>. The policy by which the
209 hash value is transformed into a position within the table
210 can dramatically affect performance. Hash-based containers
211 also do not resize naturally (as opposed to tree-based
212 containers, for example). The appropriate resize policy is
213 unfortunately intertwined with the policy that transforms
214 hash value into a position within the table.
215 </p></li><li class="listitem"><p>
216 Tree-based containers, for example, also support look-up and
217 insertion methods, and are primarily useful when maintaining
218 order between elements is important. In some cases, though,
219 one can utilize their balancing algorithms for completely
222 Figure A shows a tree whose each node contains two entries:
223 a floating-point key, and some size-type
224 <span class="emphasis"><em>metadata</em></span> (in bold beneath it) that is
225 the number of nodes in the sub-tree. (The root has key 0.99,
226 and has 5 nodes (including itself) in its sub-tree.) A
227 container based on this data structure can obviously answer
228 efficiently whether 0.3 is in the container object, but it
229 can also answer what is the order of 0.3 among all those in
230 the container object: see <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>.
233 As another example, Figure B shows a tree whose each node
234 contains two entries: a half-open geometric line interval,
235 and a number <span class="emphasis"><em>metadata</em></span> (in bold beneath
236 it) that is the largest endpoint of all intervals in its
237 sub-tree. (The root describes the interval <code class="constant">[20,
238 36)</code>, and the largest endpoint in its sub-tree is
239 99.) A container based on this data structure can obviously
240 answer efficiently whether <code class="constant">[3, 41)</code> is
241 in the container object, but it can also answer efficiently
242 whether the container object has intervals that intersect
243 <code class="constant">[3, 41)</code>. These types of queries are
244 very useful in geometric algorithms and lease-management
247 It is important to note, however, that as the trees are
248 modified, their internal structure changes. To maintain
249 these invariants, one must supply some policy that is aware
250 of these changes. Without this, it would be better to use a
251 linked list (in itself very efficient for these purposes).
252 </p></li></ol></div><div class="figure"><a id="idp17575248"></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" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.underlying"></a>Underlying Data Structures</h5></div></div></div><p>
253 The standard C++ library contains associative containers based on
254 red-black trees and collision-chaining hash tables. These are
255 very useful, but they are not ideal for all types of
258 The figure below shows the different underlying data structures
259 currently supported in this library.
260 </p><div class="figure"><a id="idp17581968"></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>
261 A shows a collision-chaining hash-table, B shows a probing
262 hash-table, C shows a red-black tree, D shows a splay tree, E shows
263 a tree based on an ordered vector(implicit in the order of the
264 elements), F shows a PATRICIA trie, and G shows a list-based
265 container with update policies.
267 Each of these data structures has some performance benefits, in
268 terms of speed, size or both. For now, note that vector-based trees
269 and probing hash tables manipulate memory more efficiently than
270 red-black trees and collision-chaining hash tables, and that
271 list-based associative containers are very useful for constructing
274 Now consider a function manipulating a generic associative
276 </p><pre class="programlisting">
277 template<class Cntnr>
279 some_op_sequence(Cntnr &r_cnt)
284 Ideally, the underlying data structure
285 of <code class="classname">Cntnr</code> would not affect what can be
286 done with <code class="varname">r_cnt</code>. Unfortunately, this is not
289 For example, if <code class="classname">Cntnr</code>
290 is <code class="classname">std::map</code>, then the function can
292 </p><pre class="programlisting">
293 std::for_each(r_cnt.find(foo), r_cnt.find(bar), foobar)
295 in order to apply <code class="classname">foobar</code> to all
296 elements between <code class="classname">foo</code> and
297 <code class="classname">bar</code>. If
298 <code class="classname">Cntnr</code> is a hash-based container,
299 then this call's results are undefined.
301 Also, if <code class="classname">Cntnr</code> is tree-based, the type
302 and object of the comparison functor can be
303 accessed. If <code class="classname">Cntnr</code> is hash based, these
304 queries are nonsensical.
306 There are various other differences based on the container's
307 underlying data structure. For one, they can be constructed by,
308 and queried for, different policies. Furthermore:
309 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
310 Containers based on C, D, E and F store elements in a
311 meaningful order; the others store elements in a meaningless
312 (and probably time-varying) order. By implication, only
313 containers based on C, D, E and F can
314 support <code class="function">erase</code> operations taking an
315 iterator and returning an iterator to the following element
316 without performance loss.
317 </p></li><li class="listitem"><p>
318 Containers based on C, D, E, and F can be split and joined
319 efficiently, while the others cannot. Containers based on C
320 and D, furthermore, can guarantee that this is exception-free;
321 containers based on E cannot guarantee this.
322 </p></li><li class="listitem"><p>
323 Containers based on all but E can guarantee that
324 erasing an element is exception free; containers based on E
325 cannot guarantee this. Containers based on all but B and E
326 can guarantee that modifying an object of their type does
327 not invalidate iterators or references to their elements,
328 while containers based on B and E cannot. Containers based
329 on C, D, and E can furthermore make a stronger guarantee,
330 namely that modifying an object of their type does not
331 affect the order of iterators.
332 </p></li></ol></div><p>
333 A unified tag and traits system (as used for the C++ standard
334 library iterators, for example) can ease generic manipulation of
335 associative containers based on different underlying data
337 </p></div><div class="section" title="Iterators"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.iterators"></a>Iterators</h5></div></div></div><p>
338 Iterators are centric to the design of the standard library
339 containers, because of the container/algorithm/iterator
340 decomposition that allows an algorithm to operate on a range
341 through iterators of some sequence. Iterators, then, are useful
342 because they allow going over a
343 specific <span class="emphasis"><em>sequence</em></span>. The standard library
344 also uses iterators for accessing a
345 specific <span class="emphasis"><em>element</em></span>: when an associative
346 container returns one through <code class="function">find</code>. The
347 standard library consistently uses the same types of iterators
348 for both purposes: going over a range, and accessing a specific
349 found element. Before the introduction of hash-based containers
350 to the standard library, this made sense (with the exception of
351 priority queues, which are discussed later).
353 Using the standard associative containers together with
354 non-order-preserving associative containers (and also because of
355 priority-queues container), there is a possible need for
356 different types of iterators for self-organizing containers:
357 the iterator concept seems overloaded to mean two different
358 things (in some cases). <em><span class="remark"> XXX
359 "ds_gen.html#find_range">Design::Associative
360 Containers::Data-Structure Genericity::Point-Type and Range-Type
362 </p><div class="section" title="Using Point Iterators for Range Operations"><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>
363 Suppose <code class="classname">cntnr</code> is some associative
364 container, and say <code class="varname">c</code> is an object of
365 type <code class="classname">cntnr</code>. Then what will be the outcome
367 </p><pre class="programlisting">
368 std::for_each(c.find(1), c.find(5), foo);
370 If <code class="classname">cntnr</code> is a tree-based container
371 object, then an in-order walk will
372 apply <code class="classname">foo</code> to the relevant elements,
373 as in the graphic below, label A. If <code class="varname">c</code> is
374 a hash-based container, then the order of elements between any
375 two elements is undefined (and probably time-varying); there is
376 no guarantee that the elements traversed will coincide with the
377 <span class="emphasis"><em>logical</em></span> elements between 1 and 5, as in
379 </p><div class="figure"><a id="idp17613664"></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>
380 In our opinion, this problem is not caused just because
381 red-black trees are order preserving while
382 collision-chaining hash tables are (generally) not - it
383 is more fundamental. Most of the standard's containers
384 order sequences in a well-defined manner that is
385 determined by their <span class="emphasis"><em>interface</em></span>:
386 calling <code class="function">insert</code> on a tree-based
387 container modifies its sequence in a predictable way, as
388 does calling <code class="function">push_back</code> on a list or
389 a vector. Conversely, collision-chaining hash tables,
390 probing hash tables, priority queues, and list-based
391 containers (which are very useful for "multimaps") are
392 self-organizing data structures; the effect of each
393 operation modifies their sequences in a manner that is
394 (practically) determined by their
395 <span class="emphasis"><em>implementation</em></span>.
397 Consequently, applying an algorithm to a sequence obtained from most
398 containers may or may not make sense, but applying it to a
399 sub-sequence of a self-organizing container does not.
400 </p></div><div class="section" title="Cost to Point Iterators to Enable Range Operations"><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>
401 Suppose <code class="varname">c</code> is some collision-chaining
402 hash-based container object, and one calls
403 </p><pre class="programlisting">c.find(3)</pre><p>
404 Then what composes the returned iterator?
406 In the graphic below, label A shows the simplest (and
407 most efficient) implementation of a collision-chaining
408 hash table. The little box marked
409 <code class="classname">point_iterator</code> shows an object
410 that contains a pointer to the element's node. Note that
411 this "iterator" has no way to move to the next element (
413 <code class="function">operator++</code>). Conversely, the little
414 box marked <code class="classname">iterator</code> stores both a
415 pointer to the element, as well as some other
416 information (the bucket number of the element). the
417 second iterator, then, is "heavier" than the first one-
418 it requires more time and space. If we were to use a
419 different container to cross-reference into this
420 hash-table using these iterators - it would take much
421 more space. As noted above, nothing much can be done by
422 incrementing these iterators, so why is this extra
425 Alternatively, one might create a collision-chaining hash-table
426 where the lists might be linked, forming a monolithic total-element
427 list, as in the graphic below, label B. Here the iterators are as
428 light as can be, but the hash-table's operations are more
430 </p><div class="figure"><a id="idp17628576"></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>
431 It should be noted that containers based on collision-chaining
432 hash-tables are not the only ones with this type of behavior;
433 many other self-organizing data structures display it as well.
434 </p></div><div class="section" title="Invalidation Guarantees"><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">
438 Following the call to <code class="classname">erase</code>, what is the
439 validity of <code class="classname">it</code>: can it be de-referenced?
440 can it be incremented?
442 The answer depends on the underlying data structure of the
443 container. The graphic below shows three cases: A1 and A2 show
444 a red-black tree; B1 and B2 show a probing hash-table; C1 and C2
445 show a collision-chaining hash table.
446 </p><div class="figure"><a id="idp17637776"></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>
447 Erasing 5 from A1 yields A2. Clearly, an iterator to 3 can
448 be de-referenced and incremented. The sequence of iterators
449 changed, but in a way that is well-defined by the interface.
450 </p></li><li class="listitem"><p>
451 Erasing 5 from B1 yields B2. Clearly, an iterator to 3 is
452 not valid at all - it cannot be de-referenced or
453 incremented; the order of iterators changed in a way that is
454 (practically) determined by the implementation and not by
456 </p></li><li class="listitem"><p>
457 Erasing 5 from C1 yields C2. Here the situation is more
458 complicated. On the one hand, there is no problem in
459 de-referencing <code class="classname">it</code>. On the other hand,
460 the order of iterators changed in a way that is
461 (practically) determined by the implementation and not by
463 </p></li></ol></div><p>
464 So in the standard library containers, it is not always possible
465 to express whether <code class="varname">it</code> is valid or not. This
466 is true also for <code class="function">insert</code>. Again, the
467 iterator concept seems overloaded.
468 </p></div></div><div class="section" title="Functional"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.functions"></a>Functional</h5></div></div></div><p>
470 The design of the functional overlay to the underlying data
471 structures differs slightly from some of the conventions used in
472 the C++ standard. A strict public interface of methods that
473 comprise only operations which depend on the class's internal
474 structure; other operations are best designed as external
475 functions. (See <a class="xref" href="policy_data_structures.html#biblio.meyers02both" title="Class Template, Member Template - or Both?">[biblio.meyers02both]</a>).With this
476 rubric, the standard associative containers lack some useful
477 methods, and provide other methods which would be better
479 </p><div class="section" title="erase"><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>
480 Order-preserving standard associative containers provide the
482 </p><pre class="programlisting">
486 which takes an iterator, erases the corresponding
487 element, and returns an iterator to the following
488 element. Also standardd hash-based associative
489 containers provide this method. This seemingly
490 increasesgenericity between associative containers,
491 since it is possible to use
492 </p><pre class="programlisting">
493 typename C::iterator it = c.begin();
494 typename C::iterator e_it = c.end();
497 it = pred(*it)? c.erase(it) : ++it;
499 in order to erase from a container object <code class="varname">
500 c</code> all element which match a
501 predicate <code class="classname">pred</code>. However, in a
502 different sense this actually decreases genericity: an
503 integral implication of this method is that tree-based
504 associative containers' memory use is linear in the total
505 number of elements they store, while hash-based
506 containers' memory use is unbounded in the total number of
507 elements they store. Assume a hash-based container is
508 allowed to decrease its size when an element is
509 erased. Then the elements might be rehashed, which means
510 that there is no "next" element - it is simply
511 undefined. Consequently, it is possible to infer from the
512 fact that the standard library's hash-based containers
513 provide this method that they cannot downsize when
514 elements are erased. As a consequence, different code is
515 needed to manipulate different containers, assuming that
516 memory should be conserved. Therefor, this library's
517 non-order preserving associative containers omit this
519 </p></li><li class="listitem"><p>
520 All associative containers include a conditional-erase method
521 </p><pre class="programlisting">
528 which erases all elements matching a predicate. This is probably the
529 only way to ensure linear-time multiple-item erase which can
530 actually downsize a container.
531 </p></li><li class="listitem"><p>
532 The standard associative containers provide methods for
533 multiple-item erase of the form
534 </p><pre class="programlisting">
538 erasing a range of elements given by a pair of
539 iterators. For tree-based or trie-based containers, this can
540 implemented more efficiently as a (small) sequence of split
541 and join operations. For other, unordered, containers, this
542 method isn't much better than an external loop. Moreover,
543 if <code class="varname">c</code> is a hash-based container,
545 </p><pre class="programlisting">
546 c.erase(c.find(2), c.find(5))
548 is almost certain to do something
549 different than erasing all elements whose keys are between 2
550 and 5, and is likely to produce other undefined behavior.
551 </p></li></ol></div></div><div class="section" title="split and join"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.split"></a>
552 <code class="function">split</code> and <code class="function">join</code>
553 </h6></div></div></div><p>
554 It is well-known that tree-based and trie-based container
555 objects can be efficiently split or joined (See
556 <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>). Externally splitting or
557 joining trees is super-linear, and, furthermore, can throw
558 exceptions. Split and join methods, consequently, seem good
559 choices for tree-based container methods, especially, since as
560 noted just before, they are efficient replacements for erasing
562 </p></div><div class="section" title="insert"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.insert"></a>
563 <code class="function">insert</code>
564 </h6></div></div></div><p>
565 The standard associative containers provide methods of the form
566 </p><pre class="programlisting">
567 template<class It>
571 for inserting a range of elements given by a pair of
572 iterators. At best, this can be implemented as an external loop,
573 or, even more efficiently, as a join operation (for the case of
574 tree-based or trie-based containers). Moreover, these methods seem
575 similar to constructors taking a range given by a pair of
576 iterators; the constructors, however, are transactional, whereas
577 the insert methods are not; this is possibly confusing.
578 </p></div><div class="section" title="operator== and operator<="><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.compare"></a>
579 <code class="function">operator==</code> and <code class="function">operator<=</code>
580 </h6></div></div></div><p>
581 Associative containers are parametrized by policies allowing to
582 test key equivalence: a hash-based container can do this through
583 its equivalence functor, and a tree-based container can do this
584 through its comparison functor. In addition, some standard
585 associative containers have global function operators, like
586 <code class="function">operator==</code> and <code class="function">operator<=</code>,
587 that allow comparing entire associative containers.
589 In our opinion, these functions are better left out. To begin
590 with, they do not significantly improve over an external
591 loop. More importantly, however, they are possibly misleading -
592 <code class="function">operator==</code>, for example, usually checks for
593 equivalence, or interchangeability, but the associative
594 container cannot check for values' equivalence, only keys'
595 equivalence; also, are two containers considered equivalent if
596 they store the same values in different order? this is an
598 </p></div></div></div><div class="section" title="Priority Queues"><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" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.policy"></a>Policy Choices</h5></div></div></div><p>
599 Priority queues are containers that allow efficiently inserting
600 values and accessing the maximal value (in the sense of the
601 container's comparison functor). Their interface
602 supports <code class="function">push</code>
603 and <code class="function">pop</code>. The standard
604 container <code class="classname">std::priorityqueue</code> indeed support
605 these methods, but little else. For algorithmic and
606 software-engineering purposes, other methods are needed:
607 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
608 Many graph algorithms (see
609 <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>) require increasing a
610 value in a priority queue (again, in the sense of the
611 container's comparison functor), or joining two
612 priority-queue objects.
613 </p></li><li class="listitem"><p>The return type of <code class="classname">priority_queue</code>'s
614 <code class="function">push</code> method is a point-type iterator, which can
615 be used for modifying or erasing arbitrary values. For
616 example:</p><pre class="programlisting">
617 priority_queue<int> p;
618 priority_queue<int>::point_iterator it = p.push(3);
620 </pre><p>These types of cross-referencing operations are necessary
621 for making priority queues useful for different applications,
622 especially graph applications.</p></li><li class="listitem"><p>
623 It is sometimes necessary to erase an arbitrary value in a
624 priority queue. For example, consider
625 the <code class="function">select</code> function for monitoring
627 </p><pre class="programlisting">
629 select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds,
630 struct timeval *timeout);
632 then, as the select documentation states:
634 <span class="quote">“<span class="quote">
635 The nfds argument specifies the range of file
636 descriptors to be tested. The select() function tests file
637 descriptors in the range of 0 to nfds-1.</span>”</span>
639 It stands to reason, therefore, that we might wish to
640 maintain a minimal value for <code class="varname">nfds</code>, and
641 priority queues immediately come to mind. Note, though, that
642 when a socket is closed, the minimal file description might
643 change; in the absence of an efficient means to erase an
644 arbitrary value from a priority queue, we might as well
645 avoid its use altogether.
647 The standard containers typically support iterators. It is
649 for <code class="classname">std::priority_queue</code> to omit them
650 (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
651 ask why do priority queues need to support iterators, since
652 they are self-organizing containers with a different purpose
653 than abstracting sequences. There are several reasons:
654 </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p>
655 Iterators (even in self-organizing containers) are
656 useful for many purposes: cross-referencing
657 containers, serialization, and debugging code that uses
659 </p></li><li class="listitem"><p>
660 The standard library's hash-based containers support
661 iterators, even though they too are self-organizing
662 containers with a different purpose than abstracting
664 </p></li><li class="listitem"><p>
665 In standard-library-like containers, it is natural to specify the
666 interface of operations for modifying a value or erasing
667 a value (discussed previously) in terms of a iterators.
668 It should be noted that the standard
669 containers also use iterators for accessing and
670 manipulating a specific value. In hash-based
671 containers, one checks the existence of a key by
672 comparing the iterator returned by <code class="function">find</code> to the
673 iterator returned by <code class="function">end</code>, and not by comparing a
674 pointer returned by <code class="function">find</code> to <span class="type">NULL</span>.
675 </p></li></ol></div></li></ol></div></div><div class="section" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.underlying"></a>Underlying Data Structures</h5></div></div></div><p>
676 There are three main implementations of priority queues: the
677 first employs a binary heap, typically one which uses a
678 sequence; the second uses a tree (or forest of trees), which is
679 typically less structured than an associative container's tree;
680 the third simply uses an associative container. These are
681 shown in the figure below with labels A1 and A2, B, and C.
682 </p><div class="figure"><a id="idp17705360"></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>
683 No single implementation can completely replace any of the
684 others. Some have better <code class="function">push</code>
685 and <code class="function">pop</code> amortized performance, some have
686 better bounded (worst case) response time than others, some
687 optimize a single method at the expense of others, etc. In
688 general the "best" implementation is dictated by the specific
691 As with associative containers, the more implementations
692 co-exist, the more necessary a traits mechanism is for handling
693 generic containers safely and efficiently. This is especially
694 important for priority queues, since the invalidation guarantees
695 of one of the most useful data structures - binary heaps - is
696 markedly different than those of most of the others.
697 </p></div><div class="section" title="Binary Heaps"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.binary_heap"></a>Binary Heaps</h5></div></div></div><p>
698 Binary heaps are one of the most useful underlying
699 data structures for priority queues. They are very efficient in
700 terms of memory (since they don't require per-value structure
701 metadata), and have the best amortized <code class="function">push</code> and
702 <code class="function">pop</code> performance for primitive types like
703 <span class="type">int</span>.
705 The standard library's <code class="classname">priority_queue</code>
706 implements this data structure as an adapter over a sequence,
708 <code class="classname">std::vector</code>
709 or <code class="classname">std::deque</code>, which correspond to labels
710 A1 and A2 respectively in the graphic above.
712 This is indeed an elegant example of the adapter concept and
713 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
714 several reasons why a binary-heap priority queue
715 may be better implemented as a container instead of a
717 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
718 <code class="classname">std::priority_queue</code> cannot erase values
719 from its adapted sequence (irrespective of the sequence
720 type). This means that the memory use of
721 an <code class="classname">std::priority_queue</code> object is always
722 proportional to the maximal number of values it ever contained,
723 and not to the number of values that it currently
724 contains. (See <code class="filename">performance/priority_queue_text_pop_mem_usage.cc</code>.)
725 This implementation of binary heaps acts very differently than
726 other underlying data structures (See also pairing heaps).
727 </p></li><li class="listitem"><p>
728 Some combinations of adapted sequences and value types
729 are very inefficient or just don't make sense. If one uses
730 <code class="classname">std::priority_queue<std::vector<std::string>
731 > ></code>, for example, then not only will each
732 operation perform a logarithmic number of
733 <code class="classname">std::string</code> assignments, but, furthermore, any
734 operation (including <code class="function">pop</code>) can render the container
735 useless due to exceptions. Conversely, if one uses
736 <code class="classname">std::priority_queue<std::deque<int> >
737 ></code>, then each operation uses incurs a logarithmic
738 number of indirect accesses (through pointers) unnecessarily.
739 It might be better to let the container make a conservative
740 deduction whether to use the structure in the graphic above, labels A1 or A2.
741 </p></li><li class="listitem"><p>
742 There does not seem to be a systematic way to determine
743 what exactly can be done with the priority queue.
744 </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p>
745 If <code class="classname">p</code> is a priority queue adapting an
746 <code class="classname">std::vector</code>, then it is possible to iterate over
747 all values by using <code class="function">&p.top()</code> and
748 <code class="function">&p.top() + p.size()</code>, but this will not work
749 if <code class="varname">p</code> is adapting an <code class="classname">std::deque</code>; in any
750 case, one cannot use <code class="classname">p.begin()</code> and
751 <code class="classname">p.end()</code>. If a different sequence is adapted, it
752 is even more difficult to determine what can be
754 </p></li><li class="listitem"><p>
755 If <code class="varname">p</code> is a priority queue adapting an
756 <code class="classname">std::deque</code>, then the reference return by
757 </p><pre class="programlisting">
760 will remain valid until it is popped,
761 but if <code class="varname">p</code> adapts an <code class="classname">std::vector</code>, the
762 next <code class="function">push</code> will invalidate it. If a different
763 sequence is adapted, it is even more difficult to
764 determine what can be done.
765 </p></li></ol></div></li><li class="listitem"><p>
766 Sequence-based binary heaps can still implement
767 linear-time <code class="function">erase</code> and <code class="function">modify</code> operations.
768 This means that if one needs to erase a small
769 (say logarithmic) number of values, then one might still
770 choose this underlying data structure. Using
771 <code class="classname">std::priority_queue</code>, however, this will generally
772 change the order of growth of the entire sequence of
774 </p></li></ol></div></div></div></div></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h2 class="title"><a id="pbds.biblio"></a>Bibliography</h2></div></div></div><div class="biblioentry" title="STL Exception Handling Contract"><a id="biblio.abrahams97exception"></a><p>[biblio.abrahams97exception] <span class="title"><em>
775 <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1075.pdf" target="_top">
776 STL Exception Handling Contract
778 </em>. </span><span class="date">1997. </span><span class="author"><span class="firstname">
780 </span> <span class="surname">
782 </span>. </span><span class="publisher"><span class="publishername">
784 . </span></span></p></div><div class="biblioentry" title="Modern C++ Design: Generic Programming and Design Patterns Applied"><a id="biblio.alexandrescu01modern"></a><p>[biblio.alexandrescu01modern] <span class="title"><em>
785 Modern C++ Design: Generic Programming and Design Patterns Applied
786 </em>. </span><span class="date">
788 . </span><span class="author"><span class="firstname">
790 </span> <span class="surname">
792 </span>. </span><span class="publisher"><span class="publishername">
793 Addison-Wesley Publishing Company
794 . </span></span></p></div><div class="biblioentry" title="MTF, Bit, and COMB: A Guide to Deterministic and Randomized Algorithms for the List Update Problem"><a id="biblio.andrew04mtf"></a><p>[biblio.andrew04mtf] <span class="title"><em>
795 MTF, Bit, and COMB: A Guide to Deterministic and Randomized
796 Algorithms for the List Update Problem
797 </em>. </span><span class="authorgroup"><span class="firstname">
799 </span> <span class="surname">
801 </span> and <span class="firstname">
803 </span> <span class="surname">
805 </span>. </span></p></div><div class="biblioentry" title="Why You Shouldn't Use set - and What You Should Use Instead"><a id="biblio.austern00noset"></a><p>[biblio.austern00noset] <span class="title"><em>
806 Why You Shouldn't Use set - and What You Should Use Instead
807 </em>. </span><span class="date">
809 . </span><span class="author"><span class="firstname">
811 </span> <span class="surname">
813 </span>. </span><span class="publisher"><span class="publishername">
815 . </span></span></p></div><div class="biblioentry" title="A Proposal to Add Hashtables to the Standard Library"><a id="biblio.austern01htprop"></a><p>[biblio.austern01htprop] <span class="title"><em>
816 <a class="link" href="http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2001/n1326.html" target="_top">
817 A Proposal to Add Hashtables to the Standard Library
819 </em>. </span><span class="date">
821 . </span><span class="author"><span class="firstname">
823 </span> <span class="surname">
825 </span>. </span><span class="publisher"><span class="publishername">
827 . </span></span></p></div><div class="biblioentry" title="Segmented iterators and hierarchical algorithms"><a id="biblio.austern98segmentedit"></a><p>[biblio.austern98segmentedit] <span class="title"><em>
828 Segmented iterators and hierarchical algorithms
829 </em>. </span><span class="date">
831 . </span><span class="author"><span class="firstname">
833 </span> <span class="surname">
835 </span>. </span><span class="publisher"><span class="publishername">
837 . </span></span></p></div><div class="biblioentry" title="Boost Timer Library"><a id="biblio.dawestimer"></a><p>[biblio.dawestimer] <span class="title"><em>
838 <a class="link" href="www.boost.org/doc/libs/release/libs/timer/" target="_top">
841 </em>. </span><span class="author"><span class="firstname">
843 </span> <span class="surname">
845 </span>. </span><span class="publisher"><span class="publishername">
847 . </span></span></p></div><div class="biblioentry" title="Boost Pool Library"><a id="biblio.clearypool"></a><p>[biblio.clearypool] <span class="title"><em>
848 <a class="link" href="www.boost.org/doc/libs/release/libs/pool/" target="_top">
851 </em>. </span><span class="author"><span class="firstname">
853 </span> <span class="surname">
855 </span>. </span><span class="publisher"><span class="publishername">
857 . </span></span></p></div><div class="biblioentry" title="Boost Type Traits Library"><a id="biblio.maddocktraits"></a><p>[biblio.maddocktraits] <span class="title"><em>
858 <a class="link" href="www.boost.org/doc/libs/release/libs/type_traits/" target="_top">
859 Boost Type Traits Library
861 </em>. </span><span class="authorgroup"><span class="firstname">
863 </span> <span class="surname">
865 </span> and <span class="firstname">
867 </span> <span class="surname">
869 </span>. </span><span class="publisher"><span class="publishername">
871 . </span></span></p></div><div class="biblioentry" title="Worst-case efficient priority queues"><a id="biblio.brodal96priority"></a><p>[biblio.brodal96priority] <span class="title"><em>
872 <a class="link" href="https://dl.acm.org/citation.cfm?id=313883" target="_top">
873 Worst-case efficient priority queues
875 </em>. </span><span class="author"><span class="firstname">
877 </span> <span class="surname">
879 </span>. </span></p></div><div class="biblioentry" title="Efficient C++ Programming Techniques"><a id="biblio.bulkamayheweff"></a><p>[biblio.bulkamayheweff] <span class="title"><em>
880 Efficient C++ Programming Techniques
881 </em>. </span><span class="date">
883 . </span><span class="authorgroup"><span class="firstname">
885 </span> <span class="surname">
887 </span> and <span class="firstname">
889 </span> <span class="surname">
891 </span>. </span><span class="publisher"><span class="publishername">
892 Addison-Wesley Publishing Company
893 . </span></span></p></div><div class="biblioentry" title="Introduction to Algorithms, 2nd edition"><a id="biblio.clrs2001"></a><p>[biblio.clrs2001] <span class="title"><em>
894 Introduction to Algorithms, 2nd edition
895 </em>. </span><span class="date">
897 . </span><span class="authorgroup"><span class="firstname">
899 </span> <span class="surname">
901 </span>, <span class="firstname">
903 </span> <span class="surname">
905 </span>, <span class="firstname">
907 </span> <span class="surname">
909 </span>, and <span class="firstname">
911 </span> <span class="surname">
913 </span>. </span><span class="publisher"><span class="publishername">
915 . </span></span></p></div><div class="biblioentry" title="Balls and bins: A study in negative dependence"><a id="biblio.dubhashi98neg"></a><p>[biblio.dubhashi98neg] <span class="title"><em>
916 Balls and bins: A study in negative dependence
917 </em>. </span><span class="date">
919 . </span><span class="authorgroup"><span class="firstname">
921 </span> <span class="surname">
923 </span> and <span class="firstname">
925 </span> <span class="surname">
927 </span>. </span><span class="publisher"><span class="publishername">
928 Random Structures and Algorithms 13
929 . </span></span></p></div><div class="biblioentry" title="Extendible hashing - a fast access method for dynamic files"><a id="biblio.fagin79extendible"></a><p>[biblio.fagin79extendible] <span class="title"><em>
930 Extendible hashing - a fast access method for dynamic files
931 </em>. </span><span class="date">
933 . </span><span class="authorgroup"><span class="firstname">
935 </span> <span class="surname">
937 </span>, <span class="firstname">
939 </span> <span class="surname">
941 </span>, <span class="firstname">
943 </span> <span class="surname">
945 </span>, and <span class="firstname">
947 </span> <span class="surname">
949 </span>. </span><span class="publisher"><span class="publishername">
950 ACM Trans. Database Syst. 4
951 . </span></span></p></div><div class="biblioentry" title="Ptset: Sets of integers implemented as Patricia trees"><a id="biblio.filliatre2000ptset"></a><p>[biblio.filliatre2000ptset] <span class="title"><em>
952 <a class="link" href="http://cristal.inria.fr/~frisch/icfp06_contest/advtr/applyOmatic/ptset.ml" target="_top">
953 Ptset: Sets of integers implemented as Patricia trees
955 </em>. </span><span class="date">
957 . </span><span class="author"><span class="firstname">
959 </span> <span class="surname">
961 </span>. </span></p></div><div class="biblioentry" title="The pairing heap: a new form of self-adjusting heap"><a id="biblio.fredman86pairing"></a><p>[biblio.fredman86pairing] <span class="title"><em>
962 <a class="link" href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf" target="_top">
963 The pairing heap: a new form of self-adjusting heap
965 </em>. </span><span class="date">
967 . </span><span class="authorgroup"><span class="firstname">
969 </span> <span class="surname">
971 </span>, <span class="firstname">
973 </span> <span class="surname">
975 </span>, <span class="firstname">
977 </span> <span class="surname">
979 </span>, and <span class="firstname">
981 </span> <span class="surname">
983 </span>. </span></p></div><div class="biblioentry" title="Design Patterns - Elements of Reusable Object-Oriented Software"><a id="biblio.gof"></a><p>[biblio.gof] <span class="title"><em>
984 Design Patterns - Elements of Reusable Object-Oriented Software
985 </em>. </span><span class="date">
987 . </span><span class="authorgroup"><span class="firstname">
989 </span> <span class="surname">
991 </span>, <span class="firstname">
993 </span> <span class="surname">
995 </span>, <span class="firstname">
997 </span> <span class="surname">
999 </span>, and <span class="firstname">
1001 </span> <span class="surname">
1003 </span>. </span><span class="publisher"><span class="publishername">
1004 Addison-Wesley Publishing Company
1005 . </span></span></p></div><div class="biblioentry" title="Order-preserving key transformations"><a id="biblio.garg86order"></a><p>[biblio.garg86order] <span class="title"><em>
1006 Order-preserving key transformations
1007 </em>. </span><span class="date">
1009 . </span><span class="authorgroup"><span class="firstname">
1011 </span> <span class="surname">
1013 </span> and <span class="firstname">
1015 </span> <span class="surname">
1017 </span>. </span><span class="publisher"><span class="publishername">
1018 Trans. Database Syst. 11
1019 . </span></span></p></div><div class="biblioentry" title="Making a real hash of things"><a id="biblio.hyslop02making"></a><p>[biblio.hyslop02making] <span class="title"><em>
1020 Making a real hash of things
1021 </em>. </span><span class="date">
1023 . </span><span class="authorgroup"><span class="firstname">
1025 </span> <span class="surname">
1027 </span> and <span class="firstname">
1029 </span> <span class="surname">
1031 </span>. </span><span class="publisher"><span class="publishername">
1033 . </span></span></p></div><div class="biblioentry" title="The C++ Standard Library - A Tutorial and Reference"><a id="biblio.jossutis01stl"></a><p>[biblio.jossutis01stl] <span class="title"><em>
1034 The C++ Standard Library - A Tutorial and Reference
1035 </em>. </span><span class="date">
1037 . </span><span class="author"><span class="firstname">
1039 </span> <span class="surname">
1041 </span>. </span><span class="publisher"><span class="publishername">
1042 Addison-Wesley Publishing Company
1043 . </span></span></p></div><div class="biblioentry" title="New Heap Data Structures"><a id="biblio.kt99fat_heaps"></a><p>[biblio.kt99fat_heaps] <span class="title"><em>
1044 <a class="link" href="http://www.cs.princeton.edu/research/techreps/TR-597-99" target="_top">
1045 New Heap Data Structures
1047 </em>. </span><span class="date">
1049 . </span><span class="authorgroup"><span class="firstname">
1051 </span> <span class="surname">
1053 </span> and <span class="firstname">
1055 </span> <span class="surname">
1057 </span>. </span></p></div><div class="biblioentry" title="Are Set Iterators Mutable or Immutable?"><a id="biblio.kleft00sets"></a><p>[biblio.kleft00sets] <span class="title"><em>
1058 Are Set Iterators Mutable or Immutable?
1059 </em>. </span><span class="date">
1061 . </span><span class="authorgroup"><span class="firstname">
1063 </span> <span class="surname">
1065 </span> and <span class="firstname">
1067 </span> <span class="surname">
1069 </span>. </span><span class="publisher"><span class="publishername">
1071 . </span></span></p></div><div class="biblioentry" title="The Art of Computer Programming - Sorting and Searching"><a id="biblio.knuth98sorting"></a><p>[biblio.knuth98sorting] <span class="title"><em>
1072 The Art of Computer Programming - Sorting and Searching
1073 </em>. </span><span class="date">
1075 . </span><span class="author"><span class="firstname">
1077 </span> <span class="surname">
1079 </span>. </span><span class="publisher"><span class="publishername">
1080 Addison-Wesley Publishing Company
1081 . </span></span></p></div><div class="biblioentry" title="Data abstraction and hierarchy"><a id="biblio.liskov98data"></a><p>[biblio.liskov98data] <span class="title"><em>
1082 Data abstraction and hierarchy
1083 </em>. </span><span class="date">
1085 . </span><span class="author"><span class="firstname">
1087 </span> <span class="surname">
1089 </span>. </span><span class="publisher"><span class="publishername">
1091 . </span></span></p></div><div class="biblioentry" title="Linear hashing: A new tool for file and table addressing"><a id="biblio.litwin80lh"></a><p>[biblio.litwin80lh] <span class="title"><em>
1092 Linear hashing: A new tool for file and table addressing
1093 </em>. </span><span class="date">
1095 . </span><span class="author"><span class="firstname">
1097 </span> <span class="surname">
1099 </span>. </span><span class="publisher"><span class="publishername">
1100 Proceedings of International Conference on Very Large Data Bases
1101 . </span></span></p></div><div class="biblioentry" title="Deamortization - Part 2: Binomial Heaps"><a id="biblio.maverik_lowerbounds"></a><p>[biblio.maverik_lowerbounds] <span class="title"><em>
1102 <a class="link" href="http://magic.aladdin.cs.cmu.edu/2005/08/01/deamortization-part-2-binomial-heaps" target="_top">
1103 Deamortization - Part 2: Binomial Heaps
1105 </em>. </span><span class="date">
1107 . </span><span class="author"><span class="firstname">
1109 </span> <span class="surname">
1111 </span>. </span></p></div><div class="biblioentry" title="More Effective C++: 35 New Ways to Improve Your Programs and Designs"><a id="biblio.meyers96more"></a><p>[biblio.meyers96more] <span class="title"><em>
1112 More Effective C++: 35 New Ways to Improve Your Programs and Designs
1113 </em>. </span><span class="date">
1115 . </span><span class="author"><span class="firstname">
1117 </span> <span class="surname">
1119 </span>. </span><span class="publisher"><span class="publishername">
1120 Addison-Wesley Publishing Company
1121 . </span></span></p></div><div class="biblioentry" title="How Non-Member Functions Improve Encapsulation"><a id="biblio.meyers00nonmember"></a><p>[biblio.meyers00nonmember] <span class="title"><em>
1122 How Non-Member Functions Improve Encapsulation
1123 </em>. </span><span class="date">
1125 . </span><span class="author"><span class="firstname">
1127 </span> <span class="surname">
1129 </span>. </span><span class="publisher"><span class="publishername">
1131 . </span></span></p></div><div class="biblioentry" title="Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library"><a id="biblio.meyers01stl"></a><p>[biblio.meyers01stl] <span class="title"><em>
1132 Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library
1133 </em>. </span><span class="date">
1135 . </span><span class="author"><span class="firstname">
1137 </span> <span class="surname">
1139 </span>. </span><span class="publisher"><span class="publishername">
1140 Addison-Wesley Publishing Company
1141 . </span></span></p></div><div class="biblioentry" title="Class Template, Member Template - or Both?"><a id="biblio.meyers02both"></a><p>[biblio.meyers02both] <span class="title"><em>
1142 Class Template, Member Template - or Both?
1143 </em>. </span><span class="date">
1145 . </span><span class="author"><span class="firstname">
1147 </span> <span class="surname">
1149 </span>. </span><span class="publisher"><span class="publishername">
1151 . </span></span></p></div><div class="biblioentry" title="Randomized Algorithms"><a id="biblio.motwani95random"></a><p>[biblio.motwani95random] <span class="title"><em>
1152 Randomized Algorithms
1153 </em>. </span><span class="date">
1155 . </span><span class="authorgroup"><span class="firstname">
1157 </span> <span class="surname">
1159 </span> and <span class="firstname">
1161 </span> <span class="surname">
1163 </span>. </span><span class="publisher"><span class="publishername">
1164 Cambridge University Press
1165 . </span></span></p></div><div class="biblioentry" title="COM: Component Model Object Technologies"><a id="biblio.mscom"></a><p>[biblio.mscom] <span class="title"><em>
1166 <a class="link" href="https://www.microsoft.com/com/" target="_top">
1167 COM: Component Model Object Technologies
1169 </em>. </span><span class="publisher"><span class="publishername">
1171 . </span></span></p></div><div class="biblioentry" title="Rationale for Adding Hash Tables to the C++ Standard Template Library"><a id="biblio.musser95rationale"></a><p>[biblio.musser95rationale] <span class="title"><em>
1172 Rationale for Adding Hash Tables to the C++ Standard Template Library
1173 </em>. </span><span class="date">
1175 . </span><span class="author"><span class="firstname">
1177 </span> <span class="surname">
1179 </span>. </span></p></div><div class="biblioentry" title="STL Tutorial and Reference Guide"><a id="biblio.musser96stltutorial"></a><p>[biblio.musser96stltutorial] <span class="title"><em>
1180 STL Tutorial and Reference Guide
1181 </em>. </span><span class="date">
1183 . </span><span class="authorgroup"><span class="firstname">
1185 </span> <span class="surname">
1187 </span> and <span class="firstname">
1189 </span> <span class="surname">
1191 </span>. </span><span class="publisher"><span class="publishername">
1192 Addison-Wesley Publishing Company
1193 . </span></span></p></div><div class="biblioentry" title="Priority Queues and the STL"><a id="biblio.nelson96stlpq"></a><p>[biblio.nelson96stlpq] <span class="title"><em>
1194 <a class="link" href="http://www.dogma.net/markn/articles/pq_stl/priority.htm" target="_top">Priority Queues and the STL
1196 </em>. </span><span class="date">
1198 . </span><span class="author"><span class="firstname">
1200 </span> <span class="surname">
1202 </span>. </span><span class="publisher"><span class="publishername">
1204 . </span></span></p></div><div class="biblioentry" title="Fast mergeable integer maps"><a id="biblio.okasaki98mereable"></a><p>[biblio.okasaki98mereable] <span class="title"><em>
1205 Fast mergeable integer maps
1206 </em>. </span><span class="date">
1208 . </span><span class="authorgroup"><span class="firstname">
1210 </span> <span class="surname">
1212 </span> and <span class="firstname">
1214 </span> <span class="surname">
1216 </span>. </span><span class="publisher"><span class="publishername">
1218 . </span></span></p></div><div class="biblioentry" title="Standard Template Library Programmer's Guide"><a id="biblio.sgi_stl"></a><p>[biblio.sgi_stl] <span class="title"><em>
1219 <a class="link" href="http://www.sgi.com/tech/stl/" target="_top">
1220 Standard Template Library Programmer's Guide
1222 </em>. </span><span class="author"><span class="firstname">
1224 </span> <span class="surname">
1226 </span>. </span><span class="publisher"><span class="publishername">
1228 . </span></span></p></div><div class="biblioentry" title="select"><a id="biblio.select_man"></a><p>[biblio.select_man] <span class="title"><em>
1229 <a class="link" href="http://pubs.opengroup.org/onlinepubs/9699919799/functions/select.html" target="_top">
1232 </em>. </span></p></div><div class="biblioentry" title="Amortized Efficiency of List Update Problems"><a id="biblio.sleator84amortized"></a><p>[biblio.sleator84amortized] <span class="title"><em>
1233 Amortized Efficiency of List Update Problems
1234 </em>. </span><span class="date">
1236 . </span><span class="authorgroup"><span class="firstname">
1238 </span> <span class="surname">
1240 </span> and <span class="firstname">
1242 </span> <span class="surname">
1244 </span>. </span><span class="publisher"><span class="publishername">
1245 ACM Symposium on Theory of Computing
1246 . </span></span></p></div><div class="biblioentry" title="Self-Adjusting Binary Search Trees"><a id="biblio.sleator85self"></a><p>[biblio.sleator85self] <span class="title"><em>
1247 Self-Adjusting Binary Search Trees
1248 </em>. </span><span class="date">
1250 . </span><span class="authorgroup"><span class="firstname">
1252 </span> <span class="surname">
1254 </span> and <span class="firstname">
1256 </span> <span class="surname">
1258 </span>. </span><span class="publisher"><span class="publishername">
1259 ACM Symposium on Theory of Computing
1260 . </span></span></p></div><div class="biblioentry" title="The Standard Template Library"><a id="biblio.stepanov94standard"></a><p>[biblio.stepanov94standard] <span class="title"><em>
1261 The Standard Template Library
1262 </em>. </span><span class="date">
1264 . </span><span class="authorgroup"><span class="firstname">
1266 </span> <span class="surname">
1268 </span> and <span class="firstname">
1270 </span> <span class="surname">
1272 </span>. </span></p></div><div class="biblioentry" title="The C++ Programming Langugage"><a id="biblio.stroustrup97cpp"></a><p>[biblio.stroustrup97cpp] <span class="title"><em>
1273 The C++ Programming Langugage
1274 </em>. </span><span class="date">
1276 . </span><span class="author"><span class="firstname">
1278 </span> <span class="surname">
1280 </span>. </span><span class="publisher"><span class="publishername">
1281 Addison-Wesley Publishing Company
1282 . </span></span></p></div><div class="biblioentry" title="C++ Templates: The Complete Guide"><a id="biblio.vandevoorde2002cpptemplates"></a><p>[biblio.vandevoorde2002cpptemplates] <span class="title"><em>
1283 C++ Templates: The Complete Guide
1284 </em>. </span><span class="date">
1286 . </span><span class="authorgroup"><span class="firstname">
1288 </span> <span class="surname">
1290 </span> and <span class="firstname">
1292 </span> <span class="surname">
1294 </span>. </span><span class="publisher"><span class="publishername">
1295 Addison-Wesley Publishing Company
1296 . </span></span></p></div><div class="biblioentry" title="Thirty Years Among the Dead"><a id="biblio.wickland96thirty"></a><p>[biblio.wickland96thirty] <span class="title"><em>
1297 <a class="link" href="http://myweb.wvnet.edu/~gsa00121/books/amongdead30.zip" target="_top">
1298 Thirty Years Among the Dead
1300 </em>. </span><span class="date">
1302 . </span><span class="author"><span class="firstname">
1304 </span> <span class="surname">
1306 </span>. </span><span class="publisher"><span class="publishername">
1307 National Psychological Institute
1308 . </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="bk01pt03ch21s02.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>