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

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