OSDN Git Service

* doc/xml/manual/abi.xml: Update URLs for C++ ABI.
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / doc / html / manual / policy_data_structures.html
1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
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="&#10;&#9;ISO C++&#10;      , &#10;&#9;policy&#10;      , &#10;&#9;container&#10;      , &#10;&#9;data&#10;      , &#10;&#9;structure&#10;      , &#10;&#9;associated&#10;      , &#10;&#9;tree&#10;      , &#10;&#9;trie&#10;      , &#10;&#9;hash&#10;      , &#10;&#9;metaprogramming&#10;      " /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    " /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      runtime&#10;    , &#10;      library&#10;    " /><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. 
4   Extensions
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">
25           Erase Memory Use
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">
35           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
74       by design).
75     </p><p>
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>
77       </p><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.
82       </p><p>
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.
89       </p><p>
90         In many cases, the longer names allow capabilities and behaviours
91         controlled by macros to also be unamibiguously emitted as distinct
92         generated names.
93       </p><p>
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.
108         </p><p>
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
113           container.
114         </p><pre class="programlisting">
115           template&lt;typename Cntnr&gt;
116           void
117           some_op_sequence(Cntnr&amp; r_cnt)
118           {
119           ...
120           }
121         </pre><p>
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
136           thrown.
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.
140         </p><p>
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
152           point...
153         </p><p>
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.
161         </p><p>
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
220                 different purposes.
221               </p><p>
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>.
232               </p><p>
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
245                 algorithms.
246               </p><p>
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
256             settings.
257           </p><p>
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.
266           </p><p>
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
272             "multimaps".
273           </p><p>
274             Now consider a function manipulating a generic associative
275             container,
276           </p><pre class="programlisting">
277             template&lt;class Cntnr&gt;
278             int
279             some_op_sequence(Cntnr &amp;r_cnt)
280             {
281             ...
282             }
283           </pre><p>
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
287             the case.
288           </p><p>
289             For example, if <code class="classname">Cntnr</code>
290             is <code class="classname">std::map</code>, then the function can
291             use
292           </p><pre class="programlisting">
293             std::for_each(r_cnt.find(foo), r_cnt.find(bar), foobar)
294           </pre><p>
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.
300           </p><p>
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.
305           </p><p>
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
336             structures.
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).
352           </p><p>
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"&gt;Design::Associative
360             Containers::Data-Structure Genericity::Point-Type and Range-Type
361             Methods</span></em>.
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
366               of
367             </p><pre class="programlisting">
368               std::for_each(c.find(1), c.find(5), foo);
369             </pre><p>
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
378               label B.
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>.
396             </p><p>
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?
405             </p><p>
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 (
412               it cannot support
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
423               information needed?
424             </p><p>
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
429               complicated.
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">
435               it = c.find(3);
436               c.erase(5);
437             </pre><p>
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?
441             </p><p>
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
455                   the interface.
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
462                   the interface.
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>
469           </p><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
478             removed.
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
481                   method
482                 </p><pre class="programlisting">
483                   iterator
484                   erase(iterator it)
485                 </pre><p>
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();
496                   while(it != e_it)
497                   it = pred(*it)? c.erase(it) : ++it;
498                 </pre><p>
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
518                   method.
519                 </p></li><li class="listitem"><p>
520                   All associative containers include a conditional-erase method
521                 </p><pre class="programlisting">
522                   template&lt;
523                   class Pred&gt;
524                   size_type
525                   erase_if
526                   (Pred pred)
527                 </pre><p>
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">
535                   size_type
536                   erase(It b, It e)
537                 </pre><p>
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,
544                   then
545                 </p><pre class="programlisting">
546                   c.erase(c.find(2), c.find(5))
547                 </pre><p>
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
561               sub-sequences.
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&lt;class It&gt;
568               size_type
569               insert(It b, It e);
570             </pre><p>
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&lt;="><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&lt;=</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&lt;=</code>,
587               that allow comparing entire associative containers.
588             </p><p>
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
597               arbitrary decision.
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&lt;int&gt; p;
618                 priority_queue&lt;int&gt;::point_iterator it = p.push(3);
619                 p.modify(it, 4);
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
626                 file descriptors:
627               </p><pre class="programlisting">
628                 int
629                 select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds,
630                 struct timeval *timeout);
631               </pre><p>
632                 then, as the select documentation states:
633               </p><p>
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>
638               </p><p>
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.
646               </p><p>
647                 The standard containers typically support iterators. It is
648                 somewhat unusual
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
658                     these containers.
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
663                     sequences.
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
689             problem.
690           </p><p>
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>.
704           </p><p>
705             The standard library's <code class="classname">priority_queue</code>
706             implements this data structure as an adapter over a sequence,
707             typically
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.
711           </p><p>
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
716             sequence adapter:
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&lt;std::vector&lt;std::string&gt;
731                 &gt; &gt;</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&lt;std::deque&lt;int&gt; &gt;
737                 &gt;</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">&amp;p.top()</code> and
748                     <code class="function">&amp;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
753                     done.
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">
758                     p.top()
759                   </pre><p>
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
773                 operations.
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
777         </a>
778       </em>. </span><span class="date">1997. </span><span class="author"><span class="firstname">
779             Dave
780           </span> <span class="surname">
781             Abrahams
782           </span>. </span><span class="publisher"><span class="publishername">
783           ISO SC22/WG21
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">
787         2001
788       . </span><span class="author"><span class="firstname">
789             Andrei
790           </span> <span class="surname">
791             Alexandrescu
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">
798               K.
799             </span> <span class="surname">
800               Andrew
801             </span> and <span class="firstname">
802               D.
803             </span> <span class="surname">
804               Gleich
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">
808         April, 2000
809       . </span><span class="author"><span class="firstname">
810             Matthew
811           </span> <span class="surname">
812             Austern
813           </span>. </span><span class="publisher"><span class="publishername">
814           C++ Report
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
818         </a>
819       </em>. </span><span class="date">
820         2001
821       . </span><span class="author"><span class="firstname">
822             Matthew
823           </span> <span class="surname">
824             Austern
825           </span>. </span><span class="publisher"><span class="publishername">
826           ISO SC22/WG21
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">
830         April, 1998
831       . </span><span class="author"><span class="firstname">
832             Matthew
833           </span> <span class="surname">
834             Austern
835           </span>. </span><span class="publisher"><span class="publishername">
836           Generic Programming
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">
839           Boost Timer Library
840         </a>
841       </em>. </span><span class="author"><span class="firstname">
842             Beeman
843           </span> <span class="surname">
844             Dawes
845           </span>. </span><span class="publisher"><span class="publishername">
846           Boost
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">
849           Boost Pool Library
850         </a>
851       </em>. </span><span class="author"><span class="firstname">
852             Stephen
853           </span> <span class="surname">
854             Cleary
855           </span>. </span><span class="publisher"><span class="publishername">
856           Boost
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
860         </a>
861       </em>. </span><span class="authorgroup"><span class="firstname">
862               Maddock
863             </span> <span class="surname">
864               John
865             </span> and <span class="firstname">
866               Stephen
867             </span> <span class="surname">
868               Cleary
869             </span>. </span><span class="publisher"><span class="publishername">
870           Boost
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
874         </a>
875       </em>. </span><span class="author"><span class="firstname">
876             Gerth
877           </span> <span class="surname">
878             Stolting Brodal
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">
882         1997
883       . </span><span class="authorgroup"><span class="firstname">
884               D.
885             </span> <span class="surname">
886               Bulka
887             </span> and <span class="firstname">
888               D.
889             </span> <span class="surname">
890               Mayhew
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">
896         2001
897       . </span><span class="authorgroup"><span class="firstname">
898               T. H.
899             </span> <span class="surname">
900               Cormen
901             </span>, <span class="firstname">
902               C. E.
903             </span> <span class="surname">
904               Leiserson
905             </span>, <span class="firstname">
906               R. L.
907             </span> <span class="surname">
908               Rivest
909             </span>, and <span class="firstname">
910               C.
911             </span> <span class="surname">
912               Stein
913             </span>. </span><span class="publisher"><span class="publishername">
914           MIT Press
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">
918         1998
919       . </span><span class="authorgroup"><span class="firstname">
920               D.
921             </span> <span class="surname">
922               Dubashi
923             </span> and <span class="firstname">
924               D.
925             </span> <span class="surname">
926               Ranjan
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">
932         1979
933       . </span><span class="authorgroup"><span class="firstname">
934               R.
935             </span> <span class="surname">
936               Fagin
937             </span>, <span class="firstname">
938               J.
939             </span> <span class="surname">
940               Nievergelt
941             </span>, <span class="firstname">
942               N.
943             </span> <span class="surname">
944               Pippenger
945             </span>, and <span class="firstname">
946               H. R.
947             </span> <span class="surname">
948               Strong
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
954         </a>
955       </em>. </span><span class="date">
956         2000
957       . </span><span class="author"><span class="firstname">
958             Jean-Christophe
959           </span> <span class="surname">
960             Filliatre
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
964         </a>
965       </em>. </span><span class="date">
966         1986
967       . </span><span class="authorgroup"><span class="firstname">
968               M. L.
969             </span> <span class="surname">
970               Fredman
971             </span>, <span class="firstname">
972               R.
973             </span> <span class="surname">
974               Sedgewick
975             </span>, <span class="firstname">
976               D. D.
977             </span> <span class="surname">
978               Sleator
979             </span>, and <span class="firstname">
980               R. E.
981             </span> <span class="surname">
982               Tarjan
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">
986         1995
987       . </span><span class="authorgroup"><span class="firstname">
988               E.
989             </span> <span class="surname">
990               Gamma
991             </span>, <span class="firstname">
992               R.
993             </span> <span class="surname">
994               Helm
995             </span>, <span class="firstname">
996               R.
997             </span> <span class="surname">
998               Johnson
999             </span>, and <span class="firstname">
1000               J.
1001             </span> <span class="surname">
1002               Vlissides
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">
1008         1986
1009       . </span><span class="authorgroup"><span class="firstname">
1010               A. K.
1011             </span> <span class="surname">
1012               Garg
1013             </span> and <span class="firstname">
1014               C. C.
1015             </span> <span class="surname">
1016               Gotlieb
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">
1022         May 2002
1023       . </span><span class="authorgroup"><span class="firstname">
1024               J.
1025             </span> <span class="surname">
1026               Hyslop
1027             </span> and <span class="firstname">
1028               Herb
1029             </span> <span class="surname">
1030               Sutter
1031             </span>. </span><span class="publisher"><span class="publishername">
1032           C++ Report
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">
1036         2001
1037       . </span><span class="author"><span class="firstname">
1038             N. M.
1039           </span> <span class="surname">
1040             Jossutis
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
1046         </a>
1047       </em>. </span><span class="date">
1048         1999
1049       . </span><span class="authorgroup"><span class="firstname">
1050               Haim
1051             </span> <span class="surname">
1052               Kaplan
1053             </span> and <span class="firstname">
1054               Robert E.
1055             </span> <span class="surname">
1056               Tarjan
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">
1060         October 2000
1061       . </span><span class="authorgroup"><span class="firstname">
1062               Angelika
1063             </span> <span class="surname">
1064               Langer
1065             </span> and <span class="firstname">
1066               Klaus
1067             </span> <span class="surname">
1068               Kleft
1069             </span>. </span><span class="publisher"><span class="publishername">
1070           C/C++ Users Jornal
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">
1074         1998
1075       . </span><span class="author"><span class="firstname">
1076             D. E.
1077           </span> <span class="surname">
1078             Knuth
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">
1084         May 1998
1085       . </span><span class="author"><span class="firstname">
1086             B.
1087           </span> <span class="surname">
1088             Liskov
1089           </span>. </span><span class="publisher"><span class="publishername">
1090           SIGPLAN Notices 23
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">
1094         June 1980
1095       . </span><span class="author"><span class="firstname">
1096             W.
1097           </span> <span class="surname">
1098             Litwin
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
1104         </a>
1105       </em>. </span><span class="date">
1106         2005
1107       . </span><span class="author"><span class="firstname">
1108             Maverik
1109           </span> <span class="surname">
1110             Woo
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">
1114         1996
1115       . </span><span class="author"><span class="firstname">
1116             Scott
1117           </span> <span class="surname">
1118             Meyers
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">
1124         2000
1125       . </span><span class="author"><span class="firstname">
1126             Scott
1127           </span> <span class="surname">
1128             Meyers
1129           </span>. </span><span class="publisher"><span class="publishername">
1130           C/C++ Users Journal
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">
1134         2001
1135       . </span><span class="author"><span class="firstname">
1136             Scott
1137           </span> <span class="surname">
1138             Meyers
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">
1144         2003
1145       . </span><span class="author"><span class="firstname">
1146             Scott
1147           </span> <span class="surname">
1148             Meyers
1149           </span>. </span><span class="publisher"><span class="publishername">
1150           C/C++ Users Journal
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">
1154         2003
1155       . </span><span class="authorgroup"><span class="firstname">
1156               R.
1157             </span> <span class="surname">
1158               Motwani
1159             </span> and <span class="firstname">
1160               P.
1161             </span> <span class="surname">
1162               Raghavan
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
1168         </a>
1169       </em>. </span><span class="publisher"><span class="publishername">
1170           Microsoft
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">
1174         1995
1175       . </span><span class="author"><span class="firstname">
1176             David R.
1177           </span> <span class="surname">
1178             Musser
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">
1182         1996
1183       . </span><span class="authorgroup"><span class="firstname">
1184               David R.
1185             </span> <span class="surname">
1186               Musser
1187             </span> and <span class="firstname">
1188               A.
1189             </span> <span class="surname">
1190               Saini
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
1195         </a>
1196       </em>. </span><span class="date">
1197         January 1996
1198       . </span><span class="author"><span class="firstname">
1199             Mark
1200           </span> <span class="surname">
1201             Nelson
1202           </span>. </span><span class="publisher"><span class="publishername">
1203           Dr. Dobbs Journal
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">
1207         September 1998
1208       . </span><span class="authorgroup"><span class="firstname">
1209               C.
1210             </span> <span class="surname">
1211               Okasaki
1212             </span> and <span class="firstname">
1213               A.
1214             </span> <span class="surname">
1215               Gill
1216             </span>. </span><span class="publisher"><span class="publishername">
1217           In Workshop on ML
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
1221         </a>
1222       </em>. </span><span class="author"><span class="firstname">
1223             Matt
1224           </span> <span class="surname">
1225             Austern
1226           </span>. </span><span class="publisher"><span class="publishername">
1227           SGI
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">
1230           select
1231         </a>
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">
1235         1984
1236       . </span><span class="authorgroup"><span class="firstname">
1237               D. D.
1238             </span> <span class="surname">
1239               Sleator
1240             </span> and <span class="firstname">
1241               R. E.
1242             </span> <span class="surname">
1243               Tarjan
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">
1249         1985
1250       . </span><span class="authorgroup"><span class="firstname">
1251               D. D.
1252             </span> <span class="surname">
1253               Sleator
1254             </span> and <span class="firstname">
1255               R. E.
1256             </span> <span class="surname">
1257               Tarjan
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">
1263         1984
1264       . </span><span class="authorgroup"><span class="firstname">
1265               A. A.
1266             </span> <span class="surname">
1267               Stepanov
1268             </span> and <span class="firstname">
1269               M.
1270             </span> <span class="surname">
1271               Lee
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">
1275         1997
1276       . </span><span class="author"><span class="firstname">
1277             Bjarne
1278           </span> <span class="surname">
1279             Stroustrup
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">
1285         2002
1286       . </span><span class="authorgroup"><span class="firstname">
1287               D.
1288             </span> <span class="surname">
1289               Vandevoorde
1290             </span> and <span class="firstname">
1291               N. M.
1292             </span> <span class="surname">
1293               Josuttis
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
1299         </a>
1300       </em>. </span><span class="date">
1301         1996
1302       . </span><span class="author"><span class="firstname">
1303             C. A.
1304           </span> <span class="surname">
1305             Wickland
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>