| 1 |
424 |
jeremybenn |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
| 2 |
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
| 3 |
|
|
|
| 4 |
|
|
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
| 5 |
|
|
<head>
|
| 6 |
|
|
<meta name="generator" content=
|
| 7 |
|
|
"HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
|
| 8 |
|
|
|
| 9 |
|
|
<title>Priority-Queues</title>
|
| 10 |
|
|
<meta http-equiv="Content-Type" content=
|
| 11 |
|
|
"text/html; charset=us-ascii" />
|
| 12 |
|
|
</head>
|
| 13 |
|
|
|
| 14 |
|
|
<body>
|
| 15 |
|
|
<div id="page">
|
| 16 |
|
|
<h1>Priority-Queue Design</h1>
|
| 17 |
|
|
|
| 18 |
|
|
<h2><a name="overview" id="overview">Overview</a></h2>
|
| 19 |
|
|
|
| 20 |
|
|
<p>The priority-queue container has the following
|
| 21 |
|
|
declaration:</p>
|
| 22 |
|
|
<pre>
|
| 23 |
|
|
<b>template</b><
|
| 24 |
|
|
<b>typename</b> Value_Type,
|
| 25 |
|
|
<b>typename</b> Cmp_Fn = std::less<Value_Type>,
|
| 26 |
|
|
<b>typename</b> Tag = <a href="pairing_heap_tag.html">pairing_heap_tag</a>,
|
| 27 |
|
|
<b>typename</b> Allocator = std::allocator<<b>char</b>> >
|
| 28 |
|
|
<b>class</b> <a href="priority_queue.html">priority_queue</a>;
|
| 29 |
|
|
</pre>
|
| 30 |
|
|
|
| 31 |
|
|
<p>The parameters have the following meaning:</p>
|
| 32 |
|
|
|
| 33 |
|
|
<ol>
|
| 34 |
|
|
<li><tt>Value_Type</tt> is the value type.</li>
|
| 35 |
|
|
|
| 36 |
|
|
<li><tt>Cmp_Fn</tt> is a value comparison functor</li>
|
| 37 |
|
|
|
| 38 |
|
|
<li><tt>Tag</tt> specifies which underlying data structure
|
| 39 |
|
|
to use.</li>
|
| 40 |
|
|
|
| 41 |
|
|
<li><tt>Allocator</tt> is an allocator
|
| 42 |
|
|
type.</li>
|
| 43 |
|
|
</ol>
|
| 44 |
|
|
|
| 45 |
|
|
<p>The <tt>Tag</tt> parameter specifies which underlying
|
| 46 |
|
|
data structure to use. Instantiating it by <a href=
|
| 47 |
|
|
"pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>,
|
| 48 |
|
|
<a href=
|
| 49 |
|
|
"binary_heap_tag.html"><tt>binary_heap_tag</tt></a>,
|
| 50 |
|
|
<a href=
|
| 51 |
|
|
"binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>,
|
| 52 |
|
|
<a href=
|
| 53 |
|
|
"rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>,
|
| 54 |
|
|
or <a href=
|
| 55 |
|
|
"thin_heap_tag.html"><tt>thin_heap_tag</tt></a>,
|
| 56 |
|
|
specifies, respectively, an underlying pairing heap [<a href=
|
| 57 |
|
|
"references.html#fredman86pairing">fredman86pairing</a>],
|
| 58 |
|
|
binary heap [<a href="references.html#clrs2001">clrs2001</a>],
|
| 59 |
|
|
binomial heap [<a href=
|
| 60 |
|
|
"references.html#clrs2001">clrs2001</a>], a binomial heap with
|
| 61 |
|
|
a redundant binary counter [<a href=
|
| 62 |
|
|
"references.html#maverik_lowerbounds">maverik_lowerbounds</a>],
|
| 63 |
|
|
or a thin heap [<a href=
|
| 64 |
|
|
"references.html#kt99fat_heaps">kt99fat_heas</a>]. These are
|
| 65 |
|
|
explained further in <a href="#pq_imp">Implementations</a>.</p>
|
| 66 |
|
|
|
| 67 |
|
|
<p>As mentioned in <a href=
|
| 68 |
|
|
"tutorial.html#pq">Tutorial::Priority Queues</a>,
|
| 69 |
|
|
<a href=
|
| 70 |
|
|
"priority_queue.html"><tt>__gnu_pbds::priority_queue</tt></a>
|
| 71 |
|
|
shares most of the same interface with <tt>std::priority_queue</tt>.
|
| 72 |
|
|
<i>E.g.</i> if <tt>q</tt> is a priority queue of type
|
| 73 |
|
|
<tt>Q</tt>, then <tt>q.top()</tt> will return the "largest"
|
| 74 |
|
|
value in the container (according to <tt><b>typename</b>
|
| 75 |
|
|
Q::cmp_fn</tt>). <a href=
|
| 76 |
|
|
"priority_queue.html"><tt>__gnu_pbds::priority_queue</tt></a>
|
| 77 |
|
|
has a larger (and very slightly different) interface than
|
| 78 |
|
|
<tt>std::priority_queue</tt>, however, since typically
|
| 79 |
|
|
<tt>push</tt> and <tt>pop</tt> are deemed insufficient for
|
| 80 |
|
|
manipulating priority-queues. </p>
|
| 81 |
|
|
|
| 82 |
|
|
<p>Different settings require different priority-queue
|
| 83 |
|
|
implementations which are described in <a href=
|
| 84 |
|
|
"#pq_imp">Implementations</a>; <a href="#pq_traits">Traits</a>
|
| 85 |
|
|
discusses ways to differentiate between the different traits of
|
| 86 |
|
|
different implementations.</p>
|
| 87 |
|
|
|
| 88 |
|
|
<h2><a name="pq_it" id="pq_it">Iterators</a></h2>
|
| 89 |
|
|
|
| 90 |
|
|
<p>There are many different underlying-data structures for
|
| 91 |
|
|
implementing priority queues. Unfortunately, most such
|
| 92 |
|
|
structures are oriented towards making <tt>push</tt> and
|
| 93 |
|
|
<tt>top</tt> efficient, and consequently don't allow efficient
|
| 94 |
|
|
access of other elements: for instance, they cannot support an efficient
|
| 95 |
|
|
<tt>find</tt> method. In the use case where it
|
| 96 |
|
|
is important to both access and "do something with" an
|
| 97 |
|
|
arbitrary value, one would be out of luck. For example, many graph algorithms require
|
| 98 |
|
|
modifying a value (typically increasing it in the sense of the
|
| 99 |
|
|
priority queue's comparison functor).</p>
|
| 100 |
|
|
|
| 101 |
|
|
<p>In order to access and manipulate an arbitrary value in a
|
| 102 |
|
|
priority queue, one needs to reference the internals of the
|
| 103 |
|
|
priority queue from some form of an associative container -
|
| 104 |
|
|
this is unavoidable. Of course, in order to maintain the
|
| 105 |
|
|
encapsulation of the priority queue, this needs to be done in a
|
| 106 |
|
|
way that minimizes exposure to implementation internals.</p>
|
| 107 |
|
|
|
| 108 |
|
|
<p>In <tt>pb_ds</tt> the priority queue's <tt>insert</tt>
|
| 109 |
|
|
method returns an iterator, which if valid can be used for subsequent <tt>modify</tt> and
|
| 110 |
|
|
<tt>erase</tt> operations. This both preserves the priority
|
| 111 |
|
|
queue's encapsulation, and allows accessing arbitrary values (since the
|
| 112 |
|
|
returned iterators from the <tt>push</tt> operation can be
|
| 113 |
|
|
stored in some form of associative container).</p>
|
| 114 |
|
|
|
| 115 |
|
|
<p>Priority queues' iterators present a problem regarding their
|
| 116 |
|
|
invalidation guarantees. One assumes that calling
|
| 117 |
|
|
<tt><b>operator</b>++</tt> on an iterator will associate it
|
| 118 |
|
|
with the "next" value. Priority-queues are
|
| 119 |
|
|
self-organizing: each operation changes what the "next" value
|
| 120 |
|
|
means. Consequently, it does not make sense that <tt>push</tt>
|
| 121 |
|
|
will return an iterator that can be incremented - this can have
|
| 122 |
|
|
no possible use. Also, as in the case of hash-based containers,
|
| 123 |
|
|
it is awkward to define if a subsequent <tt>push</tt> operation
|
| 124 |
|
|
invalidates a prior returned iterator: it invalidates it in the
|
| 125 |
|
|
sense that its "next" value is not related to what it
|
| 126 |
|
|
previously considered to be its "next" value. However, it might not
|
| 127 |
|
|
invalidate it, in the sense that it can be
|
| 128 |
|
|
de-referenced and used for <tt>modify</tt> and <tt>erase</tt>
|
| 129 |
|
|
operations.</p>
|
| 130 |
|
|
|
| 131 |
|
|
<p>Similarly to the case of the other unordered associative
|
| 132 |
|
|
containers, <tt>pb_ds</tt> uses a distinction between
|
| 133 |
|
|
point-type and range type iterators. A priority queue's <tt>iterator</tt> can always be
|
| 134 |
|
|
converted to a <tt>point_iterator</tt>, and a
|
| 135 |
|
|
<tt>const_iterator</tt> can always be converted to a
|
| 136 |
|
|
<tt>const_point_iterator</tt>.</p>
|
| 137 |
|
|
|
| 138 |
|
|
<p>The following snippet demonstrates manipulating an arbitrary
|
| 139 |
|
|
value:</p>
|
| 140 |
|
|
<pre>
|
| 141 |
|
|
<i>// A priority queue of integers.</i>
|
| 142 |
|
|
<a href=
|
| 143 |
|
|
"priority_queue.html">priority_queue</a><<b>int</b>> p;
|
| 144 |
|
|
|
| 145 |
|
|
<i>// Insert some values into the priority queue.</i>
|
| 146 |
|
|
<a href=
|
| 147 |
|
|
"priority_queue.html">priority_queue</a><<b>int</b>>::point_iterator it = p.push(0);
|
| 148 |
|
|
|
| 149 |
|
|
p.push(1);
|
| 150 |
|
|
p.push(2);
|
| 151 |
|
|
|
| 152 |
|
|
<i>// Now modify a value.</i>
|
| 153 |
|
|
p.modify(it, 3);
|
| 154 |
|
|
|
| 155 |
|
|
assert(p.top() == 3);
|
| 156 |
|
|
</pre>
|
| 157 |
|
|
|
| 158 |
|
|
<p>(<a href="pq_examples.html#xref">Priority Queue
|
| 159 |
|
|
Examples::Cross-Referencing</a> shows a more detailed
|
| 160 |
|
|
example.)</p>
|
| 161 |
|
|
|
| 162 |
|
|
<p>It should be noted that an alternative design could embed an
|
| 163 |
|
|
associative container in a priority queue. Could, but most probably should not. To begin with, it should be noted that one
|
| 164 |
|
|
could always encapsulate a priority queue and an associative
|
| 165 |
|
|
container mapping values to priority queue iterators with no
|
| 166 |
|
|
performance loss. One cannot, however, "un-encapsulate" a
|
| 167 |
|
|
priority queue embedding an associative container, which might
|
| 168 |
|
|
lead to performance loss. Assume, that one needs to
|
| 169 |
|
|
associate each value with some data unrelated to priority
|
| 170 |
|
|
queues. Then using <tt>pb_ds</tt>'s design, one could use an
|
| 171 |
|
|
associative container mapping each value to a pair consisting
|
| 172 |
|
|
of this data and a priority queue's iterator. Using the
|
| 173 |
|
|
embedded method would need to use two associative
|
| 174 |
|
|
containers. Similar problems might arise in cases where a value
|
| 175 |
|
|
can reside simultaneously in many priority queues.</p>
|
| 176 |
|
|
|
| 177 |
|
|
<h2><a name="pq_imp" id="pq_imp">Implementations</a></h2>
|
| 178 |
|
|
|
| 179 |
|
|
<p>There are three main implementations of priority queues: the
|
| 180 |
|
|
first employs a binary heap, typically one which uses a
|
| 181 |
|
|
sequence; the second uses a tree (or forest of trees), which is
|
| 182 |
|
|
typically less structured than an associative container's tree;
|
| 183 |
|
|
the third simply uses an associative container. These are
|
| 184 |
|
|
shown, respectively, in Figures <a href=
|
| 185 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 186 |
|
|
Data-Structures</a> A1 and A2, Figure <a href=
|
| 187 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 188 |
|
|
Data-Structures</a> B, and Figures <a href=
|
| 189 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 190 |
|
|
Data-Structures</a> C.</p>
|
| 191 |
|
|
|
| 192 |
|
|
<h6 class="c1"><a name="pq_different_underlying_dss" id=
|
| 193 |
|
|
"pq_different_underlying_dss"><img src=
|
| 194 |
|
|
"pq_different_underlying_dss.png" alt="no image" /></a></h6>
|
| 195 |
|
|
|
| 196 |
|
|
<h6 class="c1">Underlying Priority-Queue Data-Structures.</h6>
|
| 197 |
|
|
|
| 198 |
|
|
<p>Roughly speaking, any value that is both pushed and popped
|
| 199 |
|
|
from a priority queue must incur a logarithmic expense (in the
|
| 200 |
|
|
amortized sense). Any priority queue implementation that would
|
| 201 |
|
|
avoid this, would violate known bounds on comparison-based
|
| 202 |
|
|
sorting (see, <i>e.g.</i>, [<a href=
|
| 203 |
|
|
"references.html#clrs2001">clrs2001</a>] and <a href=
|
| 204 |
|
|
"references.html#brodal96priority">brodal96priority</a>]).</p>
|
| 205 |
|
|
|
| 206 |
|
|
<p>Most implementations do
|
| 207 |
|
|
not differ in the asymptotic amortized complexity of
|
| 208 |
|
|
<tt>push</tt> and <tt>pop</tt> operations, but they differ in
|
| 209 |
|
|
the constants involved, in the complexity of other operations
|
| 210 |
|
|
(<i>e.g.</i>, <tt>modify</tt>), and in the worst-case
|
| 211 |
|
|
complexity of single operations. In general, the more
|
| 212 |
|
|
"structured" an implementation (<i>i.e.</i>, the more internal
|
| 213 |
|
|
invariants it possesses) - the higher its amortized complexity
|
| 214 |
|
|
of <tt>push</tt> and <tt>pop</tt> operations.</p>
|
| 215 |
|
|
|
| 216 |
|
|
<p><tt>pb_ds</tt> implements different algorithms using a
|
| 217 |
|
|
single class: <a href="priority_queue.html">priority_queue</a>.
|
| 218 |
|
|
Instantiating the <tt>Tag</tt> template parameter, "selects"
|
| 219 |
|
|
the implementation:</p>
|
| 220 |
|
|
|
| 221 |
|
|
<ol>
|
| 222 |
|
|
<li>Instantiating <tt>Tag = <a href=
|
| 223 |
|
|
"binary_heap_tag.html">binary_heap_tag</a></tt> creates
|
| 224 |
|
|
a binary heap of the form in Figures <a href=
|
| 225 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 226 |
|
|
Data-Structures</a> A1 or A2. The former is internally
|
| 227 |
|
|
selected by <a href="priority_queue.html">priority_queue</a>
|
| 228 |
|
|
if <tt>Value_Type</tt> is instantiated by a primitive type
|
| 229 |
|
|
(<i>e.g.</i>, an <tt><b>int</b></tt>); the latter is
|
| 230 |
|
|
internally selected for all other types (<i>e.g.</i>,
|
| 231 |
|
|
<tt>std::string</tt>). This implementations is relatively
|
| 232 |
|
|
unstructured, and so has good <tt>push</tt> and <tt>pop</tt>
|
| 233 |
|
|
performance; it is the "best-in-kind" for primitive
|
| 234 |
|
|
types, <i>e.g.</i>, <tt><b>int</b></tt>s. Conversely, it has
|
| 235 |
|
|
high worst-case performance, and can support only linear-time
|
| 236 |
|
|
<tt>modify</tt> and <tt>erase</tt> operations; this is
|
| 237 |
|
|
explained further in <a href="#pq_traits">Traits</a>.</li>
|
| 238 |
|
|
|
| 239 |
|
|
<li>Instantiating <tt>Tag = <a href=
|
| 240 |
|
|
"pairing_heap_tag.html">pairing_heap_tag</a></tt>
|
| 241 |
|
|
creates a pairing heap of the form in Figure <a href=
|
| 242 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 243 |
|
|
Data-Structures</a> B. This implementations too is relatively
|
| 244 |
|
|
unstructured, and so has good <tt>push</tt> and <tt>pop</tt>
|
| 245 |
|
|
performance; it is the "best-in-kind" for non-primitive
|
| 246 |
|
|
types, <i>e.g.</i>, <tt>std:string</tt>s. It also has very
|
| 247 |
|
|
good worst-case <tt>push</tt> and <tt>join</tt> performance
|
| 248 |
|
|
(<i>O(1)</i>), but has high worst-case <tt>pop</tt>
|
| 249 |
|
|
complexity.</li>
|
| 250 |
|
|
|
| 251 |
|
|
<li>Instantiating <tt>Tag = <a href=
|
| 252 |
|
|
"binomial_heap_tag.html">binomial_heap_tag</a></tt>
|
| 253 |
|
|
creates a binomial heap of the form in Figure <a href=
|
| 254 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 255 |
|
|
Data-Structures</a> B. This implementations is more
|
| 256 |
|
|
structured than a pairing heap, and so has worse
|
| 257 |
|
|
<tt>push</tt> and <tt>pop</tt> performance. Conversely, it
|
| 258 |
|
|
has sub-linear worst-case bounds for <tt>pop</tt>,
|
| 259 |
|
|
<i>e.g.</i>, and so it might be preferred in cases where
|
| 260 |
|
|
responsiveness is important.</li>
|
| 261 |
|
|
|
| 262 |
|
|
<li>Instantiating <tt>Tag = <a href=
|
| 263 |
|
|
"rc_binomial_heap_tag.html">rc_binomial_heap_tag</a></tt>
|
| 264 |
|
|
creates a binomial heap of the form in Figure <a href=
|
| 265 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 266 |
|
|
Data-Structures</a> B, accompanied by a redundant counter
|
| 267 |
|
|
which governs the trees. This implementations is therefore
|
| 268 |
|
|
more structured than a binomial heap, and so has worse
|
| 269 |
|
|
<tt>push</tt> and <tt>pop</tt> performance. Conversely, it
|
| 270 |
|
|
guarantees <i>O(1)</i> <tt>push</tt> complexity, and so it
|
| 271 |
|
|
might be preferred in cases where the responsiveness of a
|
| 272 |
|
|
binomial heap is insufficient.</li>
|
| 273 |
|
|
|
| 274 |
|
|
<li>Instantiating <tt>Tag = <a href=
|
| 275 |
|
|
"thin_heap_tag.html">thin_heap_tag</a></tt> creates a
|
| 276 |
|
|
thin heap of the form in Figure <a href=
|
| 277 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 278 |
|
|
Data-Structures</a> B. This implementations too is more
|
| 279 |
|
|
structured than a pairing heap, and so has worse
|
| 280 |
|
|
<tt>push</tt> and <tt>pop</tt> performance. Conversely, it
|
| 281 |
|
|
has better worst-case and identical amortized complexities
|
| 282 |
|
|
than a Fibonacci heap, and so might be more appropriate for
|
| 283 |
|
|
some graph algorithms.</li>
|
| 284 |
|
|
</ol>
|
| 285 |
|
|
|
| 286 |
|
|
<p><a href="pq_performance_tests.html">Priority-Queue
|
| 287 |
|
|
Performance Tests</a> shows some results for the above, and
|
| 288 |
|
|
discusses these points further.</p>
|
| 289 |
|
|
|
| 290 |
|
|
<p>Of course, one can use any order-preserving associative
|
| 291 |
|
|
container as a priority queue, as in Figure <a href=
|
| 292 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 293 |
|
|
Data-Structures</a> C, possibly by creating an adapter class
|
| 294 |
|
|
over the associative container (much as
|
| 295 |
|
|
<tt>std::priority_queue</tt> can adapt <tt>std::vector</tt>).
|
| 296 |
|
|
This has the advantage that no cross-referencing is necessary
|
| 297 |
|
|
at all; the priority queue itself is an associative container.
|
| 298 |
|
|
Most associative containers are too structured to compete with
|
| 299 |
|
|
priority queues in terms of <tt>push</tt> and <tt>pop</tt>
|
| 300 |
|
|
performance.</p>
|
| 301 |
|
|
|
| 302 |
|
|
<h2><a name="pq_traits" id="pq_traits">Traits</a></h2>
|
| 303 |
|
|
|
| 304 |
|
|
<p>It would be nice if all priority queues could
|
| 305 |
|
|
share exactly the same behavior regardless of implementation. Sadly, this is not possible. Just one for instance is in join operations: joining
|
| 306 |
|
|
two binary heaps might throw an exception (not corrupt
|
| 307 |
|
|
any of the heaps on which it operates), but joining two pairing
|
| 308 |
|
|
heaps is exception free.</p>
|
| 309 |
|
|
|
| 310 |
|
|
<p>Tags and traits are very useful for manipulating generic
|
| 311 |
|
|
types. <a href=
|
| 312 |
|
|
"priority_queue.html"><tt>__gnu_pbds::priority_queue</tt></a>
|
| 313 |
|
|
publicly defines <tt>container_category</tt> as one of the tags
|
| 314 |
|
|
discussed in <a href="#pq_imp">Implementations</a>. Given any
|
| 315 |
|
|
container <tt>Cntnr</tt>, the tag of the underlying
|
| 316 |
|
|
data structure can be found via <tt><b>typename</b>
|
| 317 |
|
|
Cntnr::container_category</tt>; this is one of the types shown in
|
| 318 |
|
|
Figure <a href="#pq_tag_cd">Data-structure tag class
|
| 319 |
|
|
hierarchy</a>.</p>
|
| 320 |
|
|
|
| 321 |
|
|
<h6 class="c1"><a name="pq_tag_cd" id=
|
| 322 |
|
|
"pq_tag_cd"><img src="priority_queue_tag_cd.png" alt=
|
| 323 |
|
|
"no image" /></a></h6>
|
| 324 |
|
|
|
| 325 |
|
|
<h6 class="c1">Data-structure tag class hierarchy.</h6>
|
| 326 |
|
|
|
| 327 |
|
|
<p>Additionally, a traits mechanism can be used to query a
|
| 328 |
|
|
container type for its attributes. Given any container
|
| 329 |
|
|
<tt>Cntnr</tt>, then <tt><a href=
|
| 330 |
|
|
"assoc_container_traits.html">__gnu_pbds::container_traits</a><Cntnr></tt>
|
| 331 |
|
|
is a traits class identifying the properties of the
|
| 332 |
|
|
container.</p>
|
| 333 |
|
|
|
| 334 |
|
|
<p>To find if a container might throw if two of its objects are
|
| 335 |
|
|
joined, one can use <a href=
|
| 336 |
|
|
"assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::split_join_can_throw</tt>,
|
| 337 |
|
|
for example.</p>
|
| 338 |
|
|
|
| 339 |
|
|
<p>Different priority-queue implementations have different invalidation guarantees. This is
|
| 340 |
|
|
especially important, since as explained in <a href=
|
| 341 |
|
|
"#pq_it">Iterators</a>, there is no way to access an arbitrary
|
| 342 |
|
|
value of priority queues except for iterators. Similarly to
|
| 343 |
|
|
associative containers, one can use
|
| 344 |
|
|
<a href=
|
| 345 |
|
|
"assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::invalidation_guarantee</tt>
|
| 346 |
|
|
to get the invalidation guarantee type of a priority queue.</p>
|
| 347 |
|
|
|
| 348 |
|
|
<p>It is easy to understand from Figure <a href=
|
| 349 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 350 |
|
|
Data-Structures</a>, what <a href=
|
| 351 |
|
|
"assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::invalidation_guarantee</tt>
|
| 352 |
|
|
will be for different implementations. All implementations of
|
| 353 |
|
|
type <a href="#pq_different_underlying_dss">Underlying
|
| 354 |
|
|
Priority-Queue Data-Structures</a> B have <a href=
|
| 355 |
|
|
"point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>:
|
| 356 |
|
|
the container can freely internally reorganize the nodes -
|
| 357 |
|
|
range-type iterators are invalidated, but point-type iterators
|
| 358 |
|
|
are always valid. Implementations of type <a href=
|
| 359 |
|
|
"#pq_different_underlying_dss">Underlying Priority-Queue
|
| 360 |
|
|
Data-Structures</a> A1 and A2 have <a href=
|
| 361 |
|
|
"basic_invalidation_guarantee.html"><tt>basic_invalidation_guarantee</tt></a>:
|
| 362 |
|
|
the container can freely internally reallocate the array - both
|
| 363 |
|
|
point-type and range-type iterators might be invalidated.</p>
|
| 364 |
|
|
|
| 365 |
|
|
<p>This has major implications, and constitutes a good reason to avoid
|
| 366 |
|
|
using binary heaps. A binary heap can perform <tt>modify</tt>
|
| 367 |
|
|
or <tt>erase</tt> efficiently <u>given a valid point-type
|
| 368 |
|
|
iterator</u>. However, inn order to supply it with a valid point-type
|
| 369 |
|
|
iterator, one needs to iterate (linearly) over all
|
| 370 |
|
|
values, then supply the relevant iterator (recall that a
|
| 371 |
|
|
range-type iterator can always be converted to a point-type
|
| 372 |
|
|
iterator). This means that if the number of <tt>modify</tt> or
|
| 373 |
|
|
<tt>erase</tt> operations is non-negligible (say
|
| 374 |
|
|
super-logarithmic in the total sequence of operations) - binary
|
| 375 |
|
|
heaps will perform badly.</p>
|
| 376 |
|
|
<pre>
|
| 377 |
|
|
|
| 378 |
|
|
</pre>
|
| 379 |
|
|
</div>
|
| 380 |
|
|
</body>
|
| 381 |
|
|
</html>
|
