OSDN Git Service

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