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<typename Cntnr> 46 void 47 some_op_sequence(Cntnr& 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