| 1 |
742 |
jeremybenn |
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
|
| 2 |
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
|
| 3 |
|
|
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Chapter 22. Policy-Based Data Structures</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content=" 	ISO C++ , 	policy , 	container , 	data , 	structure , 	associated , 	tree , 	trie , 	hash , 	metaprogramming "/><meta name="keywords" content=" ISO C++ , library "/><meta name="keywords" content=" ISO C++ , runtime , library "/><link rel="home" href="../index.html" title="The GNU C++ Library"/><link rel="up" href="extensions.html" title="Part III. Extensions"/><link rel="prev" href="bk01pt03ch21s02.html" title="Implementation"/><link rel="next" href="policy_data_structures_using.html" title="Using"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 22. Policy-Based Data Structures</th></tr><tr><td align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><th width="60%" align="center">Part III.
|
| 4 |
|
|
Extensions
|
| 5 |
|
|
|
| 6 |
|
|
</th><td 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"/>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"><a id="pbds.intro"/>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"/>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"/>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<typename Cntnr>
|
| 118 |
|
|
void
|
| 119 |
|
|
some_op_sequence(Cntnr& 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"/>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"/>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"/>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"/>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"><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>.
|
| 233 |
|
|
|
| 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="id516222"/><p class="title"><strong>Figure 22.1. Node Invariants</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_node_invariants.png" style="text-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"/>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="id516278"/><p class="title"><strong>Figure 22.2. Underlying Associative Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_different_underlying_dss_1.png" style="text-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<class Cntnr>
|
| 280 |
|
|
int
|
| 281 |
|
|
some_op_sequence(Cntnr &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"><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"/>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">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"/>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="id516541"/><p class="title"><strong>Figure 22.3. Range Iteration in Different Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_point_iterators_range_ops_1.png" style="text-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"/>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="id516665"/><p class="title"><strong>Figure 22.4. Point Iteration in Hash Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_point_iterators_range_ops_2.png" style="text-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"/>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="id516742"/><p class="title"><strong>Figure 22.5. Effect of erase in different underlying data structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_invalidation_guarantee_erase.png" style="text-align: middle" alt="Effect of erase in different underlying data structures"/></div></div></div><br class="figure-break"/><div class="orderedlist"><ol class="orderedlist"><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"/>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"/><code class="function">erase</code></h6></div></div></div><div class="orderedlist"><ol class="orderedlist"><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();
|
| 497 |
|
|
|
| 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<
|
| 525 |
|
|
class Pred>
|
| 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"/>
|
| 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"/>
|
| 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<class It>
|
| 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<="><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.compare"/>
|
| 581 |
|
|
<code class="function">operator==</code> and <code class="function">operator<=</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<=</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"/>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"/>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"><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<int> p;
|
| 620 |
|
|
priority_queue<int>::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"><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"/>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="id517306"/><p class="title"><strong>Figure 22.6. Underlying Priority Queue Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_different_underlying_dss_2.png" style="text-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"/>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"><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<std::vector<std::string>
|
| 733 |
|
|
> ></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<std::deque<int> >
|
| 739 |
|
|
></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"><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">&p.top()</code> and
|
| 750 |
|
|
<code class="function">&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"/>
|
| 777 |
|
|
Bibliography
|
| 778 |
|
|
</h2></div></div></div><div class="biblioentry" title="STL Exception Handling Contract"><a id="biblio.abrahams97exception"/><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">
|
| 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"/><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"/><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"/><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"/><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">
|
| 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"/><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"/><p>[biblio.dawestimer] <span class="title"><em>
|
| 842 |
|
|
<a class="link" href="www.boost.org/doc/libs/release/libs/timer/">
|
| 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"/><p>[biblio.clearypool] <span class="title"><em>
|
| 852 |
|
|
<a class="link" href="www.boost.org/doc/libs/release/libs/pool/">
|
| 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"/><p>[biblio.maddocktraits] <span class="title"><em>
|
| 862 |
|
|
<a class="link" href="www.boost.org/doc/libs/release/libs/type_traits/">
|
| 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"/><p>[biblio.brodal96priority] <span class="title"><em>
|
| 876 |
|
|
<a class="link" href="http://portal.acm.org/citation.cfm?id=313883">
|
| 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"/><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"/><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"/><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"/><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"/><p>[biblio.filliatre2000ptset] <span class="title"><em>
|
| 956 |
|
|
<a class="link" href="http://cristal.inria.fr/~frisch/icfp06_contest/advtr/applyOmatic/ptset.ml">
|
| 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"/><p>[biblio.fredman86pairing] <span class="title"><em>
|
| 966 |
|
|
<a class="link" href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf">
|
| 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"/><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"/><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"/><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"/><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"/><p>[biblio.kt99fat_heaps] <span class="title"><em>
|
| 1048 |
|
|
<a class="link" href="http://www.cs.princeton.edu/research/techreps/TR-597-99">
|
| 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"/><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"/><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"/><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"/><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"/><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">
|
| 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"/><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"/><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"/><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"/><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"/><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"/><p>[biblio.mscom] <span class="title"><em>
|
| 1170 |
|
|
<a class="link" href="http://www.microsoft.com/com">
|
| 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"/><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"/><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"/><p>[biblio.nelson96stlpq] <span class="title"><em>
|
| 1198 |
|
|
<a class="link" href="http://www.dogma.net/markn/articles/pq_stl/priority.htm">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"/><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"/><p>[biblio.sgi_stl] <span class="title"><em>
|
| 1223 |
|
|
<a class="link" href="http://www.sgi.com/tech/stl">
|
| 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"/><p>[biblio.select_man] <span class="title"><em>
|
| 1233 |
|
|
<a class="link" href="http://www.scit.wlv.ac.uk/cgi-bin/mansec?3C+select">
|
| 1234 |
|
|
select
|
| 1235 |
|
|
</a>
|
| 1236 |
|
|
</em>. </span></p></div><div class="biblioentry" title="Amortized Efficiency of List Update Problems"><a id="biblio.sleator84amortized"/><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"/><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"/><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"/><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"/><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"/><p>[biblio.wickland96thirty] <span class="title"><em>
|
| 1301 |
|
|
<a class="link" href="http://myweb.wvnet.edu/~gsa00121/books/amongdead30.zip">
|
| 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 align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><td align="center"><a accesskey="u" href="extensions.html">Up</a></td><td align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr><tr><td align="left" valign="top">Implementation </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Using</td></tr></table></div></body></html>
|
