| <?xml version="1.0" encoding="UTF-8" standalone="no"?> | |
| <!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 Stylesheets Vsnapshot" /><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. | |
| Extensions | |
| </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 Queue</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"> | |
| Configuring via Template Parameters | |
| </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.traits"> | |
| Querying Container Attributes | |
| </a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.point_range_iteration"> | |
| Point and Range Iteration | |
| </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"> | |
| Distinguishing Between Maps and Sets | |
| </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"> | |
| Text <code class="function">find</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_find"> | |
| Integer <code class="function">find</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_find"> | |
| Integer Subscript <code class="function">find</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.int_subscript_insert"> | |
| Integer Subscript <code class="function">insert</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.zlob_int_find"> | |
| Integer <code class="function">find</code> with Skewed-Distribution | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.hash.erase_mem"> | |
| Erase Memory Use | |
| </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"> | |
| Text <code class="function">insert</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_find"> | |
| Text <code class="function">find</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.text_lor_find"> | |
| Text <code class="function">find</code> with Locality-of-Reference | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.split_join"> | |
| <code class="function">split</code> and <code class="function">join</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.branch.order_statistics"> | |
| Order-Statistics | |
| </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"> | |
| Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_find_large"> | |
| Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_small"> | |
| Text <code class="function">insert</code> with Small | |
| Secondary-to-Primary Key Ratios | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_large"> | |
| Text <code class="function">insert</code> with Small | |
| Secondary-to-Primary Key Ratios | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_small"> | |
| Text <code class="function">insert</code> with Small | |
| Secondary-to-Primary Key Ratios Memory Use | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.multimap.text_insert_mem_large"> | |
| Text <code class="function">insert</code> with Small | |
| Secondary-to-Primary Key Ratios Memory Use | |
| </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"> | |
| Text <code class="function">push</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_push_pop"> | |
| Text <code class="function">push</code> and <code class="function">pop</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push"> | |
| Integer <code class="function">push</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.int_push_pop"> | |
| Integer <code class="function">push</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_pop"> | |
| Text <code class="function">pop</code> Memory Use | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_join"> | |
| Text <code class="function">join</code> | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_up"> | |
| Text <code class="function">modify</code> Up | |
| </a></span></dt><dt><span class="section"><a href="policy_based_data_structures_test.html#performance.priority_queue.text_modify_down"> | |
| Text <code class="function">modify</code> Down | |
| </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> | |
| This is a library of policy-based elementary data structures: | |
| associative containers and priority queues. It is designed for | |
| high-performance, flexibility, semantic safety, and conformance to | |
| the corresponding containers in <code class="literal">std</code> and | |
| <code class="literal">std::tr1</code> (except for some points where it differs | |
| by design). | |
| </p><p> | |
| </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> | |
| </p><p> | |
| An attempt is made to categorize the wide variety of possible | |
| container designs in terms of performance-impacting factors. These | |
| performance factors are translated into design policies and | |
| incorporated into container design. | |
| </p><p> | |
| There is tension between unravelling factors into a coherent set of | |
| policies. Every attempt is made to make a minimal set of | |
| factors. However, in many cases multiple factors make for long | |
| template names. Every attempt is made to alias and use typedefs in | |
| the source files, but the generated names for external symbols can | |
| be large for binary files or debuggers. | |
| </p><p> | |
| In many cases, the longer names allow capabilities and behaviours | |
| controlled by macros to also be unambiguously emitted as distinct | |
| generated names. | |
| </p><p> | |
| Specific issues found while unraveling performance factors in the | |
| design of associative containers and priority queues follow. | |
| </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> | |
| Associative containers depend on their composite policies to a very | |
| large extent. Implicitly hard-wiring policies can hamper their | |
| performance and limit their functionality. An efficient hash-based | |
| container, for example, requires policies for testing key | |
| equivalence, hashing keys, translating hash values into positions | |
| within the hash table, and determining when and how to resize the | |
| table internally. A tree-based container can efficiently support | |
| order statistics, i.e. the ability to query what is the order of | |
| each key within the sequence of keys in the container, but only if | |
| the container is supplied with a policy to internally update | |
| meta-data. There are many other such examples. | |
| </p><p> | |
| Ideally, all associative containers would share the same | |
| interface. Unfortunately, underlying data structures and mapping | |
| semantics differentiate between different containers. For example, | |
| suppose one writes a generic function manipulating an associative | |
| container. | |
| </p><pre class="programlisting"> | |
| template<typename Cntnr> | |
| void | |
| some_op_sequence(Cntnr& r_cnt) | |
| { | |
| ... | |
| } | |
| </pre><p> | |
| Given this, then what can one assume about the instantiating | |
| container? The answer varies according to its underlying data | |
| structure. If the underlying data structure of | |
| <code class="literal">Cntnr</code> is based on a tree or trie, then the order | |
| of elements is well defined; otherwise, it is not, in general. If | |
| the underlying data structure of <code class="literal">Cntnr</code> is based | |
| on a collision-chaining hash table, then modifying | |
| r_<code class="literal">Cntnr</code> will not invalidate its iterators' order; | |
| if the underlying data structure is a probing hash table, then this | |
| is not the case. If the underlying data structure is based on a tree | |
| or trie, then a reference to the container can efficiently be split; | |
| otherwise, it cannot, in general. If the underlying data structure | |
| is a red-black tree, then splitting a reference to the container is | |
| exception-free; if it is an ordered-vector tree, exceptions can be | |
| thrown. | |
| </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.priority_queue"></a>Priority Queue</h4></div></div></div><p> | |
| Priority queues are useful when one needs to efficiently access a | |
| minimum (or maximum) value as the set of values changes. | |
| </p><p> | |
| Most useful data structures for priority queues have a relatively | |
| simple structure, as they are geared toward relatively simple | |
| requirements. Unfortunately, these structures do not support access | |
| to an arbitrary value, which turns out to be necessary in many | |
| algorithms. Say, decreasing an arbitrary value in a graph | |
| algorithm. Therefore, some extra mechanism is necessary and must be | |
| invented for accessing arbitrary values. There are at least two | |
| alternatives: embedding an associative container in a priority | |
| queue, or allowing cross-referencing through iterators. The first | |
| solution adds significant overhead; the second solution requires a | |
| precise definition of iterator invalidation. Which is the next | |
| point... | |
| </p><p> | |
| Priority queues, like hash-based containers, store values in an | |
| order that is meaningless and undefined externally. For example, a | |
| <code class="code">push</code> operation can internally reorganize the | |
| values. Because of this characteristic, describing a priority | |
| queues' iterator is difficult: on one hand, the values to which | |
| iterators point can remain valid, but on the other, the logical | |
| order of iterators can change unpredictably. | |
| </p><p> | |
| Roughly speaking, any element that is both inserted to a priority | |
| queue (e.g. through <code class="code">push</code>) and removed | |
| from it (e.g., through <code class="code">pop</code>), incurs a | |
| logarithmic overhead (in the amortized sense). Different underlying | |
| data structures place the actual cost differently: some are | |
| optimized for amortized complexity, whereas others guarantee that | |
| specific operations only have a constant cost. One underlying data | |
| structure might be chosen if modifying a value is frequent | |
| (Dijkstra's shortest-path algorithm), whereas a different one might | |
| be chosen otherwise. Unfortunately, an array-based binary heap - an | |
| underlying data structure that optimizes (in the amortized sense) | |
| <code class="code">push</code> and <code class="code">pop</code> operations, differs from the | |
| others in terms of its invalidation guarantees. Other design | |
| decisions also impact the cost and placement of the overhead, at the | |
| expense of more difference in the kinds of operations that the | |
| underlying data structure can support. These differences pose a | |
| challenge when creating a uniform interface for priority queues. | |
| </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> | |
| Many fine associative-container libraries were already written, | |
| most notably, the C++ standard's associative containers. Why | |
| then write another library? This section shows some possible | |
| advantages of this library, when considering the challenges in | |
| the introduction. Many of these points stem from the fact that | |
| the ISO C++ process introduced associative-containers in a | |
| two-step process (first standardizing tree-based containers, | |
| only then adding hash-based containers, which are fundamentally | |
| different), did not standardize priority queues as containers, | |
| and (in our opinion) overloads the iterator concept. | |
| </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> | |
| </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> | |
| Associative containers require a relatively large number of | |
| policies to function efficiently in various settings. In some | |
| cases this is needed for making their common operations more | |
| efficient, and in other cases this allows them to support a | |
| larger set of operations | |
| </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> | |
| Hash-based containers, for example, support look-up and | |
| insertion methods (<code class="function">find</code> and | |
| <code class="function">insert</code>). In order to locate elements | |
| quickly, they are supplied a hash functor, which instruct | |
| how to transform a key object into some size type; a hash | |
| functor might transform <code class="constant">"hello"</code> | |
| into <code class="constant">1123002298</code>. A hash table, though, | |
| requires transforming each key object into some size-type | |
| type in some specific domain; a hash table with a 128-long | |
| table might transform <code class="constant">"hello"</code> into | |
| position <code class="constant">63</code>. The policy by which the | |
| hash value is transformed into a position within the table | |
| can dramatically affect performance. Hash-based containers | |
| also do not resize naturally (as opposed to tree-based | |
| containers, for example). The appropriate resize policy is | |
| unfortunately intertwined with the policy that transforms | |
| hash value into a position within the table. | |
| </p></li><li class="listitem"><p> | |
| Tree-based containers, for example, also support look-up and | |
| insertion methods, and are primarily useful when maintaining | |
| order between elements is important. In some cases, though, | |
| one can utilize their balancing algorithms for completely | |
| different purposes. | |
| </p><p> | |
| Figure A shows a tree whose each node contains two entries: | |
| a floating-point key, and some size-type | |
| <span class="emphasis"><em>metadata</em></span> (in bold beneath it) that is | |
| the number of nodes in the sub-tree. (The root has key 0.99, | |
| and has 5 nodes (including itself) in its sub-tree.) A | |
| container based on this data structure can obviously answer | |
| efficiently whether 0.3 is in the container object, but it | |
| can also answer what is the order of 0.3 among all those in | |
| the container object: see <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>. | |
| </p><p> | |
| As another example, Figure B shows a tree whose each node | |
| contains two entries: a half-open geometric line interval, | |
| and a number <span class="emphasis"><em>metadata</em></span> (in bold beneath | |
| it) that is the largest endpoint of all intervals in its | |
| sub-tree. (The root describes the interval <code class="constant">[20, | |
| 36)</code>, and the largest endpoint in its sub-tree is | |
| 99.) A container based on this data structure can obviously | |
| answer efficiently whether <code class="constant">[3, 41)</code> is | |
| in the container object, but it can also answer efficiently | |
| whether the container object has intervals that intersect | |
| <code class="constant">[3, 41)</code>. These types of queries are | |
| very useful in geometric algorithms and lease-management | |
| algorithms. | |
| </p><p> | |
| It is important to note, however, that as the trees are | |
| modified, their internal structure changes. To maintain | |
| these invariants, one must supply some policy that is aware | |
| of these changes. Without this, it would be better to use a | |
| linked list (in itself very efficient for these purposes). | |
| </p></li></ol></div><div class="figure"><a id="id-1.3.5.8.2.5.3.3.4"></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> | |
| The standard C++ library contains associative containers based on | |
| red-black trees and collision-chaining hash tables. These are | |
| very useful, but they are not ideal for all types of | |
| settings. | |
| </p><p> | |
| The figure below shows the different underlying data structures | |
| currently supported in this library. | |
| </p><div class="figure"><a id="id-1.3.5.8.2.5.3.4.4"></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> | |
| A shows a collision-chaining hash-table, B shows a probing | |
| hash-table, C shows a red-black tree, D shows a splay tree, E shows | |
| a tree based on an ordered vector (implicit in the order of the | |
| elements), F shows a PATRICIA trie, and G shows a list-based | |
| container with update policies. | |
| </p><p> | |
| Each of these data structures has some performance benefits, in | |
| terms of speed, size or both. For now, note that vector-based trees | |
| and probing hash tables manipulate memory more efficiently than | |
| red-black trees and collision-chaining hash tables, and that | |
| list-based associative containers are very useful for constructing | |
| "multimaps". | |
| </p><p> | |
| Now consider a function manipulating a generic associative | |
| container, | |
| </p><pre class="programlisting"> | |
| template<class Cntnr> | |
| int | |
| some_op_sequence(Cntnr &r_cnt) | |
| { | |
| ... | |
| } | |
| </pre><p> | |
| Ideally, the underlying data structure | |
| of <code class="classname">Cntnr</code> would not affect what can be | |
| done with <code class="varname">r_cnt</code>. Unfortunately, this is not | |
| the case. | |
| </p><p> | |
| For example, if <code class="classname">Cntnr</code> | |
| is <code class="classname">std::map</code>, then the function can | |
| use | |
| </p><pre class="programlisting"> | |
| std::for_each(r_cnt.find(foo), r_cnt.find(bar), foobar) | |
| </pre><p> | |
| in order to apply <code class="classname">foobar</code> to all | |
| elements between <code class="classname">foo</code> and | |
| <code class="classname">bar</code>. If | |
| <code class="classname">Cntnr</code> is a hash-based container, | |
| then this call's results are undefined. | |
| </p><p> | |
| Also, if <code class="classname">Cntnr</code> is tree-based, the type | |
| and object of the comparison functor can be | |
| accessed. If <code class="classname">Cntnr</code> is hash based, these | |
| queries are nonsensical. | |
| </p><p> | |
| There are various other differences based on the container's | |
| underlying data structure. For one, they can be constructed by, | |
| and queried for, different policies. Furthermore: | |
| </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> | |
| Containers based on C, D, E and F store elements in a | |
| meaningful order; the others store elements in a meaningless | |
| (and probably time-varying) order. By implication, only | |
| containers based on C, D, E and F can | |
| support <code class="function">erase</code> operations taking an | |
| iterator and returning an iterator to the following element | |
| without performance loss. | |
| </p></li><li class="listitem"><p> | |
| Containers based on C, D, E, and F can be split and joined | |
| efficiently, while the others cannot. Containers based on C | |
| and D, furthermore, can guarantee that this is exception-free; | |
| containers based on E cannot guarantee this. | |
| </p></li><li class="listitem"><p> | |
| Containers based on all but E can guarantee that | |
| erasing an element is exception free; containers based on E | |
| cannot guarantee this. Containers based on all but B and E | |
| can guarantee that modifying an object of their type does | |
| not invalidate iterators or references to their elements, | |
| while containers based on B and E cannot. Containers based | |
| on C, D, and E can furthermore make a stronger guarantee, | |
| namely that modifying an object of their type does not | |
| affect the order of iterators. | |
| </p></li></ol></div><p> | |
| A unified tag and traits system (as used for the C++ standard | |
| library iterators, for example) can ease generic manipulation of | |
| associative containers based on different underlying data | |
| structures. | |
| </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> | |
| Iterators are centric to the design of the standard library | |
| containers, because of the container/algorithm/iterator | |
| decomposition that allows an algorithm to operate on a range | |
| through iterators of some sequence. Iterators, then, are useful | |
| because they allow going over a | |
| specific <span class="emphasis"><em>sequence</em></span>. The standard library | |
| also uses iterators for accessing a | |
| specific <span class="emphasis"><em>element</em></span>: when an associative | |
| container returns one through <code class="function">find</code>. The | |
| standard library consistently uses the same types of iterators | |
| for both purposes: going over a range, and accessing a specific | |
| found element. Before the introduction of hash-based containers | |
| to the standard library, this made sense (with the exception of | |
| priority queues, which are discussed later). | |
| </p><p> | |
| Using the standard associative containers together with | |
| non-order-preserving associative containers (and also because of | |
| priority-queues container), there is a possible need for | |
| different types of iterators for self-organizing containers: | |
| the iterator concept seems overloaded to mean two different | |
| things (in some cases). | |
| </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> | |
| Suppose <code class="classname">cntnr</code> is some associative | |
| container, and say <code class="varname">c</code> is an object of | |
| type <code class="classname">cntnr</code>. Then what will be the outcome | |
| of | |
| </p><pre class="programlisting"> | |
| std::for_each(c.find(1), c.find(5), foo); | |
| </pre><p> | |
| If <code class="classname">cntnr</code> is a tree-based container | |
| object, then an in-order walk will | |
| apply <code class="classname">foo</code> to the relevant elements, | |
| as in the graphic below, label A. If <code class="varname">c</code> is | |
| a hash-based container, then the order of elements between any | |
| two elements is undefined (and probably time-varying); there is | |
| no guarantee that the elements traversed will coincide with the | |
| <span class="emphasis"><em>logical</em></span> elements between 1 and 5, as in | |
| label B. | |
| </p><div class="figure"><a id="id-1.3.5.8.2.5.3.5.4.5"></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> | |
| In our opinion, this problem is not caused just because | |
| red-black trees are order preserving while | |
| collision-chaining hash tables are (generally) not - it | |
| is more fundamental. Most of the standard's containers | |
| order sequences in a well-defined manner that is | |
| determined by their <span class="emphasis"><em>interface</em></span>: | |
| calling <code class="function">insert</code> on a tree-based | |
| container modifies its sequence in a predictable way, as | |
| does calling <code class="function">push_back</code> on a list or | |
| a vector. Conversely, collision-chaining hash tables, | |
| probing hash tables, priority queues, and list-based | |
| containers (which are very useful for "multimaps") are | |
| self-organizing data structures; the effect of each | |
| operation modifies their sequences in a manner that is | |
| (practically) determined by their | |
| <span class="emphasis"><em>implementation</em></span>. | |
| </p><p> | |
| Consequently, applying an algorithm to a sequence obtained from most | |
| containers may or may not make sense, but applying it to a | |
| sub-sequence of a self-organizing container does not. | |
| </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> | |
| Suppose <code class="varname">c</code> is some collision-chaining | |
| hash-based container object, and one calls | |
| </p><pre class="programlisting">c.find(3)</pre><p> | |
| Then what composes the returned iterator? | |
| </p><p> | |
| In the graphic below, label A shows the simplest (and | |
| most efficient) implementation of a collision-chaining | |
| hash table. The little box marked | |
| <code class="classname">point_iterator</code> shows an object | |
| that contains a pointer to the element's node. Note that | |
| this "iterator" has no way to move to the next element ( | |
| it cannot support | |
| <code class="function">operator++</code>). Conversely, the little | |
| box marked <code class="classname">iterator</code> stores both a | |
| pointer to the element, as well as some other | |
| information (the bucket number of the element). The | |
| second iterator, then, is "heavier" than the first one- | |
| it requires more time and space. If we were to use a | |
| different container to cross-reference into this | |
| hash-table using these iterators - it would take much | |
| more space. As noted above, nothing much can be done by | |
| incrementing these iterators, so why is this extra | |
| information needed? | |
| </p><p> | |
| Alternatively, one might create a collision-chaining hash-table | |
| where the lists might be linked, forming a monolithic total-element | |
| list, as in the graphic below, label B. Here the iterators are as | |
| light as can be, but the hash-table's operations are more | |
| complicated. | |
| </p><div class="figure"><a id="id-1.3.5.8.2.5.3.5.5.7"></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> | |
| It should be noted that containers based on collision-chaining | |
| hash-tables are not the only ones with this type of behavior; | |
| many other self-organizing data structures display it as well. | |
| </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"> | |
| it = c.find(3); | |
| c.erase(5); | |
| </pre><p> | |
| Following the call to <code class="classname">erase</code>, what is the | |
| validity of <code class="classname">it</code>: can it be de-referenced? | |
| can it be incremented? | |
| </p><p> | |
| The answer depends on the underlying data structure of the | |
| container. The graphic below shows three cases: A1 and A2 show | |
| a red-black tree; B1 and B2 show a probing hash-table; C1 and C2 | |
| show a collision-chaining hash table. | |
| </p><div class="figure"><a id="id-1.3.5.8.2.5.3.5.6.6"></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> | |
| Erasing 5 from A1 yields A2. Clearly, an iterator to 3 can | |
| be de-referenced and incremented. The sequence of iterators | |
| changed, but in a way that is well-defined by the interface. | |
| </p></li><li class="listitem"><p> | |
| Erasing 5 from B1 yields B2. Clearly, an iterator to 3 is | |
| not valid at all - it cannot be de-referenced or | |
| incremented; the order of iterators changed in a way that is | |
| (practically) determined by the implementation and not by | |
| the interface. | |
| </p></li><li class="listitem"><p> | |
| Erasing 5 from C1 yields C2. Here the situation is more | |
| complicated. On the one hand, there is no problem in | |
| de-referencing <code class="classname">it</code>. On the other hand, | |
| the order of iterators changed in a way that is | |
| (practically) determined by the implementation and not by | |
| the interface. | |
| </p></li></ol></div><p> | |
| So in the standard library containers, it is not always possible | |
| to express whether <code class="varname">it</code> is valid or not. This | |
| is true also for <code class="function">insert</code>. Again, the | |
| iterator concept seems overloaded. | |
| </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> | |
| </p><p> | |
| The design of the functional overlay to the underlying data | |
| structures differs slightly from some of the conventions used in | |
| the C++ standard. A strict public interface of methods that | |
| comprise only operations which depend on the class's internal | |
| structure; other operations are best designed as external | |
| functions. (See <a class="xref" href="policy_data_structures.html#biblio.meyers02both" title="Class Template, Member Template - or Both?">[biblio.meyers02both]</a>). With this | |
| rubric, the standard associative containers lack some useful | |
| methods, and provide other methods which would be better | |
| removed. | |
| </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> | |
| Order-preserving standard associative containers provide the | |
| method | |
| </p><pre class="programlisting"> | |
| iterator | |
| erase(iterator it) | |
| </pre><p> | |
| which takes an iterator, erases the corresponding | |
| element, and returns an iterator to the following | |
| element. Also standard hash-based associative | |
| containers provide this method. This seemingly | |
| increases genericity between associative containers, | |
| since it is possible to use | |
| </p><pre class="programlisting"> | |
| typename C::iterator it = c.begin(); | |
| typename C::iterator e_it = c.end(); | |
| while(it != e_it) | |
| it = pred(*it)? c.erase(it) : ++it; | |
| </pre><p> | |
| in order to erase from a container object <code class="varname"> | |
| c</code> all elements which match a | |
| predicate <code class="classname">pred</code>. However, in a | |
| different sense this actually decreases genericity: an | |
| integral implication of this method is that tree-based | |
| associative containers' memory use is linear in the total | |
| number of elements they store, while hash-based | |
| containers' memory use is unbounded in the total number of | |
| elements they store. Assume a hash-based container is | |
| allowed to decrease its size when an element is | |
| erased. Then the elements might be rehashed, which means | |
| that there is no "next" element - it is simply | |
| undefined. Consequently, it is possible to infer from the | |
| fact that the standard library's hash-based containers | |
| provide this method that they cannot downsize when | |
| elements are erased. As a consequence, different code is | |
| needed to manipulate different containers, assuming that | |
| memory should be conserved. Therefore, this library's | |
| non-order preserving associative containers omit this | |
| method. | |
| </p></li><li class="listitem"><p> | |
| All associative containers include a conditional-erase method | |
| </p><pre class="programlisting"> | |
| template< | |
| class Pred> | |
| size_type | |
| erase_if | |
| (Pred pred) | |
| </pre><p> | |
| which erases all elements matching a predicate. This is probably the | |
| only way to ensure linear-time multiple-item erase which can | |
| actually downsize a container. | |
| </p></li><li class="listitem"><p> | |
| The standard associative containers provide methods for | |
| multiple-item erase of the form | |
| </p><pre class="programlisting"> | |
| size_type | |
| erase(It b, It e) | |
| </pre><p> | |
| erasing a range of elements given by a pair of | |
| iterators. For tree-based or trie-based containers, this can | |
| be implemented more efficiently as a (small) sequence of split | |
| and join operations. For other, unordered, containers, this | |
| method isn't much better than an external loop. Moreover, | |
| if <code class="varname">c</code> is a hash-based container, | |
| then | |
| </p><pre class="programlisting"> | |
| c.erase(c.find(2), c.find(5)) | |
| </pre><p> | |
| is almost certain to do something | |
| different than erasing all elements whose keys are between 2 | |
| and 5, and is likely to produce other undefined behavior. | |
| </p></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.split"></a> | |
| <code class="function">split</code> and <code class="function">join</code> | |
| </h6></div></div></div><p> | |
| It is well-known that tree-based and trie-based container | |
| objects can be efficiently split or joined (See | |
| <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>). Externally splitting or | |
| joining trees is super-linear, and, furthermore, can throw | |
| exceptions. Split and join methods, consequently, seem good | |
| choices for tree-based container methods, especially, since as | |
| noted just before, they are efficient replacements for erasing | |
| sub-sequences. | |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.insert"></a> | |
| <code class="function">insert</code> | |
| </h6></div></div></div><p> | |
| The standard associative containers provide methods of the form | |
| </p><pre class="programlisting"> | |
| template<class It> | |
| size_type | |
| insert(It b, It e); | |
| </pre><p> | |
| for inserting a range of elements given by a pair of | |
| iterators. At best, this can be implemented as an external loop, | |
| or, even more efficiently, as a join operation (for the case of | |
| tree-based or trie-based containers). Moreover, these methods seem | |
| similar to constructors taking a range given by a pair of | |
| iterators; the constructors, however, are transactional, whereas | |
| the insert methods are not; this is possibly confusing. | |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.compare"></a> | |
| <code class="function">operator==</code> and <code class="function">operator<=</code> | |
| </h6></div></div></div><p> | |
| Associative containers are parametrized by policies allowing to | |
| test key equivalence: a hash-based container can do this through | |
| its equivalence functor, and a tree-based container can do this | |
| through its comparison functor. In addition, some standard | |
| associative containers have global function operators, like | |
| <code class="function">operator==</code> and <code class="function">operator<=</code>, | |
| that allow comparing entire associative containers. | |
| </p><p> | |
| In our opinion, these functions are better left out. To begin | |
| with, they do not significantly improve over an external | |
| loop. More importantly, however, they are possibly misleading - | |
| <code class="function">operator==</code>, for example, usually checks for | |
| equivalence, or interchangeability, but the associative | |
| container cannot check for values' equivalence, only keys' | |
| equivalence; also, are two containers considered equivalent if | |
| they store the same values in different order? This is an | |
| arbitrary decision. | |
| </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> | |
| Priority queues are containers that allow efficiently inserting | |
| values and accessing the maximal value (in the sense of the | |
| container's comparison functor). Their interface | |
| supports <code class="function">push</code> | |
| and <code class="function">pop</code>. The standard | |
| container <code class="classname">std::priority_queue</code> indeed supports | |
| these methods, but little else. For algorithmic and | |
| software-engineering purposes, other methods are needed: | |
| </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> | |
| Many graph algorithms (see | |
| <a class="xref" href="policy_data_structures.html#biblio.clrs2001" title="Introduction to Algorithms, 2nd edition">[biblio.clrs2001]</a>) require increasing a | |
| value in a priority queue (again, in the sense of the | |
| container's comparison functor), or joining two | |
| priority-queue objects. | |
| </p></li><li class="listitem"><p>The return type of <code class="classname">priority_queue</code>'s | |
| <code class="function">push</code> method is a point-type iterator, which can | |
| be used for modifying or erasing arbitrary values. For | |
| example:</p><pre class="programlisting"> | |
| priority_queue<int> p; | |
| priority_queue<int>::point_iterator it = p.push(3); | |
| p.modify(it, 4); | |
| </pre><p>These types of cross-referencing operations are necessary | |
| for making priority queues useful for different applications, | |
| especially graph applications.</p></li><li class="listitem"><p> | |
| It is sometimes necessary to erase an arbitrary value in a | |
| priority queue. For example, consider | |
| the <code class="function">select</code> function for monitoring | |
| file descriptors: | |
| </p><pre class="programlisting"> | |
| int | |
| select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds, | |
| struct timeval *timeout); | |
| </pre><p> | |
| then, as the select documentation states: | |
| </p><p> | |
| <span class="quote">“<span class="quote"> | |
| The nfds argument specifies the range of file | |
| descriptors to be tested. The select() function tests file | |
| descriptors in the range of 0 to nfds-1.</span>”</span> | |
| </p><p> | |
| It stands to reason, therefore, that we might wish to | |
| maintain a minimal value for <code class="varname">nfds</code>, and | |
| priority queues immediately come to mind. Note, though, that | |
| when a socket is closed, the minimal file description might | |
| change; in the absence of an efficient means to erase an | |
| arbitrary value from a priority queue, we might as well | |
| avoid its use altogether. | |
| </p><p> | |
| The standard containers typically support iterators. It is | |
| somewhat unusual | |
| for <code class="classname">std::priority_queue</code> to omit them | |
| (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 | |
| ask why do priority queues need to support iterators, since | |
| they are self-organizing containers with a different purpose | |
| than abstracting sequences. There are several reasons: | |
| </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p> | |
| Iterators (even in self-organizing containers) are | |
| useful for many purposes: cross-referencing | |
| containers, serialization, and debugging code that uses | |
| these containers. | |
| </p></li><li class="listitem"><p> | |
| The standard library's hash-based containers support | |
| iterators, even though they too are self-organizing | |
| containers with a different purpose than abstracting | |
| sequences. | |
| </p></li><li class="listitem"><p> | |
| In standard-library-like containers, it is natural to specify the | |
| interface of operations for modifying a value or erasing | |
| a value (discussed previously) in terms of iterators. | |
| It should be noted that the standard | |
| containers also use iterators for accessing and | |
| manipulating a specific value. In hash-based | |
| containers, one checks the existence of a key by | |
| comparing the iterator returned by <code class="function">find</code> to the | |
| iterator returned by <code class="function">end</code>, and not by comparing a | |
| pointer returned by <code class="function">find</code> to <span class="type">NULL</span>. | |
| </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> | |
| There are three main implementations of priority queues: the | |
| first employs a binary heap, typically one which uses a | |
| sequence; the second uses a tree (or forest of trees), which is | |
| typically less structured than an associative container's tree; | |
| the third simply uses an associative container. These are | |
| shown in the figure below with labels A1 and A2, B, and C. | |
| </p><div class="figure"><a id="id-1.3.5.8.2.5.4.3.3"></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> | |
| No single implementation can completely replace any of the | |
| others. Some have better <code class="function">push</code> | |
| and <code class="function">pop</code> amortized performance, some have | |
| better bounded (worst case) response time than others, some | |
| optimize a single method at the expense of others, etc. In | |
| general the "best" implementation is dictated by the specific | |
| problem. | |
| </p><p> | |
| As with associative containers, the more implementations | |
| co-exist, the more necessary a traits mechanism is for handling | |
| generic containers safely and efficiently. This is especially | |
| important for priority queues, since the invalidation guarantees | |
| of one of the most useful data structures - binary heaps - is | |
| markedly different than those of most of the others. | |
| </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> | |
| Binary heaps are one of the most useful underlying | |
| data structures for priority queues. They are very efficient in | |
| terms of memory (since they don't require per-value structure | |
| metadata), and have the best amortized <code class="function">push</code> and | |
| <code class="function">pop</code> performance for primitive types like | |
| <span class="type">int</span>. | |
| </p><p> | |
| The standard library's <code class="classname">priority_queue</code> | |
| implements this data structure as an adapter over a sequence, | |
| typically | |
| <code class="classname">std::vector</code> | |
| or <code class="classname">std::deque</code>, which correspond to labels | |
| A1 and A2 respectively in the graphic above. | |
| </p><p> | |
| This is indeed an elegant example of the adapter concept and | |
| 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 | |
| several reasons why a binary-heap priority queue | |
| may be better implemented as a container instead of a | |
| sequence adapter: | |
| </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> | |
| <code class="classname">std::priority_queue</code> cannot erase values | |
| from its adapted sequence (irrespective of the sequence | |
| type). This means that the memory use of | |
| an <code class="classname">std::priority_queue</code> object is always | |
| proportional to the maximal number of values it ever contained, | |
| and not to the number of values that it currently | |
| contains. (See <code class="filename">performance/priority_queue_text_pop_mem_usage.cc</code>.) | |
| This implementation of binary heaps acts very differently than | |
| other underlying data structures (See also pairing heaps). | |
| </p></li><li class="listitem"><p> | |
| Some combinations of adapted sequences and value types | |
| are very inefficient or just don't make sense. If one uses | |
| <code class="classname">std::priority_queue<std::vector<std::string> | |
| > ></code>, for example, then not only will each | |
| operation perform a logarithmic number of | |
| <code class="classname">std::string</code> assignments, but, furthermore, any | |
| operation (including <code class="function">pop</code>) can render the container | |
| useless due to exceptions. Conversely, if one uses | |
| <code class="classname">std::priority_queue<std::deque<int> > | |
| ></code>, then each operation incurs a logarithmic | |
| number of indirect accesses (through pointers) unnecessarily. | |
| It might be better to let the container make a conservative | |
| deduction whether to use the structure in the graphic above, labels A1 or A2. | |
| </p></li><li class="listitem"><p> | |
| There does not seem to be a systematic way to determine | |
| what exactly can be done with the priority queue. | |
| </p><div class="orderedlist"><ol class="orderedlist" type="a"><li class="listitem"><p> | |
| If <code class="classname">p</code> is a priority queue adapting an | |
| <code class="classname">std::vector</code>, then it is possible to iterate over | |
| all values by using <code class="function">&p.top()</code> and | |
| <code class="function">&p.top() + p.size()</code>, but this will not work | |
| if <code class="varname">p</code> is adapting an <code class="classname">std::deque</code>; in any | |
| case, one cannot use <code class="classname">p.begin()</code> and | |
| <code class="classname">p.end()</code>. If a different sequence is adapted, it | |
| is even more difficult to determine what can be | |
| done. | |
| </p></li><li class="listitem"><p> | |
| If <code class="varname">p</code> is a priority queue adapting an | |
| <code class="classname">std::deque</code>, then the reference returned by | |
| </p><pre class="programlisting"> | |
| p.top() | |
| </pre><p> | |
| will remain valid until it is popped, | |
| but if <code class="varname">p</code> adapts an <code class="classname">std::vector</code>, the | |
| next <code class="function">push</code> will invalidate it. If a different | |
| sequence is adapted, it is even more difficult to | |
| determine what can be done. | |
| </p></li></ol></div></li><li class="listitem"><p> | |
| Sequence-based binary heaps can still implement | |
| linear-time <code class="function">erase</code> and <code class="function">modify</code> operations. | |
| This means that if one needs to erase a small | |
| (say logarithmic) number of values, then one might still | |
| choose this underlying data structure. Using | |
| <code class="classname">std::priority_queue</code>, however, this will generally | |
| change the order of growth of the entire sequence of | |
| operations. | |
| </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> | |
| <a class="link" href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1075.pdf" target="_top"> | |
| STL Exception Handling Contract | |
| </a> | |
| </em>. </span><span class="date">1997. </span><span class="author"><span class="firstname"> | |
| Dave | |
| </span> <span class="surname"> | |
| Abrahams | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| ISO SC22/WG21 | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.alexandrescu01modern"></a><p>[biblio.alexandrescu01modern] <span class="title"><em> | |
| Modern C++ Design: Generic Programming and Design Patterns Applied | |
| </em>. </span><span class="date"> | |
| 2001 | |
| . </span><span class="author"><span class="firstname"> | |
| Andrei | |
| </span> <span class="surname"> | |
| Alexandrescu | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.andrew04mtf"></a><p>[biblio.andrew04mtf] <span class="title"><em> | |
| MTF, Bit, and COMB: A Guide to Deterministic and Randomized | |
| Algorithms for the List Update Problem | |
| </em>. </span><span class="authorgroup"><span class="firstname"> | |
| K. | |
| </span> <span class="surname"> | |
| Andrew | |
| </span> and <span class="firstname"> | |
| D. | |
| </span> <span class="surname"> | |
| Gleich | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.austern00noset"></a><p>[biblio.austern00noset] <span class="title"><em> | |
| Why You Shouldn't Use set - and What You Should Use Instead | |
| </em>. </span><span class="date"> | |
| April, 2000 | |
| . </span><span class="author"><span class="firstname"> | |
| Matthew | |
| </span> <span class="surname"> | |
| Austern | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| C++ Report | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.austern01htprop"></a><p>[biblio.austern01htprop] <span class="title"><em> | |
| <a class="link" href="https://www.open-std.org/JTC1/sc22/wg21/docs/papers/2001/n1326.html" target="_top"> | |
| A Proposal to Add Hashtables to the Standard Library | |
| </a> | |
| </em>. </span><span class="date"> | |
| 2001 | |
| . </span><span class="author"><span class="firstname"> | |
| Matthew | |
| </span> <span class="surname"> | |
| Austern | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| ISO SC22/WG21 | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.austern98segmentedit"></a><p>[biblio.austern98segmentedit] <span class="title"><em> | |
| Segmented iterators and hierarchical algorithms | |
| </em>. </span><span class="date"> | |
| April, 1998 | |
| . </span><span class="author"><span class="firstname"> | |
| Matthew | |
| </span> <span class="surname"> | |
| Austern | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Generic Programming | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.dawestimer"></a><p>[biblio.dawestimer] <span class="title"><em> | |
| <a class="link" href="http://www.boost.org/libs/timer/" target="_top"> | |
| Boost Timer Library | |
| </a> | |
| </em>. </span><span class="author"><span class="firstname"> | |
| Beeman | |
| </span> <span class="surname"> | |
| Dawes | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Boost | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.clearypool"></a><p>[biblio.clearypool] <span class="title"><em> | |
| <a class="link" href="http://www.boost.org/libs/pool/" target="_top"> | |
| Boost Pool Library | |
| </a> | |
| </em>. </span><span class="author"><span class="firstname"> | |
| Stephen | |
| </span> <span class="surname"> | |
| Cleary | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Boost | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.maddocktraits"></a><p>[biblio.maddocktraits] <span class="title"><em> | |
| <a class="link" href="http://www.boost.org/libs/type_traits/" target="_top"> | |
| Boost Type Traits Library | |
| </a> | |
| </em>. </span><span class="authorgroup"><span class="firstname"> | |
| Maddock | |
| </span> <span class="surname"> | |
| John | |
| </span> and <span class="firstname"> | |
| Stephen | |
| </span> <span class="surname"> | |
| Cleary | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Boost | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.brodal96priority"></a><p>[biblio.brodal96priority] <span class="title"><em> | |
| <a class="link" href="https://dl.acm.org/doi/10.5555/313852.313883" target="_top"> | |
| Worst-case efficient priority queues | |
| </a> | |
| </em>. </span><span class="author"><span class="firstname"> | |
| Gerth | |
| </span> <span class="surname"> | |
| Stolting Brodal | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.bulkamayheweff"></a><p>[biblio.bulkamayheweff] <span class="title"><em> | |
| Efficient C++ Programming Techniques | |
| </em>. </span><span class="date"> | |
| 1997 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| D. | |
| </span> <span class="surname"> | |
| Bulka | |
| </span> and <span class="firstname"> | |
| D. | |
| </span> <span class="surname"> | |
| Mayhew | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.clrs2001"></a><p>[biblio.clrs2001] <span class="title"><em> | |
| Introduction to Algorithms, 2nd edition | |
| </em>. </span><span class="date"> | |
| 2001 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| T. H. | |
| </span> <span class="surname"> | |
| Cormen | |
| </span>, <span class="firstname"> | |
| C. E. | |
| </span> <span class="surname"> | |
| Leiserson | |
| </span>, <span class="firstname"> | |
| R. L. | |
| </span> <span class="surname"> | |
| Rivest | |
| </span>, and <span class="firstname"> | |
| C. | |
| </span> <span class="surname"> | |
| Stein | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| MIT Press | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.dubhashi98neg"></a><p>[biblio.dubhashi98neg] <span class="title"><em> | |
| Balls and bins: A study in negative dependence | |
| </em>. </span><span class="date"> | |
| 1998 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| D. | |
| </span> <span class="surname"> | |
| Dubashi | |
| </span> and <span class="firstname"> | |
| D. | |
| </span> <span class="surname"> | |
| Ranjan | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Random Structures and Algorithms 13 | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.fagin79extendible"></a><p>[biblio.fagin79extendible] <span class="title"><em> | |
| Extendible hashing - a fast access method for dynamic files | |
| </em>. </span><span class="date"> | |
| 1979 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| R. | |
| </span> <span class="surname"> | |
| Fagin | |
| </span>, <span class="firstname"> | |
| J. | |
| </span> <span class="surname"> | |
| Nievergelt | |
| </span>, <span class="firstname"> | |
| N. | |
| </span> <span class="surname"> | |
| Pippenger | |
| </span>, and <span class="firstname"> | |
| H. R. | |
| </span> <span class="surname"> | |
| Strong | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| ACM Trans. Database Syst. 4 | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.filliatre2000ptset"></a><p>[biblio.filliatre2000ptset] <span class="title"><em> | |
| <a class="link" href="http://cristal.inria.fr/~frisch/icfp06_contest/advtr/applyOmatic/ptset.ml" target="_top"> | |
| Ptset: Sets of integers implemented as Patricia trees | |
| </a> | |
| </em>. </span><span class="date"> | |
| 2000 | |
| . </span><span class="author"><span class="firstname"> | |
| Jean-Christophe | |
| </span> <span class="surname"> | |
| Filliatre | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.fredman86pairing"></a><p>[biblio.fredman86pairing] <span class="title"><em> | |
| <a class="link" href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf" target="_top"> | |
| The pairing heap: a new form of self-adjusting heap | |
| </a> | |
| </em>. </span><span class="date"> | |
| 1986 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| M. L. | |
| </span> <span class="surname"> | |
| Fredman | |
| </span>, <span class="firstname"> | |
| R. | |
| </span> <span class="surname"> | |
| Sedgewick | |
| </span>, <span class="firstname"> | |
| D. D. | |
| </span> <span class="surname"> | |
| Sleator | |
| </span>, and <span class="firstname"> | |
| R. E. | |
| </span> <span class="surname"> | |
| Tarjan | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.gof"></a><p>[biblio.gof] <span class="title"><em> | |
| Design Patterns - Elements of Reusable Object-Oriented Software | |
| </em>. </span><span class="date"> | |
| 1995 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| E. | |
| </span> <span class="surname"> | |
| Gamma | |
| </span>, <span class="firstname"> | |
| R. | |
| </span> <span class="surname"> | |
| Helm | |
| </span>, <span class="firstname"> | |
| R. | |
| </span> <span class="surname"> | |
| Johnson | |
| </span>, and <span class="firstname"> | |
| J. | |
| </span> <span class="surname"> | |
| Vlissides | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.garg86order"></a><p>[biblio.garg86order] <span class="title"><em> | |
| Order-preserving key transformations | |
| </em>. </span><span class="date"> | |
| 1986 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| A. K. | |
| </span> <span class="surname"> | |
| Garg | |
| </span> and <span class="firstname"> | |
| C. C. | |
| </span> <span class="surname"> | |
| Gotlieb | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Trans. Database Syst. 11 | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.hyslop02making"></a><p>[biblio.hyslop02making] <span class="title"><em> | |
| Making a real hash of things | |
| </em>. </span><span class="date"> | |
| May 2002 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| J. | |
| </span> <span class="surname"> | |
| Hyslop | |
| </span> and <span class="firstname"> | |
| Herb | |
| </span> <span class="surname"> | |
| Sutter | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| C++ Report | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.jossutis01stl"></a><p>[biblio.jossutis01stl] <span class="title"><em> | |
| The C++ Standard Library - A Tutorial and Reference | |
| </em>. </span><span class="date"> | |
| 2001 | |
| . </span><span class="author"><span class="firstname"> | |
| N. M. | |
| </span> <span class="surname"> | |
| Jossutis | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.kt99fat_heaps"></a><p>[biblio.kt99fat_heaps] <span class="title"><em> | |
| <a class="link" href="https://www.cs.princeton.edu/research/techreps/293" target="_top"> | |
| New Heap Data Structures | |
| </a> | |
| </em>. </span><span class="date"> | |
| 1999 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| Haim | |
| </span> <span class="surname"> | |
| Kaplan | |
| </span> and <span class="firstname"> | |
| Robert E. | |
| </span> <span class="surname"> | |
| Tarjan | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.kleft00sets"></a><p>[biblio.kleft00sets] <span class="title"><em> | |
| Are Set Iterators Mutable or Immutable? | |
| </em>. </span><span class="date"> | |
| October 2000 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| Angelika | |
| </span> <span class="surname"> | |
| Langer | |
| </span> and <span class="firstname"> | |
| Klaus | |
| </span> <span class="surname"> | |
| Kleft | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| C/C++ Users Jornal | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.knuth98sorting"></a><p>[biblio.knuth98sorting] <span class="title"><em> | |
| The Art of Computer Programming - Sorting and Searching | |
| </em>. </span><span class="date"> | |
| 1998 | |
| . </span><span class="author"><span class="firstname"> | |
| D. E. | |
| </span> <span class="surname"> | |
| Knuth | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.liskov98data"></a><p>[biblio.liskov98data] <span class="title"><em> | |
| Data abstraction and hierarchy | |
| </em>. </span><span class="date"> | |
| May 1998 | |
| . </span><span class="author"><span class="firstname"> | |
| B. | |
| </span> <span class="surname"> | |
| Liskov | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| SIGPLAN Notices 23 | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.litwin80lh"></a><p>[biblio.litwin80lh] <span class="title"><em> | |
| Linear hashing: A new tool for file and table addressing | |
| </em>. </span><span class="date"> | |
| June 1980 | |
| . </span><span class="author"><span class="firstname"> | |
| W. | |
| </span> <span class="surname"> | |
| Litwin | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Proceedings of International Conference on Very Large Data Bases | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.maverick_lowerbounds"></a><p>[biblio.maverick_lowerbounds] <span class="title"><em> | |
| Deamortization - Part 2: Binomial Heaps | |
| </em>. </span><span class="date"> | |
| 2005 | |
| . </span><span class="author"><span class="firstname"> | |
| Maverick | |
| </span> <span class="surname"> | |
| Woo | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.meyers96more"></a><p>[biblio.meyers96more] <span class="title"><em> | |
| More Effective C++: 35 New Ways to Improve Your Programs and Designs | |
| </em>. </span><span class="date"> | |
| 1996 | |
| . </span><span class="author"><span class="firstname"> | |
| Scott | |
| </span> <span class="surname"> | |
| Meyers | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers00nonmember"></a><p>[biblio.meyers00nonmember] <span class="title"><em> | |
| How Non-Member Functions Improve Encapsulation | |
| </em>. </span><span class="date"> | |
| 2000 | |
| . </span><span class="author"><span class="firstname"> | |
| Scott | |
| </span> <span class="surname"> | |
| Meyers | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| C/C++ Users Journal | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers01stl"></a><p>[biblio.meyers01stl] <span class="title"><em> | |
| Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library | |
| </em>. </span><span class="date"> | |
| 2001 | |
| . </span><span class="author"><span class="firstname"> | |
| Scott | |
| </span> <span class="surname"> | |
| Meyers | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.meyers02both"></a><p>[biblio.meyers02both] <span class="title"><em> | |
| Class Template, Member Template - or Both? | |
| </em>. </span><span class="date"> | |
| 2003 | |
| . </span><span class="author"><span class="firstname"> | |
| Scott | |
| </span> <span class="surname"> | |
| Meyers | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| C/C++ Users Journal | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.motwani95random"></a><p>[biblio.motwani95random] <span class="title"><em> | |
| Randomized Algorithms | |
| </em>. </span><span class="date"> | |
| 2003 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| R. | |
| </span> <span class="surname"> | |
| Motwani | |
| </span> and <span class="firstname"> | |
| P. | |
| </span> <span class="surname"> | |
| Raghavan | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Cambridge University Press | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.mscom"></a><p>[biblio.mscom] <span class="title"><em> | |
| <a class="link" href="https://learn.microsoft.com/en-us/windows/win32/com/the-component-object-model" target="_top"> | |
| The Component Object Model | |
| </a> | |
| </em>. </span><span class="publisher"><span class="publishername"> | |
| Microsoft | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.musser95rationale"></a><p>[biblio.musser95rationale] <span class="title"><em> | |
| Rationale for Adding Hash Tables to the C++ Standard Template Library | |
| </em>. </span><span class="date"> | |
| 1995 | |
| . </span><span class="author"><span class="firstname"> | |
| David R. | |
| </span> <span class="surname"> | |
| Musser | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.musser96stltutorial"></a><p>[biblio.musser96stltutorial] <span class="title"><em> | |
| STL Tutorial and Reference Guide | |
| </em>. </span><span class="date"> | |
| 1996 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| David R. | |
| </span> <span class="surname"> | |
| Musser | |
| </span> and <span class="firstname"> | |
| A. | |
| </span> <span class="surname"> | |
| Saini | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.nelson96stlpq"></a><p>[biblio.nelson96stlpq] <span class="title"><em> | |
| <a class="link" href="https://web.archive.org/web/20240806213010/https://marknelson.us/posts/1996/01/01/priority-queues.html" target="_top">Priority Queues and the STL | |
| </a> | |
| </em>. </span><span class="date"> | |
| January 1996 | |
| . </span><span class="author"><span class="firstname"> | |
| Mark | |
| </span> <span class="surname"> | |
| Nelson | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Dr. Dobbs Journal | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.okasaki98mereable"></a><p>[biblio.okasaki98mereable] <span class="title"><em> | |
| Fast mergeable integer maps | |
| </em>. </span><span class="date"> | |
| September 1998 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| C. | |
| </span> <span class="surname"> | |
| Okasaki | |
| </span> and <span class="firstname"> | |
| A. | |
| </span> <span class="surname"> | |
| Gill | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| In Workshop on ML | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.sgi_stl"></a><p>[biblio.sgi_stl] <span class="title"><em> | |
| <a class="link" href="https://web.archive.org/web/20171225062613/http://www.sgi.com/tech/stl/" target="_top"> | |
| Standard Template Library Programmer's Guide | |
| </a> | |
| </em>. </span><span class="author"><span class="firstname"> | |
| Matt | |
| </span> <span class="surname"> | |
| Austern | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| SGI | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.select_man"></a><p>[biblio.select_man] <span class="title"><em> | |
| <a class="link" href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/select.html" target="_top"> | |
| select | |
| </a> | |
| </em>. </span></p></div><div class="biblioentry"><a id="biblio.sleator84amortized"></a><p>[biblio.sleator84amortized] <span class="title"><em> | |
| Amortized Efficiency of List Update Problems | |
| </em>. </span><span class="date"> | |
| 1984 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| D. D. | |
| </span> <span class="surname"> | |
| Sleator | |
| </span> and <span class="firstname"> | |
| R. E. | |
| </span> <span class="surname"> | |
| Tarjan | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| ACM Symposium on Theory of Computing | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.sleator85self"></a><p>[biblio.sleator85self] <span class="title"><em> | |
| Self-Adjusting Binary Search Trees | |
| </em>. </span><span class="date"> | |
| 1985 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| D. D. | |
| </span> <span class="surname"> | |
| Sleator | |
| </span> and <span class="firstname"> | |
| R. E. | |
| </span> <span class="surname"> | |
| Tarjan | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| ACM Symposium on Theory of Computing | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.stepanov94standard"></a><p>[biblio.stepanov94standard] <span class="title"><em> | |
| The Standard Template Library | |
| </em>. </span><span class="date"> | |
| 1984 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| A. A. | |
| </span> <span class="surname"> | |
| Stepanov | |
| </span> and <span class="firstname"> | |
| M. | |
| </span> <span class="surname"> | |
| Lee | |
| </span>. </span></p></div><div class="biblioentry"><a id="biblio.stroustrup97cpp"></a><p>[biblio.stroustrup97cpp] <span class="title"><em> | |
| The C++ Programming Langugage | |
| </em>. </span><span class="date"> | |
| 1997 | |
| . </span><span class="author"><span class="firstname"> | |
| Bjarne | |
| </span> <span class="surname"> | |
| Stroustrup | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.vandevoorde2002cpptemplates"></a><p>[biblio.vandevoorde2002cpptemplates] <span class="title"><em> | |
| C++ Templates: The Complete Guide | |
| </em>. </span><span class="date"> | |
| 2002 | |
| . </span><span class="authorgroup"><span class="firstname"> | |
| D. | |
| </span> <span class="surname"> | |
| Vandevoorde | |
| </span> and <span class="firstname"> | |
| N. M. | |
| </span> <span class="surname"> | |
| Josuttis | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| Addison-Wesley Publishing Company | |
| . </span></span></p></div><div class="biblioentry"><a id="biblio.wickland96thirty"></a><p>[biblio.wickland96thirty] <span class="title"><em> | |
| Thirty Years Among the Dead | |
| </em>. </span><span class="date"> | |
| 1996 | |
| . </span><span class="author"><span class="firstname"> | |
| C. A. | |
| </span> <span class="surname"> | |
| Wickland | |
| </span>. </span><span class="publisher"><span class="publishername"> | |
| National Psychological Institute | |
| . </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> |