-<?xml version="1.0" encoding="UTF-8" standalone="no"?>
-<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Chapter 22. Policy-Based Data Structures</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content=" 	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="bk01pt03ch21s02.html" title="Implementation"/><link rel="next" href="policy_data_structures_using.html" title="Using"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 22. Policy-Based Data Structures</th></tr><tr><td align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><th width="60%" align="center">Part III.
+<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Chapter 22. Policy-Based Data Structures</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"><meta name="keywords" content="
+ 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="bk01pt03ch21s02.html" title="Implementation"><link rel="next" href="policy_data_structures_using.html" title="Using"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 22. Policy-Based Data Structures</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><th width="60%" align="center">Part III.
Extensions
-</th><td
align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr></table><hr/></div><div class="chapter" title="Chapter 22. Policy-Based Data Structures"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.containers.pbds"/>Chapter 22. Policy-Based Data Structures</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
+</th><td
width="20%" align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr></table><hr></div><div class="chapter" title="Chapter 22. Policy-Based Data Structures"><div class="titlepage"><div><div><h2 class="title"><a name="manual.ext.containers.pbds"></a>Chapter 22. Policy-Based Data Structures</h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
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
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_biblio.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" title="Intro"><div class="titlepage"><div><div><h2 class="title"
><a id="pbds.intro"/>Intro</h2></div></div></div><p>
+ </a></span></dt></dl></div><div class="section" title="Intro"><div class="titlepage"><div><div><h2 class="title"
style="clear: both"><a name="pbds.intro"></a>Intro</h2></div></div></div><p>
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
<code class="literal">std::tr1</code> (except for some points where it differs
by design).
</p><p>
- </p><div class="section" title="Performance Issues"><div class="titlepage"><div><div><h3 class="title"><a
id="pbds.intro.issues"/>Performance Issues</h3></div></div></div><p>
+ </p><div class="section" title="Performance Issues"><div class="titlepage"><div><div><h3 class="title"><a
name="pbds.intro.issues"></a>Performance Issues</h3></div></div></div><p>
</p><p>
An attempt is made to categorize the wide variety of possible
container designs in terms of performance-impacting factors. These
</p><p>
Specific issues found while unraveling performance factors in the
design of associative containers and priority queues follow.
- </p><div class="section" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a
id="pbds.intro.issues.associative"/>Associative</h4></div></div></div><p>
+ </p><div class="section" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a
name="pbds.intro.issues.associative"></a>Associative</h4></div></div></div><p>
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
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" title="Priority Que"><div class="titlepage"><div><div><h4 class="title"><a
id="pbds.intro.issues.priority_queue"/>Priority Que</h4></div></div></div><p>
+ </p></div><div class="section" title="Priority Que"><div class="titlepage"><div><div><h4 class="title"><a
name="pbds.intro.issues.priority_queue"></a>Priority Que</h4></div></div></div><p>
Priority queues are useful when one needs to efficiently access a
minimum (or maximum) value as the set of values changes.
</p><p>
expense of more difference in the 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" title="Goals"><div class="titlepage"><div><div><h3 class="title"><a
id="pbds.intro.motivation"/>Goals</h3></div></div></div><p>
+ </p></div></div><div class="section" title="Goals"><div class="titlepage"><div><div><h3 class="title"><a
name="pbds.intro.motivation"></a>Goals</h3></div></div></div><p>
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
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" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a
id="pbds.intro.motivation.associative"/>Associative</h4></div></div></div><p>
- </p><div class="section" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a
id="motivation.associative.policy"/>Policy Choices</h5></div></div></div><p>
+ </p><div class="section" title="Associative"><div class="titlepage"><div><div><h4 class="title"><a
name="pbds.intro.motivation.associative"></a>Associative</h4></div></div></div><p>
+ </p><div class="section" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a
name="motivation.associative.policy"></a>Policy Choices</h5></div></div></div><p>
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"><li class="listitem"><p>
+ </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
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="id527047"/><p class="title"><strong>Figure 22.1. Node Invariants</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_node_invariants.png" style="text-align: middle" alt="Node Invariants"/></div></div></div><br class="figure-break"/></div><div class="section" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.associative.underlying"/>Underlying Data Structures</h5></div></div></div><p>
+ </p></li></ol></div><div class="figure"><a
name="id640366"></a><p class="title"><b>Figure 22.1. Node Invariants</b></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_node_invariants.png" align="middle" alt="Node Invariants"></div></div></div><br class="figure-break"></div><div class="section" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a name="motivation.associative.underlying"></a>Underlying Data Structures</h5></div></div></div><p>
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
</p><p>
The figure below shows the different underlying data structures
currently supported in this library.
- </p><div class="figure"><a
id="id527103"/><p class="title"><strong>Figure 22.2. Underlying Associative Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_different_underlying_dss_1.png" style="text-align: middle" alt="Underlying Associative Data Structures"/></div></div></div><br class="figure-break"/><p>
+ </p><div class="figure"><a
name="id640422"></a><p class="title"><b>Figure 22.2. Underlying Associative Data Structures</b></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_different_underlying_dss_1.png" align="middle" alt="Underlying Associative Data Structures"></div></div></div><br class="figure-break"><p>
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
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"><li class="listitem"><p>
+ </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
library iterators, for example) can ease generic manipulation of
associative containers based on different underlying data
structures.
- </p></div><div class="section" title="Iterators"><div class="titlepage"><div><div><h5 class="title"><a
id="motivation.associative.iterators"/>Iterators</h5></div></div></div><p>
+ </p></div><div class="section" title="Iterators"><div class="titlepage"><div><div><h5 class="title"><a
name="motivation.associative.iterators"></a>Iterators</h5></div></div></div><p>
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
"ds_gen.html#find_range">Design::Associative
Containers::Data-Structure Genericity::Point-Type and Range-Type
Methods</span></em>.
- </p><div class="section" title="Using Point Iterators for Range Operations"><div class="titlepage"><div><div><h6 class="title"><a
id="associative.iterators.using"/>Using Point Iterators for Range Operations</h6></div></div></div><p>
+ </p><div class="section" title="Using Point Iterators for Range Operations"><div class="titlepage"><div><div><h6 class="title"><a
name="associative.iterators.using"></a>Using Point Iterators for Range Operations</h6></div></div></div><p>
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
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="id527366"/><p class="title"><strong>Figure 22.3. Range Iteration in Different Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_point_iterators_range_ops_1.png" style="text-align: middle" alt="Node Invariants"/></div></div></div><br class="figure-break"/><p>
+ </p><div class="figure"><a
name="id640685"></a><p class="title"><b>Figure 22.3. Range Iteration in Different Data Structures</b></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_point_iterators_range_ops_1.png" align="middle" alt="Node Invariants"></div></div></div><br class="figure-break"><p>
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
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" title="Cost to Point Iterators to Enable Range Operations"><div class="titlepage"><div><div><h6 class="title"><a
id="associative.iterators.cost"/>Cost to Point Iterators to Enable Range Operations</h6></div></div></div><p>
+ </p></div><div class="section" title="Cost to Point Iterators to Enable Range Operations"><div class="titlepage"><div><div><h6 class="title"><a
name="associative.iterators.cost"></a>Cost to Point Iterators to Enable Range Operations</h6></div></div></div><p>
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>
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="id527491"/><p class="title"><strong>Figure 22.4. Point Iteration in Hash Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_point_iterators_range_ops_2.png" style="text-align: middle" alt="Point Iteration in Hash Data Structures"/></div></div></div><br class="figure-break"/><p>
+ </p><div class="figure"><a
name="id640809"></a><p class="title"><b>Figure 22.4. Point Iteration in Hash Data Structures</b></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_point_iterators_range_ops_2.png" align="middle" alt="Point Iteration in Hash Data Structures"></div></div></div><br class="figure-break"><p>
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" title="Invalidation Guarantees"><div class="titlepage"><div><div><h6 class="title"><a
id="associative.iterators.invalidation"/>Invalidation Guarantees</h6></div></div></div><p>Consider the following snippet:</p><pre class="programlisting">
+ </p></div><div class="section" title="Invalidation Guarantees"><div class="titlepage"><div><div><h6 class="title"><a
name="associative.iterators.invalidation"></a>Invalidation Guarantees</h6></div></div></div><p>Consider the following snippet:</p><pre class="programlisting">
it = c.find(3);
c.erase(5);
</pre><p>
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="id527568"/><p class="title"><strong>Figure 22.5. Effect of erase in different underlying data structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_invalidation_guarantee_erase.png" style="text-align: middle" alt="Effect of erase in different underlying data structures"/></div></div></div><br class="figure-break"/><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
+ </p><div class="figure"><a
name="id640886"></a><p class="title"><b>Figure 22.5. Effect of erase in different underlying data structures</b></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_invalidation_guarantee_erase.png" align="middle" alt="Effect of erase in different underlying data structures"></div></div></div><br class="figure-break"><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
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.
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" title="Functional"><div class="titlepage"><div><div><h5 class="title"><a
id="motivation.associative.functions"/>Functional</h5></div></div></div><p>
+ </p></div></div><div class="section" title="Functional"><div class="titlepage"><div><div><h5 class="title"><a
name="motivation.associative.functions"></a>Functional</h5></div></div></div><p>
</p><p>
The design of the functional overlay to the underlying data
structures differs slightly from some of the conventions used in
rubric, the standard associative containers lack some useful
methods, and provide other methods which would be better
removed.
- </p><div class="section" title="erase"><div class="titlepage"><div><div><h6 class="title"><a
id="motivation.associative.functions.erase"/><code class="function">erase</code></h6></div></div></div><div class="orderedlist"><ol class="orderedlist"><li class="listitem"><p>
+ </p><div class="section" title="erase"><div class="titlepage"><div><div><h6 class="title"><a
name="motivation.associative.functions.erase"></a><code class="function">erase</code></h6></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
Order-preserving standard associative containers provide the
method
</p><pre class="programlisting">
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" title="split and join"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.split"/>
+ </p></li></ol></div></div><div class="section" title="split and join"><div class="titlepage"><div><div><h6 class="title"><a name="motivation.associative.functions.split"></a>
<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
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" title="insert"><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.insert"/>
+ </p></div><div class="section" title="insert"><div class="titlepage"><div><div><h6 class="title"><a name="motivation.associative.functions.insert"></a>
<code class="function">insert</code>
</h6></div></div></div><p>
The standard associative containers provide methods of the form
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" title="operator== and operator<="><div class="titlepage"><div><div><h6 class="title"><a id="motivation.associative.functions.compare"/>
+ </p></div><div class="section" title="operator== and operator<="><div class="titlepage"><div><div><h6 class="title"><a name="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
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" title="Priority Queues"><div class="titlepage"><div><div><h4 class="title"><a
id="pbds.intro.motivation.priority_queue"/>Priority Queues</h4></div></div></div><div class="section" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.policy"/>Policy Choices</h5></div></div></div><p>
+ </p></div></div></div><div class="section" title="Priority Queues"><div class="titlepage"><div><div><h4 class="title"><a
name="pbds.intro.motivation.priority_queue"></a>Priority Queues</h4></div></div></div><div class="section" title="Policy Choices"><div class="titlepage"><div><div><h5 class="title"><a name="motivation.priority_queue.policy"></a>Policy Choices</h5></div></div></div><p>
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
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"><li class="listitem"><p>
+ </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
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"><li class="listitem"><p>
+ </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
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" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a
id="motivation.priority_queue.underlying"/>Underlying Data Structures</h5></div></div></div><p>
+ </p></li></ol></div></li></ol></div></div><div class="section" title="Underlying Data Structures"><div class="titlepage"><div><div><h5 class="title"><a
name="motivation.priority_queue.underlying"></a>Underlying Data Structures</h5></div></div></div><p>
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="id528131"/><p class="title"><strong>Figure 22.6. Underlying Priority Queue Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" style="text-align: center"><img src="../images/pbds_different_underlying_dss_2.png" style="text-align: middle" alt="Underlying Priority Queue Data Structures"/></div></div></div><br class="figure-break"/><p>
+ </p><div class="figure"><a
name="id641449"></a><p class="title"><b>Figure 22.6. Underlying Priority Queue Data Structures</b></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_different_underlying_dss_2.png" align="middle" alt="Underlying Priority Queue Data Structures"></div></div></div><br class="figure-break"><p>
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
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" title="Binary Heaps"><div class="titlepage"><div><div><h5 class="title"><a
id="motivation.priority_queue.binary_heap"/>Binary Heaps</h5></div></div></div><p>
+ </p></div><div class="section" title="Binary Heaps"><div class="titlepage"><div><div><h5 class="title"><a
name="motivation.priority_queue.binary_heap"></a>Binary Heaps</h5></div></div></div><p>
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
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"><li class="listitem"><p>
+ </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
</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"><li class="listitem"><p>
+ </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="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" title="Bibliography"><div class="titlepage"><div><div><h2 class="title"><a id="pbds.biblio"/>
+ </p></li></ol></div></div></div></div></div><div class="bibliography" title="Bibliography"><div class="titlepage"><div><div><h2 class="title"><a name="pbds.biblio"></a>
Bibliography
- </h2></div></div></div><div class="biblioentry" title="STL Exception Handling Contract"><a id="biblio.abrahams97exception"/><p>[biblio.abrahams97exception] <span class="title"><em>
- <a class="link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1075.pdf">
+ </h2></div></div></div><div class="biblioentry" title="STL Exception Handling Contract"><a name="biblio.abrahams97exception"></a><p>[biblio.abrahams97exception] <span class="title"><i>
+ <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">
+ </i>. </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" title="Modern C++ Design: Generic Programming and Design Patterns Applied"><a id="biblio.alexandrescu01modern"/><p>[biblio.alexandrescu01modern] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Modern C++ Design: Generic Programming and Design Patterns Applied"><a name="biblio.alexandrescu01modern"></a><p>[biblio.alexandrescu01modern] <span class="title"><i>
Modern C++ Design: Generic Programming and Design Patterns Applied
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2001
. </span><span class="author"><span class="firstname">
Andrei
Alexandrescu
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="MTF, Bit, and COMB: A Guide to Deterministic and Randomized Algorithms for the List Update Problem"><a id="biblio.andrew04mtf"/><p>[biblio.andrew04mtf] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="MTF, Bit, and COMB: A Guide to Deterministic and Randomized Algorithms for the List Update Problem"><a name="biblio.andrew04mtf"></a><p>[biblio.andrew04mtf] <span class="title"><i>
MTF, Bit, and COMB: A Guide to Deterministic and Randomized
Algorithms for the List Update Problem
- </em>. </span><span class="authorgroup"><span class="firstname">
+ </i>. </span><span class="authorgroup"><span class="firstname">
K.
</span> <span class="surname">
Andrew
D.
</span> <span class="surname">
Gleich
- </span>. </span></p></div><div class="biblioentry" title="Why You Shouldn't Use set - and What You Should Use Instead"><a id="biblio.austern00noset"/><p>[biblio.austern00noset] <span class="title"><em>
+ </span>. </span></p></div><div class="biblioentry" title="Why You Shouldn't Use set - and What You Should Use Instead"><a name="biblio.austern00noset"></a><p>[biblio.austern00noset] <span class="title"><i>
Why You Shouldn't Use set - and What You Should Use Instead
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
April, 2000
. </span><span class="author"><span class="firstname">
Matthew
Austern
</span>. </span><span class="publisher"><span class="publishername">
C++ Report
- . </span></span></p></div><div class="biblioentry" title="A Proposal to Add Hashtables to the Standard Library"><a id="biblio.austern01htprop"/><p>[biblio.austern01htprop] <span class="title"><em>
- <a class="link" href="http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2001/n1326.html">
+ . </span></span></p></div><div class="biblioentry" title="A Proposal to Add Hashtables to the Standard Library"><a name="biblio.austern01htprop"></a><p>[biblio.austern01htprop] <span class="title"><i>
+ <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">
+ </i>. </span><span class="date">
2001
. </span><span class="author"><span class="firstname">
Matthew
Austern
</span>. </span><span class="publisher"><span class="publishername">
ISO SC22/WG21
- . </span></span></p></div><div class="biblioentry" title="Segmented iterators and hierarchical algorithms"><a id="biblio.austern98segmentedit"/><p>[biblio.austern98segmentedit] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Segmented iterators and hierarchical algorithms"><a name="biblio.austern98segmentedit"></a><p>[biblio.austern98segmentedit] <span class="title"><i>
Segmented iterators and hierarchical algorithms
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
April, 1998
. </span><span class="author"><span class="firstname">
Matthew
Austern
</span>. </span><span class="publisher"><span class="publishername">
Generic Programming
- . </span></span></p></div><div class="biblioentry" title="Boost Timer Library"><a id="biblio.dawestimer"/><p>[biblio.dawestimer] <span class="title"><em>
- <a class="link" href="www.boost.org/doc/libs/release/libs/timer/">
+ . </span></span></p></div><div class="biblioentry" title="Boost Timer Library"><a name="biblio.dawestimer"></a><p>[biblio.dawestimer] <span class="title"><i>
+ <a class="link" href="www.boost.org/doc/libs/release/libs/timer/" target="_top">
Boost Timer Library
</a>
- </em>. </span><span class="author"><span class="firstname">
+ </i>. </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" title="Boost Pool Library"><a id="biblio.clearypool"/><p>[biblio.clearypool] <span class="title"><em>
- <a class="link" href="www.boost.org/doc/libs/release/libs/pool/">
+ . </span></span></p></div><div class="biblioentry" title="Boost Pool Library"><a name="biblio.clearypool"></a><p>[biblio.clearypool] <span class="title"><i>
+ <a class="link" href="www.boost.org/doc/libs/release/libs/pool/" target="_top">
Boost Pool Library
</a>
- </em>. </span><span class="author"><span class="firstname">
+ </i>. </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" title="Boost Type Traits Library"><a id="biblio.maddocktraits"/><p>[biblio.maddocktraits] <span class="title"><em>
- <a class="link" href="www.boost.org/doc/libs/release/libs/type_traits/">
+ . </span></span></p></div><div class="biblioentry" title="Boost Type Traits Library"><a name="biblio.maddocktraits"></a><p>[biblio.maddocktraits] <span class="title"><i>
+ <a class="link" href="www.boost.org/doc/libs/release/libs/type_traits/" target="_top">
Boost Type Traits Library
</a>
- </em>. </span><span class="authorgroup"><span class="firstname">
+ </i>. </span><span class="authorgroup"><span class="firstname">
Maddock
</span> <span class="surname">
John
Cleary
</span>. </span><span class="publisher"><span class="publishername">
Boost
- . </span></span></p></div><div class="biblioentry" title="Worst-case efficient priority queues"><a id="biblio.brodal96priority"/><p>[biblio.brodal96priority] <span class="title"><em>
- <a class="link" href="http://portal.acm.org/citation.cfm?id=313883">
+ . </span></span></p></div><div class="biblioentry" title="Worst-case efficient priority queues"><a name="biblio.brodal96priority"></a><p>[biblio.brodal96priority] <span class="title"><i>
+ <a class="link" href="http://portal.acm.org/citation.cfm?id=313883" target="_top">
Worst-case efficient priority queues
</a>
- </em>. </span><span class="author"><span class="firstname">
+ </i>. </span><span class="author"><span class="firstname">
Gerth
</span> <span class="surname">
Stolting Brodal
- </span>. </span></p></div><div class="biblioentry" title="Efficient C++ Programming Techniques"><a id="biblio.bulkamayheweff"/><p>[biblio.bulkamayheweff] <span class="title"><em>
+ </span>. </span></p></div><div class="biblioentry" title="Efficient C++ Programming Techniques"><a name="biblio.bulkamayheweff"></a><p>[biblio.bulkamayheweff] <span class="title"><i>
Efficient C++ Programming Techniques
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1997
. </span><span class="authorgroup"><span class="firstname">
D.
Mayhew
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="Introduction to Algorithms, 2nd edition"><a id="biblio.clrs2001"/><p>[biblio.clrs2001] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Introduction to Algorithms, 2nd edition"><a name="biblio.clrs2001"></a><p>[biblio.clrs2001] <span class="title"><i>
Introduction to Algorithms, 2nd edition
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2001
. </span><span class="authorgroup"><span class="firstname">
T. H.
Stein
</span>. </span><span class="publisher"><span class="publishername">
MIT Press
- . </span></span></p></div><div class="biblioentry" title="Balls and bins: A study in negative dependence"><a id="biblio.dubhashi98neg"/><p>[biblio.dubhashi98neg] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Balls and bins: A study in negative dependence"><a name="biblio.dubhashi98neg"></a><p>[biblio.dubhashi98neg] <span class="title"><i>
Balls and bins: A study in negative dependence
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1998
. </span><span class="authorgroup"><span class="firstname">
D.
Ranjan
</span>. </span><span class="publisher"><span class="publishername">
Random Structures and Algorithms 13
- . </span></span></p></div><div class="biblioentry" title="Extendible hashing - a fast access method for dynamic files"><a id="biblio.fagin79extendible"/><p>[biblio.fagin79extendible] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Extendible hashing - a fast access method for dynamic files"><a name="biblio.fagin79extendible"></a><p>[biblio.fagin79extendible] <span class="title"><i>
Extendible hashing - a fast access method for dynamic files
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1979
. </span><span class="authorgroup"><span class="firstname">
R.
Strong
</span>. </span><span class="publisher"><span class="publishername">
ACM Trans. Database Syst. 4
- . </span></span></p></div><div class="biblioentry" title="Ptset: Sets of integers implemented as Patricia trees"><a id="biblio.filliatre2000ptset"/><p>[biblio.filliatre2000ptset] <span class="title"><em>
- <a class="link" href="http://cristal.inria.fr/~frisch/icfp06_contest/advtr/applyOmatic/ptset.ml">
+ . </span></span></p></div><div class="biblioentry" title="Ptset: Sets of integers implemented as Patricia trees"><a name="biblio.filliatre2000ptset"></a><p>[biblio.filliatre2000ptset] <span class="title"><i>
+ <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">
+ </i>. </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" title="The pairing heap: a new form of self-adjusting heap"><a id="biblio.fredman86pairing"/><p>[biblio.fredman86pairing] <span class="title"><em>
- <a class="link" href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf">
+ </span>. </span></p></div><div class="biblioentry" title="The pairing heap: a new form of self-adjusting heap"><a name="biblio.fredman86pairing"></a><p>[biblio.fredman86pairing] <span class="title"><i>
+ <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">
+ </i>. </span><span class="date">
1986
. </span><span class="authorgroup"><span class="firstname">
M. L.
R. E.
</span> <span class="surname">
Tarjan
- </span>. </span></p></div><div class="biblioentry" title="Design Patterns - Elements of Reusable Object-Oriented Software"><a id="biblio.gof"/><p>[biblio.gof] <span class="title"><em>
+ </span>. </span></p></div><div class="biblioentry" title="Design Patterns - Elements of Reusable Object-Oriented Software"><a name="biblio.gof"></a><p>[biblio.gof] <span class="title"><i>
Design Patterns - Elements of Reusable Object-Oriented Software
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1995
. </span><span class="authorgroup"><span class="firstname">
E.
Vlissides
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="Order-preserving key transformations"><a id="biblio.garg86order"/><p>[biblio.garg86order] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Order-preserving key transformations"><a name="biblio.garg86order"></a><p>[biblio.garg86order] <span class="title"><i>
Order-preserving key transformations
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1986
. </span><span class="authorgroup"><span class="firstname">
A. K.
Gotlieb
</span>. </span><span class="publisher"><span class="publishername">
Trans. Database Syst. 11
- . </span></span></p></div><div class="biblioentry" title="Making a real hash of things"><a id="biblio.hyslop02making"/><p>[biblio.hyslop02making] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Making a real hash of things"><a name="biblio.hyslop02making"></a><p>[biblio.hyslop02making] <span class="title"><i>
Making a real hash of things
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
May 2002
. </span><span class="authorgroup"><span class="firstname">
J.
Sutter
</span>. </span><span class="publisher"><span class="publishername">
C++ Report
- . </span></span></p></div><div class="biblioentry" title="The C++ Standard Library - A Tutorial and Reference"><a id="biblio.jossutis01stl"/><p>[biblio.jossutis01stl] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="The C++ Standard Library - A Tutorial and Reference"><a name="biblio.jossutis01stl"></a><p>[biblio.jossutis01stl] <span class="title"><i>
The C++ Standard Library - A Tutorial and Reference
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2001
. </span><span class="author"><span class="firstname">
N. M.
Jossutis
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="New Heap Data Structures"><a id="biblio.kt99fat_heaps"/><p>[biblio.kt99fat_heaps] <span class="title"><em>
- <a class="link" href="http://www.cs.princeton.edu/research/techreps/TR-597-99">
+ . </span></span></p></div><div class="biblioentry" title="New Heap Data Structures"><a name="biblio.kt99fat_heaps"></a><p>[biblio.kt99fat_heaps] <span class="title"><i>
+ <a class="link" href="http://www.cs.princeton.edu/research/techreps/TR-597-99" target="_top">
New Heap Data Structures
</a>
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1999
. </span><span class="authorgroup"><span class="firstname">
Haim
Robert E.
</span> <span class="surname">
Tarjan
- </span>. </span></p></div><div class="biblioentry" title="Are Set Iterators Mutable or Immutable?"><a id="biblio.kleft00sets"/><p>[biblio.kleft00sets] <span class="title"><em>
+ </span>. </span></p></div><div class="biblioentry" title="Are Set Iterators Mutable or Immutable?"><a name="biblio.kleft00sets"></a><p>[biblio.kleft00sets] <span class="title"><i>
Are Set Iterators Mutable or Immutable?
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
October 2000
. </span><span class="authorgroup"><span class="firstname">
Angelika
Kleft
</span>. </span><span class="publisher"><span class="publishername">
C/C++ Users Jornal
- . </span></span></p></div><div class="biblioentry" title="The Art of Computer Programming - Sorting and Searching"><a id="biblio.knuth98sorting"/><p>[biblio.knuth98sorting] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="The Art of Computer Programming - Sorting and Searching"><a name="biblio.knuth98sorting"></a><p>[biblio.knuth98sorting] <span class="title"><i>
The Art of Computer Programming - Sorting and Searching
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1998
. </span><span class="author"><span class="firstname">
D. E.
Knuth
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="Data abstraction and hierarchy"><a id="biblio.liskov98data"/><p>[biblio.liskov98data] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Data abstraction and hierarchy"><a name="biblio.liskov98data"></a><p>[biblio.liskov98data] <span class="title"><i>
Data abstraction and hierarchy
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
May 1998
. </span><span class="author"><span class="firstname">
B.
Liskov
</span>. </span><span class="publisher"><span class="publishername">
SIGPLAN Notices 23
- . </span></span></p></div><div class="biblioentry" title="Linear hashing: A new tool for file and table addressing"><a id="biblio.litwin80lh"/><p>[biblio.litwin80lh] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Linear hashing: A new tool for file and table addressing"><a name="biblio.litwin80lh"></a><p>[biblio.litwin80lh] <span class="title"><i>
Linear hashing: A new tool for file and table addressing
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
June 1980
. </span><span class="author"><span class="firstname">
W.
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" title="Deamortization - Part 2: Binomial Heaps"><a id="biblio.maverik_lowerbounds"/><p>[biblio.maverik_lowerbounds] <span class="title"><em>
- <a class="link" href="http://magic.aladdin.cs.cmu.edu/2005/08/01/deamortization-part-2-binomial-heaps">
+ . </span></span></p></div><div class="biblioentry" title="Deamortization - Part 2: Binomial Heaps"><a name="biblio.maverik_lowerbounds"></a><p>[biblio.maverik_lowerbounds] <span class="title"><i>
+ <a class="link" href="http://magic.aladdin.cs.cmu.edu/2005/08/01/deamortization-part-2-binomial-heaps" target="_top">
Deamortization - Part 2: Binomial Heaps
</a>
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2005
. </span><span class="author"><span class="firstname">
Maverik
</span> <span class="surname">
Woo
- </span>. </span></p></div><div class="biblioentry" title="More Effective C++: 35 New Ways to Improve Your Programs and Designs"><a id="biblio.meyers96more"/><p>[biblio.meyers96more] <span class="title"><em>
+ </span>. </span></p></div><div class="biblioentry" title="More Effective C++: 35 New Ways to Improve Your Programs and Designs"><a name="biblio.meyers96more"></a><p>[biblio.meyers96more] <span class="title"><i>
More Effective C++: 35 New Ways to Improve Your Programs and Designs
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1996
. </span><span class="author"><span class="firstname">
Scott
Meyers
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="How Non-Member Functions Improve Encapsulation"><a id="biblio.meyers00nonmember"/><p>[biblio.meyers00nonmember] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="How Non-Member Functions Improve Encapsulation"><a name="biblio.meyers00nonmember"></a><p>[biblio.meyers00nonmember] <span class="title"><i>
How Non-Member Functions Improve Encapsulation
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2000
. </span><span class="author"><span class="firstname">
Scott
Meyers
</span>. </span><span class="publisher"><span class="publishername">
C/C++ Users Journal
- . </span></span></p></div><div class="biblioentry" title="Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library"><a id="biblio.meyers01stl"/><p>[biblio.meyers01stl] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library"><a name="biblio.meyers01stl"></a><p>[biblio.meyers01stl] <span class="title"><i>
Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2001
. </span><span class="author"><span class="firstname">
Scott
Meyers
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="Class Template, Member Template - or Both?"><a id="biblio.meyers02both"/><p>[biblio.meyers02both] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Class Template, Member Template - or Both?"><a name="biblio.meyers02both"></a><p>[biblio.meyers02both] <span class="title"><i>
Class Template, Member Template - or Both?
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2003
. </span><span class="author"><span class="firstname">
Scott
Meyers
</span>. </span><span class="publisher"><span class="publishername">
C/C++ Users Journal
- . </span></span></p></div><div class="biblioentry" title="Randomized Algorithms"><a id="biblio.motwani95random"/><p>[biblio.motwani95random] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Randomized Algorithms"><a name="biblio.motwani95random"></a><p>[biblio.motwani95random] <span class="title"><i>
Randomized Algorithms
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2003
. </span><span class="authorgroup"><span class="firstname">
R.
Raghavan
</span>. </span><span class="publisher"><span class="publishername">
Cambridge University Press
- . </span></span></p></div><div class="biblioentry" title="COM: Component Model Object Technologies"><a id="biblio.mscom"/><p>[biblio.mscom] <span class="title"><em>
- <a class="link" href="http://www.microsoft.com/com">
+ . </span></span></p></div><div class="biblioentry" title="COM: Component Model Object Technologies"><a name="biblio.mscom"></a><p>[biblio.mscom] <span class="title"><i>
+ <a class="link" href="http://www.microsoft.com/com" target="_top">
COM: Component Model Object Technologies
</a>
- </em>. </span><span class="publisher"><span class="publishername">
+ </i>. </span><span class="publisher"><span class="publishername">
Microsoft
- . </span></span></p></div><div class="biblioentry" title="Rationale for Adding Hash Tables to the C++ Standard Template Library"><a id="biblio.musser95rationale"/><p>[biblio.musser95rationale] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Rationale for Adding Hash Tables to the C++ Standard Template Library"><a name="biblio.musser95rationale"></a><p>[biblio.musser95rationale] <span class="title"><i>
Rationale for Adding Hash Tables to the C++ Standard Template Library
- </em>. </span><span class="date">
+ </i>. </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" title="STL Tutorial and Reference Guide"><a id="biblio.musser96stltutorial"/><p>[biblio.musser96stltutorial] <span class="title"><em>
+ </span>. </span></p></div><div class="biblioentry" title="STL Tutorial and Reference Guide"><a name="biblio.musser96stltutorial"></a><p>[biblio.musser96stltutorial] <span class="title"><i>
STL Tutorial and Reference Guide
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1996
. </span><span class="authorgroup"><span class="firstname">
David R.
Saini
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="Priority Queues and the STL"><a id="biblio.nelson96stlpq"/><p>[biblio.nelson96stlpq] <span class="title"><em>
- <a class="link" href="http://www.dogma.net/markn/articles/pq_stl/priority.htm">Priority Queues and the STL
+ . </span></span></p></div><div class="biblioentry" title="Priority Queues and the STL"><a name="biblio.nelson96stlpq"></a><p>[biblio.nelson96stlpq] <span class="title"><i>
+ <a class="link" href="http://www.dogma.net/markn/articles/pq_stl/priority.htm" target="_top">Priority Queues and the STL
</a>
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
January 1996
. </span><span class="author"><span class="firstname">
Mark
Nelson
</span>. </span><span class="publisher"><span class="publishername">
Dr. Dobbs Journal
- . </span></span></p></div><div class="biblioentry" title="Fast mergeable integer maps"><a id="biblio.okasaki98mereable"/><p>[biblio.okasaki98mereable] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Fast mergeable integer maps"><a name="biblio.okasaki98mereable"></a><p>[biblio.okasaki98mereable] <span class="title"><i>
Fast mergeable integer maps
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
September 1998
. </span><span class="authorgroup"><span class="firstname">
C.
Gill
</span>. </span><span class="publisher"><span class="publishername">
In Workshop on ML
- . </span></span></p></div><div class="biblioentry" title="Standard Template Library Programmer's Guide"><a id="biblio.sgi_stl"/><p>[biblio.sgi_stl] <span class="title"><em>
- <a class="link" href="http://www.sgi.com/tech/stl">
+ . </span></span></p></div><div class="biblioentry" title="Standard Template Library Programmer's Guide"><a name="biblio.sgi_stl"></a><p>[biblio.sgi_stl] <span class="title"><i>
+ <a class="link" href="http://www.sgi.com/tech/stl" target="_top">
Standard Template Library Programmer's Guide
</a>
- </em>. </span><span class="author"><span class="firstname">
+ </i>. </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" title="select"><a id="biblio.select_man"/><p>[biblio.select_man] <span class="title"><em>
- <a class="link" href="http://www.scit.wlv.ac.uk/cgi-bin/mansec?3C+select">
+ . </span></span></p></div><div class="biblioentry" title="select"><a name="biblio.select_man"></a><p>[biblio.select_man] <span class="title"><i>
+ <a class="link" href="http://www.scit.wlv.ac.uk/cgi-bin/mansec?3C+select" target="_top">
select
</a>
- </em>. </span></p></div><div class="biblioentry" title="Amortized Efficiency of List Update Problems"><a id="biblio.sleator84amortized"/><p>[biblio.sleator84amortized] <span class="title"><em>
+ </i>. </span></p></div><div class="biblioentry" title="Amortized Efficiency of List Update Problems"><a name="biblio.sleator84amortized"></a><p>[biblio.sleator84amortized] <span class="title"><i>
Amortized Efficiency of List Update Problems
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1984
. </span><span class="authorgroup"><span class="firstname">
D. D.
Tarjan
</span>. </span><span class="publisher"><span class="publishername">
ACM Symposium on Theory of Computing
- . </span></span></p></div><div class="biblioentry" title="Self-Adjusting Binary Search Trees"><a id="biblio.sleator85self"/><p>[biblio.sleator85self] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="Self-Adjusting Binary Search Trees"><a name="biblio.sleator85self"></a><p>[biblio.sleator85self] <span class="title"><i>
Self-Adjusting Binary Search Trees
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1985
. </span><span class="authorgroup"><span class="firstname">
D. D.
Tarjan
</span>. </span><span class="publisher"><span class="publishername">
ACM Symposium on Theory of Computing
- . </span></span></p></div><div class="biblioentry" title="The Standard Template Library"><a id="biblio.stepanov94standard"/><p>[biblio.stepanov94standard] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="The Standard Template Library"><a name="biblio.stepanov94standard"></a><p>[biblio.stepanov94standard] <span class="title"><i>
The Standard Template Library
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1984
. </span><span class="authorgroup"><span class="firstname">
A. A.
M.
</span> <span class="surname">
Lee
- </span>. </span></p></div><div class="biblioentry" title="The C++ Programming Langugage"><a id="biblio.stroustrup97cpp"/><p>[biblio.stroustrup97cpp] <span class="title"><em>
+ </span>. </span></p></div><div class="biblioentry" title="The C++ Programming Langugage"><a name="biblio.stroustrup97cpp"></a><p>[biblio.stroustrup97cpp] <span class="title"><i>
The C++ Programming Langugage
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1997
. </span><span class="author"><span class="firstname">
Bjarne
Stroustrup
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="C++ Templates: The Complete Guide"><a id="biblio.vandevoorde2002cpptemplates"/><p>[biblio.vandevoorde2002cpptemplates] <span class="title"><em>
+ . </span></span></p></div><div class="biblioentry" title="C++ Templates: The Complete Guide"><a name="biblio.vandevoorde2002cpptemplates"></a><p>[biblio.vandevoorde2002cpptemplates] <span class="title"><i>
C++ Templates: The Complete Guide
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
2002
. </span><span class="authorgroup"><span class="firstname">
D.
Josuttis
</span>. </span><span class="publisher"><span class="publishername">
Addison-Wesley Publishing Company
- . </span></span></p></div><div class="biblioentry" title="Thirty Years Among the Dead"><a id="biblio.wickland96thirty"/><p>[biblio.wickland96thirty] <span class="title"><em>
- <a class="link" href="http://myweb.wvnet.edu/~gsa00121/books/amongdead30.zip">
+ . </span></span></p></div><div class="biblioentry" title="Thirty Years Among the Dead"><a name="biblio.wickland96thirty"></a><p>[biblio.wickland96thirty] <span class="title"><i>
+ <a class="link" href="http://myweb.wvnet.edu/~gsa00121/books/amongdead30.zip" target="_top">
Thirty Years Among the Dead
</a>
- </em>. </span><span class="date">
+ </i>. </span><span class="date">
1996
. </span><span class="author"><span class="firstname">
C. A.
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 align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><td align="center"><a accesskey="u" href="extensions.html">Up</a></td><td align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr><tr><td align="left" valign="top">Implementation </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Using</td></tr></table></div></body></html>
+ . </span></span></p></div></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt03ch21s02.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="extensions.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Implementation </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Using</td></tr></table></div></body></html>
projects / gcc.git / blobdiff