1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta name="generator" content=
"HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
<title>Introduction</title>
<meta http-equiv="Content-Type" content=
"text/html; charset=us-ascii" />
</head>
<body>
<div id="page">
<h1>Introduction</h1>
<p>This section describes what problems the library attempts to
solve. <a href="motivation.html">Motivation</a> describes the
reasons we think it solves these problems better than similar
libraries.</p>
<h2><a name="assoc" id="assoc">Associative Containers</a></h2>
<ol>
<li>Associative containers depend on their policies to a very
large extent. Implicitly hard-wiring policies can hamper their
performance and limit their functionality. An efficient
hash-based container, for example, requires policies for
testing key equivalence, hashing keys, translating hash
values into positions within the hash table, and determining
when and how to resize the table internally. A tree-based
container can efficiently support order statistics,
<i>i.e.</i>, the ability to query what is the order of each
key within the sequence of keys in the container, but only if
the container is supplied with a policy to internally update
meta-data. There are many other such examples.<p></p></li>
<li>Ideally, all associative containers would share the same
interface. Unfortunately, underlying data structures and
mapping semantics differentiate between different containers.
For example, suppose one writes a generic function
manipulating an associative container <tt>Cntnr</tt>:
<pre>
template<typename Cntnr>
void
some_op_sequence(Cntnr& r_cnt)
{
...
}
</pre>
then what can one assume about <tt>Cntnr</tt>? The answer
varies according to its underlying data structure. If the
underlying data structure of <tt>Cntnr</tt> is based on a tree or
trie, then the order of elements is well defined; otherwise, it is
not, in general. If the underlying data structure of <tt>Cntnr</tt>
is based on a collision-chaining hash table, then modifying
r_<tt>Cntnr</tt> will not invalidate its iterators' order; if the
underlying data structure is a probing hash table, then this is not
the case. If the underlying data structure is based on a tree or
trie, then <tt>r_cnt</tt> can efficiently be split; otherwise, it
cannot, in general. If the underlying data structure is a red-black
tree, then splitting <tt>r_cnt</tt> is exception-free; if it is an
ordered-vector tree, exceptions can be thrown.
<p></p></li>
</ol>
<h2><a name="pq" id="pq">Priority Queues</a></h2>
<p>Priority queues are useful when one needs to efficiently
access a minimum (or maximum) value as the set of values
changes.</p>
<ol>
<li>Most useful data structures for priority queues have a
relatively simple structure, as they are geared toward
relatively simple requirements. Unfortunately, these structures
do not support access to an arbitrary value, which turns out to
be necessary in many algorithms. Say, decreasing an arbitrary
value in a graph algorithm. Therefore, some extra mechanism is
necessary and must be invented for accessing arbitrary
values. There are at least two alternatives: embedding an
associative container in a priority queue, or allowing
cross-referencing through iterators. The first solution adds
significant overhead; the second solution requires a precise
definition of iterator invalidation. Which is the next
point...<p></p></li>
<li>Priority queues, like hash-based containers, store values in
an order that is meaningless and undefined externally. For
example, a <tt>push</tt> operation can internally reorganize the
values. Because of this characteristic, describing a priority
queues' iterator is difficult: on one hand, the values to which
iterators point can remain valid, but on the other, the logical
order of iterators can change unpredictably.<p></p></li>
<li>Roughly speaking, any element that is both inserted to a
priority queue (<i>e.g.</i>, through <tt>push</tt>) and removed
from it (<i>e.g.</i>, through <tt>pop</tt>), incurs a
logarithmic overhead (in the amortized sense). Different
underlying data structures place the actual cost differently:
some are optimized for amortized complexity, whereas others
guarantee that specific operations only have a constant
cost. One underlying data structure might be chosen if modifying
a value is frequent (Dijkstra's shortest-path algorithm),
whereas a different one might be chosen
otherwise. Unfortunately, an array-based binary heap - an
underlying data structure that optimizes (in the amortized
sense) <tt>push</tt> and <tt>pop</tt> operations, differs from
the others in terms of its invalidation guarantees. Other design
decisions also impact the cost and placement of the overhead, at
the expense of more difference in the the kinds of operations
that the underlying data structure can support. These
differences pose a challenge when creating a uniform interface
for priority queues.<p></p></li>
</ol>
</div>
</body>
</html>
|
