| <!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> |
