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