| <?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 21. 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 21. 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 21. 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"> |
| 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 unamibiguously 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 Que</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 21.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 21.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 21.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 21.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 21.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 standardd hash-based associative |
| containers provide this method. This seemingly |
| increasesgenericity 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 element 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. Therefor, 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 |
| 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::priorityqueue</code> indeed support |
| 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 a 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 21.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 uses 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 return 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="http://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="http://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/citation.cfm?id=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/TR-597-99" 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://docs.microsoft.com/en-us/windows/win32/com/the-component-object-model" target="_top"> |
| COM: Component Model Object Technologies |
| </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://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> |
