gcc-4_9-branch/libstdc++-v3/doc/html/manual/policy_data_structures.html

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