libstdc++-v3/doc/html/manual/policy_data_structures.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml"><head><title>Chapter 22. Policy-Based Data Structures</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content="&#10;&#9;ISO C++&#10;      , &#10;&#9;policy&#10;      , &#10;&#9;container&#10;      , &#10;&#9;data&#10;      , &#10;&#9;structure&#10;      , &#10;&#9;associated&#10;      , &#10;&#9;tree&#10;      , &#10;&#9;trie&#10;      , &#10;&#9;hash&#10;      , &#10;&#9;metaprogramming&#10;      "/><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    "/><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      runtime&#10;    , &#10;      library&#10;    "/><link rel="home" href="../index.html" title="The GNU C++ Library"/><link rel="up" href="extensions.html" title="Part III.  Extensions"/><link rel="prev" href="bk01pt03ch21s02.html" title="Implementation"/><link rel="next" href="policy_data_structures_using.html" title="Using"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 22. Policy-Based Data Structures</th></tr><tr><td align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><th width="60%" align="center">Part III.
   4   Extensions
   5
   6 </th><td align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr></table><hr/></div><div class="chapter" title="Chapter 22. Policy-Based Data Structures"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.containers.pbds"/>Chapter 22. Policy-Based Data Structures</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
   7             Configuring via Template Parameters
   8           </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.traits">
   9             Querying Container Attributes
  10           </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.point_range_iteration">
  11             Point and Range Iteration
  12           </a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples">Examples</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.basic">Intermediate Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.query">Querying with <code class="classname">container_traits</code> </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container">By Container Method</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container.hash">Hash-Based</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container.branch">Branch-Based</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.examples.container.priority_queue">Priority Queues</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts">Concepts</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.null_type">Null Policy Classes</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.associative_semantics">Map and Set Semantics</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#concepts.associative_semantics.set_vs_map">
  13             Distinguishing Between Maps and Sets
  14           </a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#concepts.associative_semantics.multi">Alternatives to <code class="classname">std::multiset</code> and <code class="classname">std::multimap</code></a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.iterator_semantics">Iterator Semantics</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#concepts.iterator_semantics.point_and_range">Point and Range Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#concepts.iterator_semantics.both">Distinguishing Point and Range Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.invalidation">Invalidation Guarantees</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.concepts.genericity">Genericity</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#concepts.genericity.tag">Tag</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#concepts.genericity.traits">Traits</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container">By Container</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.hash">hash</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.hash.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.hash.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.tree">tree</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.tree.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.tree.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.trie">Trie</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.trie.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.trie.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.list">List</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.list.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.list.details">Details</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures_design.html#pbds.design.container.priority_queue">Priority Queue</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_design.html#container.priority_queue.interface">Interface</a></span></dt><dt><span class="section"><a href="policy_data_structures_design.html#container.priority_queue.details">Details</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html">Testing</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#pbds.test.regression">Regression</a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#pbds.test.performance">Performance</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash">Hash-Based</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.text_find">
  15           Text <code class="function">find</code>
  16         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_find">
  17           Integer <code class="function">find</code>
  18         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_find">
  19           Integer Subscript <code class="function">find</code>
  20         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_insert">
  21           Integer Subscript <code class="function">insert</code>
  22         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.zlob_int_find">
  23           Integer <code class="function">find</code> with Skewed-Distribution
  24         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.erase_mem">
  25           Erase Memory Use
  26         </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch">Branch-Based</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_insert">
  27           Text <code class="function">insert</code>
  28         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_find">
  29           Text <code class="function">find</code>
  30         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_lor_find">
  31           Text <code class="function">find</code> with Locality-of-Reference
  32         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.split_join">
  33           <code class="function">split</code> and <code class="function">join</code>
  34         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.order_statistics">
  35           Order-Statistics
  36         </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap">Multimap</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_find_small">
  37           Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios
  38         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_find_large">
  39           Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios
  40         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_small">
  41           Text <code class="function">insert</code> with Small
  42           Secondary-to-Primary Key Ratios
  43         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_large">
  44           Text <code class="function">insert</code> with Small
  45           Secondary-to-Primary Key Ratios
  46         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_small">
  47           Text <code class="function">insert</code> with Small
  48           Secondary-to-Primary Key Ratios Memory Use
  49         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_large">
  50           Text <code class="function">insert</code> with Small
  51           Secondary-to-Primary Key Ratios Memory Use
  52         </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue">Priority Queue</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_push">
  53           Text <code class="function">push</code>
  54         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_push_pop">
  55           Text <code class="function">push</code> and <code class="function">pop</code>
  56         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push">
  57           Integer <code class="function">push</code>
  58         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push_pop">
  59           Integer <code class="function">push</code>
  60         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_pop">
  61           Text <code class="function">pop</code> Memory Use
  62         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_join">
  63           Text <code class="function">join</code>
  64         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_up">
  65           Text <code class="function">modify</code> Up
  66         </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_down">
  67           Text <code class="function">modify</code> Down
  68         </a></span></dt></dl></dd><dt><span class="section"><a href="policy_based_data_structures_test.html#pbds.test.performance.observations">Observations</a></span></dt><dd><dl><dt><span class="section"><a href="policy_based_data_structures_test.html#observations.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#observations.priority_queue">Priority_Queue</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_biblio.html">Acknowledgments</a></span></dt><dt><span class="bibliography"><a href="policy_data_structures.html#pbds.biblio">
  69         Bibliography
  70       </a></span></dt></dl></div><div class="section" title="Intro"><div class="titlepage"><div><div><h2 class="title"><a id="pbds.intro"/>Intro</h2></div></div></div><p>
  71       This is a library of policy-based elementary data structures:
  72       associative containers and priority queues. It is designed for
  73       high-performance, flexibility, semantic safety, and conformance to
  74       the corresponding containers in <code class="literal">std</code> and
  75       <code class="literal">std::tr1</code> (except for some points where it differs
  76       by design).
  77     </p><p>
  78     </p><div class="section" title="Performance Issues"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.intro.issues"/>Performance Issues</h3></div></div></div><p>
  79       </p><p>
  80         An attempt is made to categorize the wide variety of possible
  81         container designs in terms of performance-impacting factors. These
  82         performance factors are translated into design policies and
  83         incorporated into container design.
  84       </p><p>
  85         There is tension between unravelling factors into a coherent set of
  86         policies. Every attempt is made to make a minimal set of
  87         factors. However, in many cases multiple factors make for long
  88         template names. Every attempt is made to alias and use typedefs in
  89         the source files, but the generated names for external symbols can
  90         be large for binary files or debuggers.
  91       </p><p>
  92         In many cases, the longer names allow capabilities and behaviours
  93         controlled by macros to also be unamibiguously emitted as distinct
  94         generated names.
  95       </p><p>
  96         Specific issues found while unraveling performance factors in the
  97         design of associative containers and priority queues follow.
  98       </p><div class="section" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.associative"/>Associative</h4></div></div></div><p>
  99           Associative containers depend on their composite policies to a very
 100           large extent. Implicitly hard-wiring policies can hamper their
 101           performance and limit their functionality. An efficient hash-based
 102           container, for example, requires policies for testing key
 103           equivalence, hashing keys, translating hash values into positions
 104           within the hash table, and determining when and how to resize the
 105           table internally. A tree-based container can efficiently support
 106           order statistics, i.e. the ability to query what is the order of
 107           each key within the sequence of keys in the container, but only if
 108           the container is supplied with a policy to internally update
 109           meta-data. There are many other such examples.
 110         </p><p>
 111           Ideally, all associative containers would share the same
 112           interface. Unfortunately, underlying data structures and mapping
 113           semantics differentiate between different containers. For example,
 114           suppose one writes a generic function manipulating an associative
 115           container.
 116         </p><pre class="programlisting">
 117           template&lt;typename Cntnr&gt;
 118           void
 119           some_op_sequence(Cntnr&amp; r_cnt)
 120           {
 121           ...
 122           }
 123         </pre><p>
 124           Given this, then what can one assume about the instantiating
 125           container? The answer varies according to its underlying data
 126           structure. If the underlying data structure of
 127           <code class="literal">Cntnr</code> is based on a tree or trie, then the order
 128           of elements is well defined; otherwise, it is not, in general. If
 129           the underlying data structure of <code class="literal">Cntnr</code> is based
 130           on a collision-chaining hash table, then modifying
 131           r_<code class="literal">Cntnr</code> will not invalidate its iterators' order;
 132           if the underlying data structure is a probing hash table, then this
 133           is not the case. If the underlying data structure is based on a tree
 134           or trie, then a reference to the container can efficiently be split;
 135           otherwise, it cannot, in general. If the underlying data structure
 136           is a red-black tree, then splitting a reference to the container is
 137           exception-free; if it is an ordered-vector tree, exceptions can be
 138           thrown.
 139         </p></div><div class="section" title="Priority Que"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.priority_queue"/>Priority Que</h4></div></div></div><p>
 140           Priority queues are useful when one needs to efficiently access a
 141           minimum (or maximum) value as the set of values changes.
 142         </p><p>
 143           Most useful data structures for priority queues have a relatively
 144           simple structure, as they are geared toward relatively simple
 145           requirements. Unfortunately, these structures do not support access
 146           to an arbitrary value, which turns out to be necessary in many
 147           algorithms. Say, decreasing an arbitrary value in a graph
 148           algorithm. Therefore, some extra mechanism is necessary and must be
 149           invented for accessing arbitrary values. There are at least two
 150           alternatives: embedding an associative container in a priority
 151           queue, or allowing cross-referencing through iterators. The first
 152           solution adds significant overhead; the second solution requires a
 153           precise definition of iterator invalidation. Which is the next
 154           point...
 155         </p><p>
 156           Priority queues, like hash-based containers, store values in an
 157           order that is meaningless and undefined externally. For example, a
 158           <code class="code">push</code> operation can internally reorganize the
 159           values. Because of this characteristic, describing a priority
 160           queues' iterator is difficult: on one hand, the values to which
 161           iterators point can remain valid, but on the other, the logical
 162           order of iterators can change unpredictably.
 163         </p><p>
 164           Roughly speaking, any element that is both inserted to a priority
 165           queue (e.g. through <code class="code">push</code>) and removed
 166           from it (e.g., through <code class="code">pop</code>), incurs a
 167           logarithmic overhead (in the amortized sense). Different underlying
 168           data structures place the actual cost differently: some are
 169           optimized for amortized complexity, whereas others guarantee that
 170           specific operations only have a constant cost. One underlying data
 171           structure might be chosen if modifying a value is frequent
 172           (Dijkstra's shortest-path algorithm), whereas a different one might
 173           be chosen otherwise. Unfortunately, an array-based binary heap - an
 174           underlying data structure that optimizes (in the amortized sense)
 175           <code class="code">push</code> and <code class="code">pop</code> operations, differs from the
 176           others in terms of its invalidation guarantees. Other design
 177           decisions also impact the cost and placement of the overhead, at the
 178           expense of more difference in the the kinds of operations that the
 179           underlying data structure can support. These differences pose a
 180           challenge when creating a uniform interface for priority queues.
 181         </p></div></div><div class="section" title="Goals"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.intro.motivation"/>Goals</h3></div></div></div><p>
 182         Many fine associative-container libraries were already written,
 183         most notably, the C++ standard's associative containers. Why
 184         then write another library? This section shows some possible
 185         advantages of this library, when considering the challenges in
 186         the introduction. Many of these points stem from the fact that
 187         the ISO C++ process introduced associative-containers in a
 188         two-step process (first standardizing tree-based containers,
 189         only then adding hash-based containers, which are fundamentally
 190         different), did not standardize priority queues as containers,
 191         and (in our opinion) overloads the iterator concept.
 192       </p><div class="section" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.motivation.associative"/>Associative</h4></div></div></div><p>
 193         </p><div class="section" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.policy"/>Policy Choices</h5></div></div></div><p>
 194             Associative containers require a relatively large number of
 195             policies to function efficiently in various settings. In some
 196             cases this is needed for making their common operations more
 197             efficient, and in other cases this allows them to support a
 198             larger set of operations
 199           </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 200                 Hash-based containers, for example, support look-up and
 201                 insertion methods (<code class="function">find</code> and
 202                 <code class="function">insert</code>). In order to locate elements
 203                 quickly, they are supplied a hash functor, which instruct
 204                 how to transform a key object into some size type; a hash
 205                 functor might transform <code class="constant">"hello"</code>
 206                 into <code class="constant">1123002298</code>. A hash table, though,
 207                 requires transforming each key object into some size-type
 208                 type in some specific domain; a hash table with a 128-long
 209                 table might transform <code class="constant">"hello"</code> into
 210                 position <code class="constant">63</code>. The policy by which the
 211                 hash value is transformed into a position within the table
 212                 can dramatically affect performance.  Hash-based containers
 213                 also do not resize naturally (as opposed to tree-based
 214                 containers, for example). The appropriate resize policy is
 215                 unfortunately intertwined with the policy that transforms
 216                 hash value into a position within the table.
 217               </p></li><li class="listitem"><p>
 218                 Tree-based containers, for example, also support look-up and
 219                 insertion methods, and are primarily useful when maintaining
 220                 order between elements is important. In some cases, though,
 221                 one can utilize their balancing algorithms for completely
 222                 different purposes.
 223               </p><p>
 224                 Figure A shows a tree whose each node contains two entries:
 225                 a floating-point key, and some size-type
 226                 <span class="emphasis"><em>metadata</em></span> (in bold beneath it) that is
 227                 the number of nodes in the sub-tree. (The root has key 0.99,
 228                 and has 5 nodes (including itself) in its sub-tree.) A
 229                 container based on this data structure can obviously answer
 230                 efficiently whether 0.3 is in the container object, but it
 231                 can also answer what is the order of 0.3 among all those in
 232                 the container object: see <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>.
 233
 234               </p><p>
 235                 As another example, Figure B shows a tree whose each node
 236                 contains two entries: a half-open geometric line interval,
 237                 and a number <span class="emphasis"><em>metadata</em></span> (in bold beneath
 238                 it) that is the largest endpoint of all intervals in its
 239                 sub-tree.  (The root describes the interval <code class="constant">[20,
 240                 36)</code>, and the largest endpoint in its sub-tree is
 241                 99.) A container based on this data structure can obviously
 242                 answer efficiently whether <code class="constant">[3, 41)</code> is
 243                 in the container object, but it can also answer efficiently
 244                 whether the container object has intervals that intersect
 245                 <code class="constant">[3, 41)</code>. These types of queries are
 246                 very useful in geometric algorithms and lease-management
 247                 algorithms.
 248               </p><p>
 249                 It is important to note, however, that as the trees are
 250                 modified, their internal structure changes. To maintain
 251                 these invariants, one must supply some policy that is aware
 252                 of these changes.  Without this, it would be better to use a
 253                 linked list (in itself very efficient for these purposes).
 254               </p></li></ol></div><div class="figure"><a id="id573272"/><p class="title"><strong>Figure 22.1. Node Invariants</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_node_invariants.png" style="text-align: middle" alt="Node Invariants"/></div></div></div><br class="figure-break"/></div><div class="section" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.underlying"/>Underlying Data Structures</h5></div></div></div><p>
 255             The standard C++ library contains associative containers based on
 256             red-black trees and collision-chaining hash tables. These are
 257             very useful, but they are not ideal for all types of
 258             settings.
 259           </p><p>
 260             The figure below shows the different underlying data structures
 261             currently supported in this library.
 262           </p><div class="figure"><a id="id573328"/><p class="title"><strong>Figure 22.2. Underlying Associative Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_different_underlying_dss_1.png" style="text-align: middle" alt="Underlying Associative Data Structures"/></div></div></div><br class="figure-break"/><p>
 263             A shows a collision-chaining hash-table, B shows a probing
 264             hash-table, C shows a red-black tree, D shows a splay tree, E shows
 265             a tree based on an ordered vector(implicit in the order of the
 266             elements), F shows a PATRICIA trie, and G shows a list-based
 267             container with update policies.
 268           </p><p>
 269             Each of these data structures has some performance benefits, in
 270             terms of speed, size or both. For now, note that vector-based trees
 271             and probing hash tables manipulate memory more efficiently than
 272             red-black trees and collision-chaining hash tables, and that
 273             list-based associative containers are very useful for constructing
 274             "multimaps".
 275           </p><p>
 276             Now consider a function manipulating a generic associative
 277             container,
 278           </p><pre class="programlisting">
 279             template&lt;class Cntnr&gt;
 280             int
 281             some_op_sequence(Cntnr &amp;r_cnt)
 282             {
 283             ...
 284             }
 285           </pre><p>
 286             Ideally, the underlying data structure
 287             of <code class="classname">Cntnr</code> would not affect what can be
 288             done with <code class="varname">r_cnt</code>.  Unfortunately, this is not
 289             the case.
 290           </p><p>
 291             For example, if <code class="classname">Cntnr</code>
 292             is <code class="classname">std::map</code>, then the function can
 293             use
 294           </p><pre class="programlisting">
 295             std::for_each(r_cnt.find(foo), r_cnt.find(bar), foobar)
 296           </pre><p>
 297             in order to apply <code class="classname">foobar</code> to all
 298             elements between <code class="classname">foo</code> and
 299             <code class="classname">bar</code>. If
 300             <code class="classname">Cntnr</code> is a hash-based container,
 301             then this call's results are undefined.
 302           </p><p>
 303             Also, if <code class="classname">Cntnr</code> is tree-based, the type
 304             and object of the comparison functor can be
 305             accessed. If <code class="classname">Cntnr</code> is hash based, these
 306             queries are nonsensical.
 307           </p><p>
 308             There are various other differences based on the container's
 309             underlying data structure. For one, they can be constructed by,
 310             and queried for, different policies. Furthermore:
 311           </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 312                 Containers based on C, D, E and F store elements in a
 313                 meaningful order; the others store elements in a meaningless
 314                 (and probably time-varying) order. By implication, only
 315                 containers based on C, D, E and F can
 316                 support <code class="function">erase</code> operations taking an
 317                 iterator and returning an iterator to the following element
 318                 without performance loss.
 319               </p></li><li class="listitem"><p>
 320                 Containers based on C, D, E, and F can be split and joined
 321                 efficiently, while the others cannot. Containers based on C
 322                 and D, furthermore, can guarantee that this is exception-free;
 323                 containers based on E cannot guarantee this.
 324               </p></li><li class="listitem"><p>
 325                 Containers based on all but E can guarantee that
 326                 erasing an element is exception free; containers based on E
 327                 cannot guarantee this. Containers based on all but B and E
 328                 can guarantee that modifying an object of their type does
 329                 not invalidate iterators or references to their elements,
 330                 while containers based on B and E cannot. Containers based
 331                 on C, D, and E can furthermore make a stronger guarantee,
 332                 namely that modifying an object of their type does not
 333                 affect the order of iterators.
 334               </p></li></ol></div><p>
 335             A unified tag and traits system (as used for the C++ standard
 336             library iterators, for example) can ease generic manipulation of
 337             associative containers based on different underlying data
 338             structures.
 339           </p></div><div class="section" title="Iterators"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.iterators"/>Iterators</h5></div></div></div><p>
 340             Iterators are centric to the design of the standard library
 341             containers, because of the container/algorithm/iterator
 342             decomposition that allows an algorithm to operate on a range
 343             through iterators of some sequence.  Iterators, then, are useful
 344             because they allow going over a
 345             specific <span class="emphasis"><em>sequence</em></span>.  The standard library
 346             also uses iterators for accessing a
 347             specific <span class="emphasis"><em>element</em></span>: when an associative
 348             container returns one through <code class="function">find</code>. The
 349             standard library consistently uses the same types of iterators
 350             for both purposes: going over a range, and accessing a specific
 351             found element. Before the introduction of hash-based containers
 352             to the standard library, this made sense (with the exception of
 353             priority queues, which are discussed later).
 354           </p><p>
 355             Using the standard associative containers together with
 356             non-order-preserving associative containers (and also because of
 357             priority-queues container), there is a possible need for
 358             different types of iterators for self-organizing containers:
 359             the iterator concept seems overloaded to mean two different
 360             things (in some cases). <em><span class="remark"> XXX
 361             "ds_gen.html#find_range"&gt;Design::Associative
 362             Containers::Data-Structure Genericity::Point-Type and Range-Type
 363             Methods</span></em>.
 364           </p><div class="section" title="Using Point Iterators for Range Operations"><div class="titlepage"><div><div><h6 class="title"><a id="associative.iterators.using"/>Using Point Iterators for Range Operations</h6></div></div></div><p>
 365               Suppose <code class="classname">cntnr</code> is some associative
 366               container, and say <code class="varname">c</code> is an object of
 367               type <code class="classname">cntnr</code>. Then what will be the outcome
 368               of
 369             </p><pre class="programlisting">
 370               std::for_each(c.find(1), c.find(5), foo);
 371             </pre><p>
 372               If <code class="classname">cntnr</code> is a tree-based container
 373               object, then an in-order walk will
 374               apply <code class="classname">foo</code> to the relevant elements,
 375               as in the graphic below, label A. If <code class="varname">c</code> is
 376               a hash-based container, then the order of elements between any
 377               two elements is undefined (and probably time-varying); there is
 378               no guarantee that the elements traversed will coincide with the
 379               <span class="emphasis"><em>logical</em></span> elements between 1 and 5, as in
 380               label B.
 381             </p><div class="figure"><a id="id573591"/><p class="title"><strong>Figure 22.3. Range Iteration in Different Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_point_iterators_range_ops_1.png" style="text-align: middle" alt="Node Invariants"/></div></div></div><br class="figure-break"/><p>
 382               In our opinion, this problem is not caused just because
 383               red-black trees are order preserving while
 384               collision-chaining hash tables are (generally) not - it
 385               is more fundamental. Most of the standard's containers
 386               order sequences in a well-defined manner that is
 387               determined by their <span class="emphasis"><em>interface</em></span>:
 388               calling <code class="function">insert</code> on a tree-based
 389               container modifies its sequence in a predictable way, as
 390               does calling <code class="function">push_back</code> on a list or
 391               a vector. Conversely, collision-chaining hash tables,
 392               probing hash tables, priority queues, and list-based
 393               containers (which are very useful for "multimaps") are
 394               self-organizing data structures; the effect of each
 395               operation modifies their sequences in a manner that is
 396               (practically) determined by their
 397               <span class="emphasis"><em>implementation</em></span>.
 398             </p><p>
 399               Consequently, applying an algorithm to a sequence obtained from most
 400               containers may or may not make sense, but applying it to a
 401               sub-sequence of a self-organizing container does not.
 402             </p></div><div class="section" title="Cost to Point Iterators to Enable Range Operations"><div class="titlepage"><div><div><h6 class="title"><a id="associative.iterators.cost"/>Cost to Point Iterators to Enable Range Operations</h6></div></div></div><p>
 403               Suppose <code class="varname">c</code> is some collision-chaining
 404               hash-based container object, and one calls
 405             </p><pre class="programlisting">c.find(3)</pre><p>
 406               Then what composes the returned iterator?
 407             </p><p>
 408               In the graphic below, label A shows the simplest (and
 409               most efficient) implementation of a collision-chaining
 410               hash table.  The little box marked
 411               <code class="classname">point_iterator</code> shows an object
 412               that contains a pointer to the element's node. Note that
 413               this "iterator" has no way to move to the next element (
 414               it cannot support
 415               <code class="function">operator++</code>). Conversely, the little
 416               box marked <code class="classname">iterator</code> stores both a
 417               pointer to the element, as well as some other
 418               information (the bucket number of the element). the
 419               second iterator, then, is "heavier" than the first one-
 420               it requires more time and space. If we were to use a
 421               different container to cross-reference into this
 422               hash-table using these iterators - it would take much
 423               more space. As noted above, nothing much can be done by
 424               incrementing these iterators, so why is this extra
 425               information needed?
 426             </p><p>
 427               Alternatively, one might create a collision-chaining hash-table
 428               where the lists might be linked, forming a monolithic total-element
 429               list, as in the graphic below, label B.  Here the iterators are as
 430               light as can be, but the hash-table's operations are more
 431               complicated.
 432             </p><div class="figure"><a id="id573715"/><p class="title"><strong>Figure 22.4. Point Iteration in Hash Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_point_iterators_range_ops_2.png" style="text-align: middle" alt="Point Iteration in Hash Data Structures"/></div></div></div><br class="figure-break"/><p>
 433               It should be noted that containers based on collision-chaining
 434               hash-tables are not the only ones with this type of behavior;
 435               many other self-organizing data structures display it as well.
 436             </p></div><div class="section" title="Invalidation Guarantees"><div class="titlepage"><div><div><h6 class="title"><a id="associative.iterators.invalidation"/>Invalidation Guarantees</h6></div></div></div><p>Consider the following snippet:</p><pre class="programlisting">
 437               it = c.find(3);
 438               c.erase(5);
 439             </pre><p>
 440               Following the call to <code class="classname">erase</code>, what is the
 441               validity of <code class="classname">it</code>: can it be de-referenced?
 442               can it be incremented?
 443             </p><p>
 444               The answer depends on the underlying data structure of the
 445               container. The graphic below shows three cases: A1 and A2 show
 446               a red-black tree; B1 and B2 show a probing hash-table; C1 and C2
 447               show a collision-chaining hash table.
 448             </p><div class="figure"><a id="id573793"/><p class="title"><strong>Figure 22.5. Effect of erase in different underlying data structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_invalidation_guarantee_erase.png" style="text-align: middle" alt="Effect of erase in different underlying data structures"/></div></div></div><br class="figure-break"/><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 449                   Erasing 5 from A1 yields A2. Clearly, an iterator to 3 can
 450                   be de-referenced and incremented. The sequence of iterators
 451                   changed, but in a way that is well-defined by the interface.
 452                 </p></li><li class="listitem"><p>
 453                   Erasing 5 from B1 yields B2. Clearly, an iterator to 3 is
 454                   not valid at all - it cannot be de-referenced or
 455                   incremented; the order of iterators changed in a way that is
 456                   (practically) determined by the implementation and not by
 457                   the interface.
 458                 </p></li><li class="listitem"><p>
 459                   Erasing 5 from C1 yields C2. Here the situation is more
 460                   complicated. On the one hand, there is no problem in
 461                   de-referencing <code class="classname">it</code>. On the other hand,
 462                   the order of iterators changed in a way that is
 463                   (practically) determined by the implementation and not by
 464                   the interface.
 465                 </p></li></ol></div><p>
 466               So in the standard library containers, it is not always possible
 467               to express whether <code class="varname">it</code> is valid or not. This
 468               is true also for <code class="function">insert</code>. Again, the
 469               iterator concept seems overloaded.
 470             </p></div></div><div class="section" title="Functional"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.functions"/>Functional</h5></div></div></div><p>
 471           </p><p>
 472             The design of the functional overlay to the underlying data
 473             structures differs slightly from some of the conventions used in
 474             the C++ standard.  A strict public interface of methods that
 475             comprise only operations which depend on the class's internal
 476             structure; other operations are best designed as external
 477             functions. (See <a class="xref" href="policy_data_structures.html#biblio.meyers02both" title="Class Template, Member Template - or Both?">[biblio.meyers02both]</a>).With this
 478             rubric, the standard associative containers lack some useful
 479             methods, and provide other methods which would be better
 480             removed.
 481           </p><div class="section" title="erase"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.erase"/><code class="function">erase</code></h6></div></div></div><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 482                   Order-preserving standard associative containers provide the
 483                   method
 484                 </p><pre class="programlisting">
 485                   iterator
 486                   erase(iterator it)
 487                 </pre><p>
 488                   which takes an iterator, erases the corresponding
 489                   element, and returns an iterator to the following
 490                   element. Also standardd hash-based associative
 491                   containers provide this method. This seemingly
 492                   increasesgenericity between associative containers,
 493                   since it is possible to use
 494                 </p><pre class="programlisting">
 495                   typename C::iterator it = c.begin();
 496                   typename C::iterator e_it = c.end();
 497
 498                   while(it != e_it)
 499                   it = pred(*it)? c.erase(it) : ++it;
 500                 </pre><p>
 501                   in order to erase from a container object <code class="varname">
 502                   c</code> all element which match a
 503                   predicate <code class="classname">pred</code>. However, in a
 504                   different sense this actually decreases genericity: an
 505                   integral implication of this method is that tree-based
 506                   associative containers' memory use is linear in the total
 507                   number of elements they store, while hash-based
 508                   containers' memory use is unbounded in the total number of
 509                   elements they store. Assume a hash-based container is
 510                   allowed to decrease its size when an element is
 511                   erased. Then the elements might be rehashed, which means
 512                   that there is no "next" element - it is simply
 513                   undefined. Consequently, it is possible to infer from the
 514                   fact that the standard library's hash-based containers
 515                   provide this method that they cannot downsize when
 516                   elements are erased. As a consequence, different code is
 517                   needed to manipulate different containers, assuming that
 518                   memory should be conserved. Therefor, this library's
 519                   non-order preserving associative containers omit this
 520                   method.
 521                 </p></li><li class="listitem"><p>
 522                   All associative containers include a conditional-erase method
 523                 </p><pre class="programlisting">
 524                   template&lt;
 525                   class Pred&gt;
 526                   size_type
 527                   erase_if
 528                   (Pred pred)
 529                 </pre><p>
 530                   which erases all elements matching a predicate. This is probably the
 531                   only way to ensure linear-time multiple-item erase which can
 532                   actually downsize a container.
 533                 </p></li><li class="listitem"><p>
 534                   The standard associative containers provide methods for
 535                   multiple-item erase of the form
 536                 </p><pre class="programlisting">
 537                   size_type
 538                   erase(It b, It e)
 539                 </pre><p>
 540                   erasing a range of elements given by a pair of
 541                   iterators. For tree-based or trie-based containers, this can
 542                   implemented more efficiently as a (small) sequence of split
 543                   and join operations. For other, unordered, containers, this
 544                   method isn't much better than an external loop. Moreover,
 545                   if <code class="varname">c</code> is a hash-based container,
 546                   then
 547                 </p><pre class="programlisting">
 548                   c.erase(c.find(2), c.find(5))
 549                 </pre><p>
 550                   is almost certain to do something
 551                   different than erasing all elements whose keys are between 2
 552                   and 5, and is likely to produce other undefined behavior.
 553                 </p></li></ol></div></div><div class="section" title="split and join"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.split"/>
 554                 <code class="function">split</code> and <code class="function">join</code>
 555               </h6></div></div></div><p>
 556               It is well-known that tree-based and trie-based container
 557               objects can be efficiently split or joined (See
 558               <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>). Externally splitting or
 559               joining trees is super-linear, and, furthermore, can throw
 560               exceptions. Split and join methods, consequently, seem good
 561               choices for tree-based container methods, especially, since as
 562               noted just before, they are efficient replacements for erasing
 563               sub-sequences.
 564             </p></div><div class="section" title="insert"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.insert"/>
 565                 <code class="function">insert</code>
 566               </h6></div></div></div><p>
 567               The standard associative containers provide methods of the form
 568             </p><pre class="programlisting">
 569               template&lt;class It&gt;
 570               size_type
 571               insert(It b, It e);
 572             </pre><p>
 573               for inserting a range of elements given by a pair of
 574               iterators. At best, this can be implemented as an external loop,
 575               or, even more efficiently, as a join operation (for the case of
 576               tree-based or trie-based containers). Moreover, these methods seem
 577               similar to constructors taking a range given by a pair of
 578               iterators; the constructors, however, are transactional, whereas
 579               the insert methods are not; this is possibly confusing.
 580             </p></div><div class="section" title="operator== and operator&lt;="><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.compare"/>
 581                 <code class="function">operator==</code> and <code class="function">operator&lt;=</code>
 582               </h6></div></div></div><p>
 583               Associative containers are parametrized by policies allowing to
 584               test key equivalence: a hash-based container can do this through
 585               its equivalence functor, and a tree-based container can do this
 586               through its comparison functor. In addition, some standard
 587               associative containers have global function operators, like
 588               <code class="function">operator==</code> and <code class="function">operator&lt;=</code>,
 589               that allow comparing entire associative containers.
 590             </p><p>
 591               In our opinion, these functions are better left out. To begin
 592               with, they do not significantly improve over an external
 593               loop. More importantly, however, they are possibly misleading -
 594               <code class="function">operator==</code>, for example, usually checks for
 595               equivalence, or interchangeability, but the associative
 596               container cannot check for values' equivalence, only keys'
 597               equivalence; also, are two containers considered equivalent if
 598               they store the same values in different order? this is an
 599               arbitrary decision.
 600             </p></div></div></div><div class="section" title="Priority Queues"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.motivation.priority_queue"/>Priority Queues</h4></div></div></div><div class="section" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.policy"/>Policy Choices</h5></div></div></div><p>
 601             Priority queues are containers that allow efficiently inserting
 602             values and accessing the maximal value (in the sense of the
 603             container's comparison functor). Their interface
 604             supports <code class="function">push</code>
 605             and <code class="function">pop</code>. The standard
 606             container <code class="classname">std::priorityqueue</code> indeed support
 607             these methods, but little else. For algorithmic and
 608             software-engineering purposes, other methods are needed:
 609           </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 610                 Many graph algorithms (see
 611                 <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>) require increasing a
 612                 value in a priority queue (again, in the sense of the
 613                 container's comparison functor), or joining two
 614                 priority-queue objects.
 615               </p></li><li class="listitem"><p>The return type of <code class="classname">priority_queue</code>'s
 616               <code class="function">push</code> method is a point-type iterator, which can
 617               be used for modifying or erasing arbitrary values. For
 618               example:</p><pre class="programlisting">
 619                 priority_queue&lt;int&gt; p;
 620                 priority_queue&lt;int&gt;::point_iterator it = p.push(3);
 621                 p.modify(it, 4);
 622               </pre><p>These types of cross-referencing operations are necessary
 623               for making priority queues useful for different applications,
 624               especially graph applications.</p></li><li class="listitem"><p>
 625                 It is sometimes necessary to erase an arbitrary value in a
 626                 priority queue. For example, consider
 627                 the <code class="function">select</code> function for monitoring
 628                 file descriptors:
 629               </p><pre class="programlisting">
 630                 int
 631                 select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds,
 632                 struct timeval *timeout);
 633               </pre><p>
 634                 then, as the select documentation states:
 635               </p><p>
 636                 <span class="quote">“<span class="quote">
 637                   The nfds argument specifies the range of file
 638                   descriptors to be tested. The select() function tests file
 639                 descriptors in the range of 0 to nfds-1.</span>”</span>
 640               </p><p>
 641                 It stands to reason, therefore, that we might wish to
 642                 maintain a minimal value for <code class="varname">nfds</code>, and
 643                 priority queues immediately come to mind. Note, though, that
 644                 when a socket is closed, the minimal file description might
 645                 change; in the absence of an efficient means to erase an
 646                 arbitrary value from a priority queue, we might as well
 647                 avoid its use altogether.
 648               </p><p>
 649                 The standard containers typically support iterators. It is
 650                 somewhat unusual
 651                 for <code class="classname">std::priority_queue</code> to omit them
 652                 (See <a class="xref" href="policy_data_structures.html#biblio.meyers01stl" title="Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library">[biblio.meyers01stl]</a>). One might
 653                 ask why do priority queues need to support iterators, since
 654                 they are self-organizing containers with a different purpose
 655                 than abstracting sequences. There are several reasons:
 656               </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 657                     Iterators (even in self-organizing containers) are
 658                     useful for many purposes: cross-referencing
 659                     containers, serialization, and debugging code that uses
 660                     these containers.
 661                   </p></li><li class="listitem"><p>
 662                     The standard library's hash-based containers support
 663                     iterators, even though they too are self-organizing
 664                     containers with a different purpose than abstracting
 665                     sequences.
 666                   </p></li><li class="listitem"><p>
 667                     In standard-library-like containers, it is natural to specify the
 668                     interface of operations for modifying a value or erasing
 669                     a value (discussed previously) in terms of a iterators.
 670                     It should be noted that the standard
 671                     containers also use iterators for accessing and
 672                     manipulating a specific value. In hash-based
 673                     containers, one checks the existence of a key by
 674                     comparing the iterator returned by <code class="function">find</code> to the
 675                     iterator returned by <code class="function">end</code>, and not by comparing a
 676                     pointer returned by <code class="function">find</code> to <span class="type">NULL</span>.
 677                   </p></li></ol></div></li></ol></div></div><div class="section" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.underlying"/>Underlying Data Structures</h5></div></div></div><p>
 678             There are three main implementations of priority queues: the
 679             first employs a binary heap, typically one which uses a
 680             sequence; the second uses a tree (or forest of trees), which is
 681             typically less structured than an associative container's tree;
 682             the third simply uses an associative container. These are
 683             shown in the figure below with labels A1 and A2, B, and C.
 684           </p><div class="figure"><a id="id574356"/><p class="title"><strong>Figure 22.6. Underlying Priority Queue Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_different_underlying_dss_2.png" style="text-align: middle" alt="Underlying Priority Queue Data Structures"/></div></div></div><br class="figure-break"/><p>
 685             No single implementation can completely replace any of the
 686             others. Some have better <code class="function">push</code>
 687             and <code class="function">pop</code> amortized performance, some have
 688             better bounded (worst case) response time than others, some
 689             optimize a single method at the expense of others, etc. In
 690             general the "best" implementation is dictated by the specific
 691             problem.
 692           </p><p>
 693             As with associative containers, the more implementations
 694             co-exist, the more necessary a traits mechanism is for handling
 695             generic containers safely and efficiently. This is especially
 696             important for priority queues, since the invalidation guarantees
 697             of one of the most useful data structures - binary heaps - is
 698             markedly different than those of most of the others.
 699           </p></div><div class="section" title="Binary Heaps"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.binary_heap"/>Binary Heaps</h5></div></div></div><p>
 700             Binary heaps are one of the most useful underlying
 701             data structures for priority queues. They are very efficient in
 702             terms of memory (since they don't require per-value structure
 703             metadata), and have the best amortized <code class="function">push</code> and
 704             <code class="function">pop</code> performance for primitive types like
 705             <span class="type">int</span>.
 706           </p><p>
 707             The standard library's <code class="classname">priority_queue</code>
 708             implements this data structure as an adapter over a sequence,
 709             typically
 710             <code class="classname">std::vector</code>
 711             or <code class="classname">std::deque</code>, which correspond to labels
 712             A1 and A2 respectively in the graphic above.
 713           </p><p>
 714             This is indeed an elegant example of the adapter concept and
 715             the algorithm/container/iterator decomposition. (See <a class="xref" href="policy_data_structures.html#biblio.nelson96stlpq" title="Priority Queues and the STL">[biblio.nelson96stlpq]</a>). There are
 716             several reasons why a binary-heap priority queue
 717             may be better implemented as a container instead of a
 718             sequence adapter:
 719           </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 720                 <code class="classname">std::priority_queue</code> cannot erase values
 721                 from its adapted sequence (irrespective of the sequence
 722                 type). This means that the memory use of
 723                 an <code class="classname">std::priority_queue</code> object is always
 724                 proportional to the maximal number of values it ever contained,
 725                 and not to the number of values that it currently
 726                 contains. (See <code class="filename">performance/priority_queue_text_pop_mem_usage.cc</code>.)
 727                 This implementation of binary heaps acts very differently than
 728                 other underlying data structures (See also pairing heaps).
 729               </p></li><li class="listitem"><p>
 730                 Some combinations of adapted sequences and value types
 731                 are very inefficient or just don't make sense. If one uses
 732                 <code class="classname">std::priority_queue&lt;std::vector&lt;std::string&gt;
 733                 &gt; &gt;</code>, for example, then not only will each
 734                 operation perform a logarithmic number of
 735                 <code class="classname">std::string</code> assignments, but, furthermore, any
 736                 operation (including <code class="function">pop</code>) can render the container
 737                 useless due to exceptions. Conversely, if one uses
 738                 <code class="classname">std::priority_queue&lt;std::deque&lt;int&gt; &gt;
 739                 &gt;</code>, then each operation uses incurs a logarithmic
 740                 number of indirect accesses (through pointers) unnecessarily.
 741                 It might be better to let the container make a conservative
 742                 deduction whether to use the structure in the graphic above, labels A1 or A2.
 743               </p></li><li class="listitem"><p>
 744                 There does not seem to be a systematic way to determine
 745                 what exactly can be done with the priority queue.
 746               </p><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
 747                     If <code class="classname">p</code> is a priority queue adapting an
 748                     <code class="classname">std::vector</code>, then it is possible to iterate over
 749                     all values by using <code class="function">&amp;p.top()</code> and
 750                     <code class="function">&amp;p.top() + p.size()</code>, but this will not work
 751                     if <code class="varname">p</code> is adapting an <code class="classname">std::deque</code>; in any
 752                     case, one cannot use <code class="classname">p.begin()</code> and
 753                     <code class="classname">p.end()</code>. If a different sequence is adapted, it
 754                     is even more difficult to determine what can be
 755                     done.
 756                   </p></li><li class="listitem"><p>
 757                     If <code class="varname">p</code> is a priority queue adapting an
 758                     <code class="classname">std::deque</code>, then the reference return by
 759                   </p><pre class="programlisting">
 760                     p.top()
 761                   </pre><p>
 762                     will remain valid until it is popped,
 763                     but if <code class="varname">p</code> adapts an <code class="classname">std::vector</code>, the
 764                     next <code class="function">push</code> will invalidate it. If a different
 765                     sequence is adapted, it is even more difficult to
 766                     determine what can be done.
 767                   </p></li></ol></div></li><li class="listitem"><p>
 768                 Sequence-based binary heaps can still implement
 769                 linear-time <code class="function">erase</code> and <code class="function">modify</code> operations.
 770                 This means that if one needs to erase a small
 771                 (say logarithmic) number of values, then one might still
 772                 choose this underlying data structure. Using
 773                 <code class="classname">std::priority_queue</code>, however, this will generally
 774                 change the order of growth of the entire sequence of
 775                 operations.
 776               </p></li></ol></div></div></div></div></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h2 class="title"><a id="pbds.biblio"/>
 777         Bibliography
 778       </h2></div></div></div><div class="biblioentry" title="STL Exception Handling Contract"><a id="biblio.abrahams97exception"/><p>[biblio.abrahams97exception] <span class="title"><em>
 779         <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1075.pdf">
 780           STL Exception Handling Contract
 781         </a>
 782       </em>. </span><span class="date">1997. </span><span class="author"><span class="firstname">
 783             Dave
 784           </span> <span class="surname">
 785             Abrahams
 786           </span>. </span><span class="publisher"><span class="publishername">
 787           ISO SC22/WG21
 788         . </span></span></p></div><div class="biblioentry" title="Modern C++ Design: Generic Programming and Design Patterns Applied"><a id="biblio.alexandrescu01modern"/><p>[biblio.alexandrescu01modern] <span class="title"><em>
 789         Modern C++ Design: Generic Programming and Design Patterns Applied
 790       </em>. </span><span class="date">
 791         2001
 792       . </span><span class="author"><span class="firstname">
 793             Andrei
 794           </span> <span class="surname">
 795             Alexandrescu
 796           </span>. </span><span class="publisher"><span class="publishername">
 797           Addison-Wesley Publishing Company
 798         . </span></span></p></div><div class="biblioentry" title="MTF, Bit, and COMB: A Guide to Deterministic and Randomized Algorithms for the List Update Problem"><a id="biblio.andrew04mtf"/><p>[biblio.andrew04mtf] <span class="title"><em>
 799         MTF, Bit, and COMB: A Guide to Deterministic and Randomized
 800         Algorithms for the List Update Problem
 801       </em>. </span><span class="authorgroup"><span class="firstname">
 802               K.
 803             </span> <span class="surname">
 804               Andrew
 805             </span> and <span class="firstname">
 806               D.
 807             </span> <span class="surname">
 808               Gleich
 809             </span>. </span></p></div><div class="biblioentry" title="Why You Shouldn't Use set - and What You Should Use Instead"><a id="biblio.austern00noset"/><p>[biblio.austern00noset] <span class="title"><em>
 810         Why You Shouldn't Use set - and What You Should Use Instead
 811       </em>. </span><span class="date">
 812         April, 2000
 813       . </span><span class="author"><span class="firstname">
 814             Matthew
 815           </span> <span class="surname">
 816             Austern
 817           </span>. </span><span class="publisher"><span class="publishername">
 818           C++ Report
 819         . </span></span></p></div><div class="biblioentry" title="A Proposal to Add Hashtables to the Standard Library"><a id="biblio.austern01htprop"/><p>[biblio.austern01htprop] <span class="title"><em>
 820         <a class="link" href="http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2001/n1326.html">
 821           A Proposal to Add Hashtables to the Standard Library
 822         </a>
 823       </em>. </span><span class="date">
 824         2001
 825       . </span><span class="author"><span class="firstname">
 826             Matthew
 827           </span> <span class="surname">
 828             Austern
 829           </span>. </span><span class="publisher"><span class="publishername">
 830           ISO SC22/WG21
 831         . </span></span></p></div><div class="biblioentry" title="Segmented iterators and hierarchical algorithms"><a id="biblio.austern98segmentedit"/><p>[biblio.austern98segmentedit] <span class="title"><em>
 832         Segmented iterators and hierarchical algorithms
 833       </em>. </span><span class="date">
 834         April, 1998
 835       . </span><span class="author"><span class="firstname">
 836             Matthew
 837           </span> <span class="surname">
 838             Austern
 839           </span>. </span><span class="publisher"><span class="publishername">
 840           Generic Programming
 841         . </span></span></p></div><div class="biblioentry" title="Boost Timer Library"><a id="biblio.dawestimer"/><p>[biblio.dawestimer] <span class="title"><em>
 842         <a class="link" href="www.boost.org/doc/libs/release/libs/timer/">
 843           Boost Timer Library
 844         </a>
 845       </em>. </span><span class="author"><span class="firstname">
 846             Beeman
 847           </span> <span class="surname">
 848             Dawes
 849           </span>. </span><span class="publisher"><span class="publishername">
 850           Boost
 851         . </span></span></p></div><div class="biblioentry" title="Boost Pool Library"><a id="biblio.clearypool"/><p>[biblio.clearypool] <span class="title"><em>
 852         <a class="link" href="www.boost.org/doc/libs/release/libs/pool/">
 853           Boost Pool Library
 854         </a>
 855       </em>. </span><span class="author"><span class="firstname">
 856             Stephen
 857           </span> <span class="surname">
 858             Cleary
 859           </span>. </span><span class="publisher"><span class="publishername">
 860           Boost
 861         . </span></span></p></div><div class="biblioentry" title="Boost Type Traits Library"><a id="biblio.maddocktraits"/><p>[biblio.maddocktraits] <span class="title"><em>
 862         <a class="link" href="www.boost.org/doc/libs/release/libs/type_traits/">
 863           Boost Type Traits Library
 864         </a>
 865       </em>. </span><span class="authorgroup"><span class="firstname">
 866               Maddock
 867             </span> <span class="surname">
 868               John
 869             </span> and <span class="firstname">
 870               Stephen
 871             </span> <span class="surname">
 872               Cleary
 873             </span>. </span><span class="publisher"><span class="publishername">
 874           Boost
 875         . </span></span></p></div><div class="biblioentry" title="Worst-case efficient priority queues"><a id="biblio.brodal96priority"/><p>[biblio.brodal96priority] <span class="title"><em>
 876         <a class="link" href="http://portal.acm.org/citation.cfm?id=313883">
 877           Worst-case efficient priority queues
 878         </a>
 879       </em>. </span><span class="author"><span class="firstname">
 880             Gerth
 881           </span> <span class="surname">
 882             Stolting Brodal
 883           </span>. </span></p></div><div class="biblioentry" title="Efficient C++ Programming Techniques"><a id="biblio.bulkamayheweff"/><p>[biblio.bulkamayheweff] <span class="title"><em>
 884         Efficient C++ Programming Techniques
 885       </em>. </span><span class="date">
 886         1997
 887       . </span><span class="authorgroup"><span class="firstname">
 888               D.
 889             </span> <span class="surname">
 890               Bulka
 891             </span> and <span class="firstname">
 892               D.
 893             </span> <span class="surname">
 894               Mayhew
 895             </span>. </span><span class="publisher"><span class="publishername">
 896           Addison-Wesley Publishing Company
 897         . </span></span></p></div><div class="biblioentry" title="Introduction to Algorithms, 2nd edition"><a id="biblio.clrs2001"/><p>[biblio.clrs2001] <span class="title"><em>
 898         Introduction to Algorithms, 2nd edition
 899       </em>. </span><span class="date">
 900         2001
 901       . </span><span class="authorgroup"><span class="firstname">
 902               T. H.
 903             </span> <span class="surname">
 904               Cormen
 905             </span>, <span class="firstname">
 906               C. E.
 907             </span> <span class="surname">
 908               Leiserson
 909             </span>, <span class="firstname">
 910               R. L.
 911             </span> <span class="surname">
 912               Rivest
 913             </span>, and <span class="firstname">
 914               C.
 915             </span> <span class="surname">
 916               Stein
 917             </span>. </span><span class="publisher"><span class="publishername">
 918           MIT Press
 919         . </span></span></p></div><div class="biblioentry" title="Balls and bins: A study in negative dependence"><a id="biblio.dubhashi98neg"/><p>[biblio.dubhashi98neg] <span class="title"><em>
 920         Balls and bins: A study in negative dependence
 921       </em>. </span><span class="date">
 922         1998
 923       . </span><span class="authorgroup"><span class="firstname">
 924               D.
 925             </span> <span class="surname">
 926               Dubashi
 927             </span> and <span class="firstname">
 928               D.
 929             </span> <span class="surname">
 930               Ranjan
 931             </span>. </span><span class="publisher"><span class="publishername">
 932           Random Structures and Algorithms 13
 933         . </span></span></p></div><div class="biblioentry" title="Extendible hashing - a fast access method for dynamic files"><a id="biblio.fagin79extendible"/><p>[biblio.fagin79extendible] <span class="title"><em>
 934         Extendible hashing - a fast access method for dynamic files
 935       </em>. </span><span class="date">
 936         1979
 937       . </span><span class="authorgroup"><span class="firstname">
 938               R.
 939             </span> <span class="surname">
 940               Fagin
 941             </span>, <span class="firstname">
 942               J.
 943             </span> <span class="surname">
 944               Nievergelt
 945             </span>, <span class="firstname">
 946               N.
 947             </span> <span class="surname">
 948               Pippenger
 949             </span>, and <span class="firstname">
 950               H. R.
 951             </span> <span class="surname">
 952               Strong
 953             </span>. </span><span class="publisher"><span class="publishername">
 954           ACM Trans. Database Syst. 4
 955         . </span></span></p></div><div class="biblioentry" title="Ptset: Sets of integers implemented as Patricia trees"><a id="biblio.filliatre2000ptset"/><p>[biblio.filliatre2000ptset] <span class="title"><em>
 956         <a class="link" href="http://cristal.inria.fr/~frisch/icfp06_contest/advtr/applyOmatic/ptset.ml">
 957           Ptset: Sets of integers implemented as Patricia trees
 958         </a>
 959       </em>. </span><span class="date">
 960         2000
 961       . </span><span class="author"><span class="firstname">
 962             Jean-Christophe
 963           </span> <span class="surname">
 964             Filliatre
 965           </span>. </span></p></div><div class="biblioentry" title="The pairing heap: a new form of self-adjusting heap"><a id="biblio.fredman86pairing"/><p>[biblio.fredman86pairing] <span class="title"><em>
 966         <a class="link" href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf">
 967           The pairing heap: a new form of self-adjusting heap
 968         </a>
 969       </em>. </span><span class="date">
 970         1986
 971       . </span><span class="authorgroup"><span class="firstname">
 972               M. L.
 973             </span> <span class="surname">
 974               Fredman
 975             </span>, <span class="firstname">
 976               R.
 977             </span> <span class="surname">
 978               Sedgewick
 979             </span>, <span class="firstname">
 980               D. D.
 981             </span> <span class="surname">
 982               Sleator
 983             </span>, and <span class="firstname">
 984               R. E.
 985             </span> <span class="surname">
 986               Tarjan
 987             </span>. </span></p></div><div class="biblioentry" title="Design Patterns - Elements of Reusable Object-Oriented Software"><a id="biblio.gof"/><p>[biblio.gof] <span class="title"><em>
 988         Design Patterns - Elements of Reusable Object-Oriented Software
 989       </em>. </span><span class="date">
 990         1995
 991       . </span><span class="authorgroup"><span class="firstname">
 992               E.
 993             </span> <span class="surname">
 994               Gamma
 995             </span>, <span class="firstname">
 996               R.
 997             </span> <span class="surname">
 998               Helm
 999             </span>, <span class="firstname">
1000               R.
1001             </span> <span class="surname">
1002               Johnson
1003             </span>, and <span class="firstname">
1004               J.
1005             </span> <span class="surname">
1006               Vlissides
1007             </span>. </span><span class="publisher"><span class="publishername">
1008           Addison-Wesley Publishing Company
1009         . </span></span></p></div><div class="biblioentry" title="Order-preserving key transformations"><a id="biblio.garg86order"/><p>[biblio.garg86order] <span class="title"><em>
1010         Order-preserving key transformations
1011       </em>. </span><span class="date">
1012         1986
1013       . </span><span class="authorgroup"><span class="firstname">
1014               A. K.
1015             </span> <span class="surname">
1016               Garg
1017             </span> and <span class="firstname">
1018               C. C.
1019             </span> <span class="surname">
1020               Gotlieb
1021             </span>. </span><span class="publisher"><span class="publishername">
1022           Trans. Database Syst. 11
1023         . </span></span></p></div><div class="biblioentry" title="Making a real hash of things"><a id="biblio.hyslop02making"/><p>[biblio.hyslop02making] <span class="title"><em>
1024         Making a real hash of things
1025       </em>. </span><span class="date">
1026         May 2002
1027       . </span><span class="authorgroup"><span class="firstname">
1028               J.
1029             </span> <span class="surname">
1030               Hyslop
1031             </span> and <span class="firstname">
1032               Herb
1033             </span> <span class="surname">
1034               Sutter
1035             </span>. </span><span class="publisher"><span class="publishername">
1036           C++ Report
1037         . </span></span></p></div><div class="biblioentry" title="The C++ Standard Library - A Tutorial and Reference"><a id="biblio.jossutis01stl"/><p>[biblio.jossutis01stl] <span class="title"><em>
1038         The C++ Standard Library - A Tutorial and Reference
1039       </em>. </span><span class="date">
1040         2001
1041       . </span><span class="author"><span class="firstname">
1042             N. M.
1043           </span> <span class="surname">
1044             Jossutis
1045           </span>. </span><span class="publisher"><span class="publishername">
1046           Addison-Wesley Publishing Company
1047         . </span></span></p></div><div class="biblioentry" title="New Heap Data Structures"><a id="biblio.kt99fat_heaps"/><p>[biblio.kt99fat_heaps] <span class="title"><em>
1048         <a class="link" href="http://www.cs.princeton.edu/research/techreps/TR-597-99">
1049           New Heap Data Structures
1050         </a>
1051       </em>. </span><span class="date">
1052         1999
1053       . </span><span class="authorgroup"><span class="firstname">
1054               Haim
1055             </span> <span class="surname">
1056               Kaplan
1057             </span> and <span class="firstname">
1058               Robert E.
1059             </span> <span class="surname">
1060               Tarjan
1061             </span>. </span></p></div><div class="biblioentry" title="Are Set Iterators Mutable or Immutable?"><a id="biblio.kleft00sets"/><p>[biblio.kleft00sets] <span class="title"><em>
1062         Are Set Iterators Mutable or Immutable?
1063       </em>. </span><span class="date">
1064         October 2000
1065       . </span><span class="authorgroup"><span class="firstname">
1066               Angelika
1067             </span> <span class="surname">
1068               Langer
1069             </span> and <span class="firstname">
1070               Klaus
1071             </span> <span class="surname">
1072               Kleft
1073             </span>. </span><span class="publisher"><span class="publishername">
1074           C/C++ Users Jornal
1075         . </span></span></p></div><div class="biblioentry" title="The Art of Computer Programming - Sorting and Searching"><a id="biblio.knuth98sorting"/><p>[biblio.knuth98sorting] <span class="title"><em>
1076         The Art of Computer Programming - Sorting and Searching
1077       </em>. </span><span class="date">
1078         1998
1079       . </span><span class="author"><span class="firstname">
1080             D. E.
1081           </span> <span class="surname">
1082             Knuth
1083           </span>. </span><span class="publisher"><span class="publishername">
1084           Addison-Wesley Publishing Company
1085         . </span></span></p></div><div class="biblioentry" title="Data abstraction and hierarchy"><a id="biblio.liskov98data"/><p>[biblio.liskov98data] <span class="title"><em>
1086         Data abstraction and hierarchy
1087       </em>. </span><span class="date">
1088         May 1998
1089       . </span><span class="author"><span class="firstname">
1090             B.
1091           </span> <span class="surname">
1092             Liskov
1093           </span>. </span><span class="publisher"><span class="publishername">
1094           SIGPLAN Notices 23
1095         . </span></span></p></div><div class="biblioentry" title="Linear hashing: A new tool for file and table addressing"><a id="biblio.litwin80lh"/><p>[biblio.litwin80lh] <span class="title"><em>
1096         Linear hashing: A new tool for file and table addressing
1097       </em>. </span><span class="date">
1098         June 1980
1099       . </span><span class="author"><span class="firstname">
1100             W.
1101           </span> <span class="surname">
1102             Litwin
1103           </span>. </span><span class="publisher"><span class="publishername">
1104           Proceedings of International Conference on Very Large Data Bases
1105         . </span></span></p></div><div class="biblioentry" title="Deamortization - Part 2: Binomial Heaps"><a id="biblio.maverik_lowerbounds"/><p>[biblio.maverik_lowerbounds] <span class="title"><em>
1106         <a class="link" href="http://magic.aladdin.cs.cmu.edu/2005/08/01/deamortization-part-2-binomial-heaps">
1107           Deamortization - Part 2: Binomial Heaps
1108         </a>
1109       </em>. </span><span class="date">
1110         2005
1111       . </span><span class="author"><span class="firstname">
1112             Maverik
1113           </span> <span class="surname">
1114             Woo
1115           </span>. </span></p></div><div class="biblioentry" title="More Effective C++: 35 New Ways to Improve Your Programs and Designs"><a id="biblio.meyers96more"/><p>[biblio.meyers96more] <span class="title"><em>
1116         More Effective C++: 35 New Ways to Improve Your Programs and Designs
1117       </em>. </span><span class="date">
1118         1996
1119       . </span><span class="author"><span class="firstname">
1120             Scott
1121           </span> <span class="surname">
1122             Meyers
1123           </span>. </span><span class="publisher"><span class="publishername">
1124           Addison-Wesley Publishing Company
1125         . </span></span></p></div><div class="biblioentry" title="How Non-Member Functions Improve Encapsulation"><a id="biblio.meyers00nonmember"/><p>[biblio.meyers00nonmember] <span class="title"><em>
1126         How Non-Member Functions Improve Encapsulation
1127       </em>. </span><span class="date">
1128         2000
1129       . </span><span class="author"><span class="firstname">
1130             Scott
1131           </span> <span class="surname">
1132             Meyers
1133           </span>. </span><span class="publisher"><span class="publishername">
1134           C/C++ Users Journal
1135         . </span></span></p></div><div class="biblioentry" title="Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library"><a id="biblio.meyers01stl"/><p>[biblio.meyers01stl] <span class="title"><em>
1136         Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library
1137       </em>. </span><span class="date">
1138         2001
1139       . </span><span class="author"><span class="firstname">
1140             Scott
1141           </span> <span class="surname">
1142             Meyers
1143           </span>. </span><span class="publisher"><span class="publishername">
1144           Addison-Wesley Publishing Company
1145         . </span></span></p></div><div class="biblioentry" title="Class Template, Member Template - or Both?"><a id="biblio.meyers02both"/><p>[biblio.meyers02both] <span class="title"><em>
1146         Class Template, Member Template - or Both?
1147       </em>. </span><span class="date">
1148         2003
1149       . </span><span class="author"><span class="firstname">
1150             Scott
1151           </span> <span class="surname">
1152             Meyers
1153           </span>. </span><span class="publisher"><span class="publishername">
1154           C/C++ Users Journal
1155         . </span></span></p></div><div class="biblioentry" title="Randomized Algorithms"><a id="biblio.motwani95random"/><p>[biblio.motwani95random] <span class="title"><em>
1156         Randomized Algorithms
1157       </em>. </span><span class="date">
1158         2003
1159       . </span><span class="authorgroup"><span class="firstname">
1160               R.
1161             </span> <span class="surname">
1162               Motwani
1163             </span> and <span class="firstname">
1164               P.
1165             </span> <span class="surname">
1166               Raghavan
1167             </span>. </span><span class="publisher"><span class="publishername">
1168           Cambridge University Press
1169         . </span></span></p></div><div class="biblioentry" title="COM: Component Model Object Technologies"><a id="biblio.mscom"/><p>[biblio.mscom] <span class="title"><em>
1170         <a class="link" href="http://www.microsoft.com/com">
1171           COM: Component Model Object Technologies
1172         </a>
1173       </em>. </span><span class="publisher"><span class="publishername">
1174           Microsoft
1175         . </span></span></p></div><div class="biblioentry" title="Rationale for Adding Hash Tables to the C++ Standard Template Library"><a id="biblio.musser95rationale"/><p>[biblio.musser95rationale] <span class="title"><em>
1176         Rationale for Adding Hash Tables to the C++ Standard Template Library
1177       </em>. </span><span class="date">
1178         1995
1179       . </span><span class="author"><span class="firstname">
1180             David R.
1181           </span> <span class="surname">
1182             Musser
1183           </span>. </span></p></div><div class="biblioentry" title="STL Tutorial and Reference Guide"><a id="biblio.musser96stltutorial"/><p>[biblio.musser96stltutorial] <span class="title"><em>
1184         STL Tutorial and Reference Guide
1185       </em>. </span><span class="date">
1186         1996
1187       . </span><span class="authorgroup"><span class="firstname">
1188               David R.
1189             </span> <span class="surname">
1190               Musser
1191             </span> and <span class="firstname">
1192               A.
1193             </span> <span class="surname">
1194               Saini
1195             </span>. </span><span class="publisher"><span class="publishername">
1196           Addison-Wesley Publishing Company
1197         . </span></span></p></div><div class="biblioentry" title="Priority Queues and the STL"><a id="biblio.nelson96stlpq"/><p>[biblio.nelson96stlpq] <span class="title"><em>
1198         <a class="link" href="http://www.dogma.net/markn/articles/pq_stl/priority.htm">Priority Queues and the STL
1199         </a>
1200       </em>. </span><span class="date">
1201         January 1996
1202       . </span><span class="author"><span class="firstname">
1203             Mark
1204           </span> <span class="surname">
1205             Nelson
1206           </span>. </span><span class="publisher"><span class="publishername">
1207           Dr. Dobbs Journal
1208         . </span></span></p></div><div class="biblioentry" title="Fast mergeable integer maps"><a id="biblio.okasaki98mereable"/><p>[biblio.okasaki98mereable] <span class="title"><em>
1209         Fast mergeable integer maps
1210       </em>. </span><span class="date">
1211         September 1998
1212       . </span><span class="authorgroup"><span class="firstname">
1213               C.
1214             </span> <span class="surname">
1215               Okasaki
1216             </span> and <span class="firstname">
1217               A.
1218             </span> <span class="surname">
1219               Gill
1220             </span>. </span><span class="publisher"><span class="publishername">
1221           In Workshop on ML
1222         . </span></span></p></div><div class="biblioentry" title="Standard Template Library Programmer's Guide"><a id="biblio.sgi_stl"/><p>[biblio.sgi_stl] <span class="title"><em>
1223         <a class="link" href="http://www.sgi.com/tech/stl">
1224           Standard Template Library Programmer's Guide
1225         </a>
1226       </em>. </span><span class="author"><span class="firstname">
1227             Matt
1228           </span> <span class="surname">
1229             Austern
1230           </span>. </span><span class="publisher"><span class="publishername">
1231           SGI
1232         . </span></span></p></div><div class="biblioentry" title="select"><a id="biblio.select_man"/><p>[biblio.select_man] <span class="title"><em>
1233         <a class="link" href="http://www.scit.wlv.ac.uk/cgi-bin/mansec?3C+select">
1234           select
1235         </a>
1236       </em>. </span></p></div><div class="biblioentry" title="Amortized Efficiency of List Update Problems"><a id="biblio.sleator84amortized"/><p>[biblio.sleator84amortized] <span class="title"><em>
1237         Amortized Efficiency of List Update Problems
1238       </em>. </span><span class="date">
1239         1984
1240       . </span><span class="authorgroup"><span class="firstname">
1241               D. D.
1242             </span> <span class="surname">
1243               Sleator
1244             </span> and <span class="firstname">
1245               R. E.
1246             </span> <span class="surname">
1247               Tarjan
1248             </span>. </span><span class="publisher"><span class="publishername">
1249           ACM Symposium on Theory of Computing
1250         . </span></span></p></div><div class="biblioentry" title="Self-Adjusting Binary Search Trees"><a id="biblio.sleator85self"/><p>[biblio.sleator85self] <span class="title"><em>
1251         Self-Adjusting Binary Search Trees
1252       </em>. </span><span class="date">
1253         1985
1254       . </span><span class="authorgroup"><span class="firstname">
1255               D. D.
1256             </span> <span class="surname">
1257               Sleator
1258             </span> and <span class="firstname">
1259               R. E.
1260             </span> <span class="surname">
1261               Tarjan
1262             </span>. </span><span class="publisher"><span class="publishername">
1263           ACM Symposium on Theory of Computing
1264         . </span></span></p></div><div class="biblioentry" title="The Standard Template Library"><a id="biblio.stepanov94standard"/><p>[biblio.stepanov94standard] <span class="title"><em>
1265         The Standard Template Library
1266       </em>. </span><span class="date">
1267         1984
1268       . </span><span class="authorgroup"><span class="firstname">
1269               A. A.
1270             </span> <span class="surname">
1271               Stepanov
1272             </span> and <span class="firstname">
1273               M.
1274             </span> <span class="surname">
1275               Lee
1276             </span>. </span></p></div><div class="biblioentry" title="The C++ Programming Langugage"><a id="biblio.stroustrup97cpp"/><p>[biblio.stroustrup97cpp] <span class="title"><em>
1277         The C++ Programming Langugage
1278       </em>. </span><span class="date">
1279         1997
1280       . </span><span class="author"><span class="firstname">
1281             Bjarne
1282           </span> <span class="surname">
1283             Stroustrup
1284           </span>. </span><span class="publisher"><span class="publishername">
1285           Addison-Wesley Publishing Company
1286         . </span></span></p></div><div class="biblioentry" title="C++ Templates: The Complete Guide"><a id="biblio.vandevoorde2002cpptemplates"/><p>[biblio.vandevoorde2002cpptemplates] <span class="title"><em>
1287         C++ Templates: The Complete Guide
1288       </em>. </span><span class="date">
1289         2002
1290       . </span><span class="authorgroup"><span class="firstname">
1291               D.
1292             </span> <span class="surname">
1293               Vandevoorde
1294             </span> and <span class="firstname">
1295               N. M.
1296             </span> <span class="surname">
1297               Josuttis
1298             </span>. </span><span class="publisher"><span class="publishername">
1299           Addison-Wesley Publishing Company
1300         . </span></span></p></div><div class="biblioentry" title="Thirty Years Among the Dead"><a id="biblio.wickland96thirty"/><p>[biblio.wickland96thirty] <span class="title"><em>
1301         <a class="link" href="http://myweb.wvnet.edu/~gsa00121/books/amongdead30.zip">
1302           Thirty Years Among the Dead
1303         </a>
1304       </em>. </span><span class="date">
1305         1996
1306       . </span><span class="author"><span class="firstname">
1307             C. A.
1308           </span> <span class="surname">
1309             Wickland
1310           </span>. </span><span class="publisher"><span class="publishername">
1311           National Psychological Institute
1312         . </span></span></p></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><td align="center"><a accesskey="u" href="extensions.html">Up</a></td><td align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr><tr><td align="left" valign="top">Implementation </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Using</td></tr></table></div></body></html>