diff options
Diffstat (limited to 'libstdc++-v3/doc/html/ext/pb_ds/introduction.html')
| -rw-r--r-- | libstdc++-v3/doc/html/ext/pb_ds/introduction.html | 120 |
1 files changed, 0 insertions, 120 deletions
diff --git a/libstdc++-v3/doc/html/ext/pb_ds/introduction.html b/libstdc++-v3/doc/html/ext/pb_ds/introduction.html deleted file mode 100644 index b3ccbd76aee..00000000000 --- a/libstdc++-v3/doc/html/ext/pb_ds/introduction.html +++ /dev/null @@ -1,120 +0,0 @@ -<!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> |
