libstdc++-v3/docs/html/ext/pb_ds/introduction.html

   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>
  45 template&lt;typename Cntnr&gt;
  46   void
  47   some_op_sequence(Cntnr&amp; r_cnt)
  48   {
  49     ...
  50   }
  51 </pre>
  52
  53 then what can one assume about <tt>Cntnr</tt>? The answer
  54 varies according to its underlying data structure. If the
  55 underlying data structure of <tt>Cntnr</tt> is based on a tree or
  56 trie, then the order of elements is well defined; otherwise, it is
  57 not, in general. If the underlying data structure of <tt>Cntnr</tt>
  58 is based on a collision-chaining hash table, then modifying
  59 r_<tt>Cntnr</tt> will not invalidate its iterators' order; if the
  60 underlying data structure is a probing hash table, then this is not
  61 the case. If the underlying data structure is based on a tree or
  62 trie, then <tt>r_cnt</tt> can efficiently be split; otherwise, it
  63 cannot, in general. If the underlying data structure is a red-black
  64 tree, then splitting <tt>r_cnt</tt> is exception-free; if it is an
  65 ordered-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>