1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Concepts & Interface</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../heap.html" title="Chapter 17. Boost.Heap"> 10<link rel="prev" href="../heap.html" title="Chapter 17. Boost.Heap"> 11<link rel="next" href="data_structures.html" title="Data Structures"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="../heap.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../heap.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="data_structures.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="heap.concepts"></a><a class="link" href="concepts.html" title="Concepts & Interface">Concepts & Interface</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="concepts.html#heap.concepts.basic">Basic Priority Queue Interface</a></span></dt> 32<dt><span class="section"><a href="concepts.html#heap.concepts.iterators">Priority Queue Iterators</a></span></dt> 33<dt><span class="section"><a href="concepts.html#heap.concepts.comparing">Comparing Priority Queues & 34 Equivalence</a></span></dt> 35<dt><span class="section"><a href="concepts.html#heap.concepts.merge">Merging Priority Queues</a></span></dt> 36<dt><span class="section"><a href="concepts.html#heap.concepts.mutability">Mutability</a></span></dt> 37<dt><span class="section"><a href="concepts.html#heap.concepts.stability">Stability</a></span></dt> 38</dl></div> 39<div class="section"> 40<div class="titlepage"><div><div><h3 class="title"> 41<a name="heap.concepts.basic"></a><a class="link" href="concepts.html#heap.concepts.basic" title="Basic Priority Queue Interface">Basic Priority Queue Interface</a> 42</h3></div></div></div> 43<p> 44 Priority queues are queues of objects, that are ordered by their priority. 45 They support the operations of adding nodes to the data structure, accessing 46 the top element (the element with the highest priority), and removing the 47 top element. 48 </p> 49<div class="note"><table border="0" summary="Note"> 50<tr> 51<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 52<th align="left">Note</th> 53</tr> 54<tr><td align="left" valign="top"><p> 55 <code class="literal">boost.heap</code> implements priority queues as max-heaps to 56 be consistent with the STL heap functions. This is in contrast to the typical 57 textbook design, which uses min-heaps. 58 </p></td></tr> 59</table></div> 60<h6> 61<a name="heap.concepts.basic.h0"></a> 62 <span class="phrase"><a name="heap.concepts.basic.synopsis"></a></span><a class="link" href="concepts.html#heap.concepts.basic.synopsis">Synopsis</a> 63 </h6> 64<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 65<span class="keyword">class</span> <span class="identifier">priority_queue</span> 66<span class="special">{</span> 67 <span class="comment">// types</span> 68 <span class="keyword">typedef</span> <span class="identifier">T</span> <span class="identifier">value_type</span><span class="special">;</span> 69 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">size_type</span><span class="special">;</span> 70 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">difference_type</span><span class="special">;</span> 71 72 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">allocator_type</span><span class="special">;</span> 73 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">value_compare</span><span class="special">;</span> 74 75 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">reference</span><span class="special">;</span> 76 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">const_reference</span><span class="special">;</span> 77 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">pointer</span><span class="special">;</span> 78 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">const_pointer</span><span class="special">;</span> 79 80 <span class="comment">// construct/copy/destruct</span> 81 <span class="keyword">explicit</span> <span class="identifier">priority_queue</span><span class="special">(</span><span class="identifier">value_compare</span> <span class="keyword">const</span> <span class="special">&</span> <span class="special">=</span> <span class="identifier">value_compare</span><span class="special">());</span> 82 <span class="identifier">priority_queue</span><span class="special">(</span><span class="identifier">priority_queue</span> <span class="keyword">const</span> <span class="special">&);</span> 83 <span class="identifier">priority_queue</span><span class="special">&</span> <span class="keyword">operator</span><span class="special">=(</span><span class="identifier">priority_queue</span> <span class="keyword">const</span> <span class="special">&);</span> 84 <span class="identifier">priority_queue</span><span class="special">(</span><span class="identifier">priority_queue</span> <span class="special">&&);</span> <span class="comment">// move semantics (C++11 only)</span> 85 <span class="identifier">priority_queue</span><span class="special">&</span> <span class="keyword">operator</span><span class="special">=(</span><span class="identifier">priority_queue</span> <span class="special">&&);</span> <span class="comment">// move semantics (C++11 only)</span> 86 87 <span class="comment">// public member functions</span> 88 <span class="emphasis"><em>unspecified</em></span> <span class="identifier">push</span><span class="special">(</span><span class="identifier">const_reference</span><span class="special">);</span> <span class="comment">// push new element to heap</span> 89 <span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span><span class="special">...</span> <span class="identifier">Args</span><span class="special">></span> <span class="keyword">void</span> <span class="identifier">emplace</span><span class="special">(</span><span class="identifier">Args</span> <span class="special">&&...);</span> <span class="comment">// push new element to heap, C++11 only</span> 90 <span class="identifier">const_reference</span> <span class="identifier">top</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> <span class="comment">// return top element</span> 91 <span class="keyword">void</span> <span class="identifier">pop</span><span class="special">();</span> <span class="comment">// remove top element</span> 92 <span class="keyword">void</span> <span class="identifier">clear</span><span class="special">();</span> <span class="comment">// clear heap</span> 93 <span class="identifier">size_type</span> <span class="identifier">size</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> <span class="comment">// number of elements</span> 94 <span class="keyword">bool</span> <span class="identifier">empty</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> <span class="comment">// priority queue is empty</span> 95 <span class="identifier">allocator_type</span> <span class="identifier">get_allocator</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> <span class="comment">// return allocator</span> 96 <span class="identifier">size_type</span> <span class="identifier">max_size</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> <span class="comment">// maximal possible size</span> 97 <span class="keyword">void</span> <span class="identifier">reserve</span><span class="special">(</span><span class="identifier">size_type</span><span class="special">);</span> <span class="comment">// reserve space, only available if (has_reserve == true)</span> 98 99 <span class="comment">// heap equivalence</span> 100 <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">HeapType</span><span class="special">></span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&)</span> <span class="keyword">const</span><span class="special">;</span> 101 <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">HeapType</span><span class="special">></span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">!=(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&)</span> <span class="keyword">const</span><span class="special">;</span> 102 103 <span class="comment">// heap comparison</span> 104 <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">HeapType</span><span class="special">></span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special"><(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&)</span> <span class="keyword">const</span><span class="special">;</span> 105 <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">HeapType</span><span class="special">></span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">>(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&)</span> <span class="keyword">const</span><span class="special">;</span> 106 <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">HeapType</span><span class="special">></span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">>=(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&)</span> <span class="keyword">const</span><span class="special">;</span> 107 <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">HeapType</span><span class="special">></span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special"><=(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&)</span> <span class="keyword">const</span><span class="special">;</span> 108 109 <span class="comment">// public data members</span> 110 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">bool</span> <span class="identifier">constant_time_size</span><span class="special">;</span> <span class="comment">// size() has constant complexity</span> 111 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">bool</span> <span class="identifier">has_ordered_iterators</span><span class="special">;</span> <span class="comment">// priority queue has <a class="link" href="concepts.html#heap.concepts.iterators" title="Priority Queue Iterators">ordered iterators</a></span> 112 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">bool</span> <span class="identifier">is_mergable</span><span class="special">;</span> <span class="comment">// priority queue is efficiently <a class="link" href="concepts.html#heap.concepts.merge" title="Merging Priority Queues">mergable</a></span> 113 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">bool</span> <span class="identifier">is_stable</span><span class="special">;</span> <span class="comment">// priority queue has a <a class="link" href="concepts.html#heap.concepts.stability" title="Stability">stable heap order</a></span> 114 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">bool</span> <span class="identifier">has_reserve</span><span class="special">;</span> <span class="comment">// priority queue has a reserve() member</span> 115<span class="special">};</span> 116</pre> 117<h6> 118<a name="heap.concepts.basic.h1"></a> 119 <span class="phrase"><a name="heap.concepts.basic.example"></a></span><a class="link" href="concepts.html#heap.concepts.basic.example">Example</a> 120 </h6> 121<p> 122</p> 123<pre class="programlisting"><span class="comment">// PriorityQueue is expected to be a max-heap of integer values</span> 124<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">></span> 125<span class="keyword">void</span> <span class="identifier">basic_interface</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 126<span class="special">{</span> 127 <span class="identifier">PriorityQueue</span> <span class="identifier">pq</span><span class="special">;</span> 128 129 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> 130 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 131 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> 132 133 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"Priority Queue: popped elements"</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 134 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 3</span> 135 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 136 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 2</span> 137 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 138 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 1</span> 139 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 140 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 141<span class="special">}</span> 142</pre> 143<p> 144 </p> 145</div> 146<div class="section"> 147<div class="titlepage"><div><div><h3 class="title"> 148<a name="heap.concepts.iterators"></a><a class="link" href="concepts.html#heap.concepts.iterators" title="Priority Queue Iterators">Priority Queue Iterators</a> 149</h3></div></div></div> 150<div class="toc"><dl class="toc"><dt><span class="section"><a href="concepts.html#heap.concepts.iterators.ordered_iterators">Ordered 151 Iterators</a></span></dt></dl></div> 152<h6> 153<a name="heap.concepts.iterators.h0"></a> 154 <span class="phrase"><a name="heap.concepts.iterators.synopsis"></a></span><a class="link" href="concepts.html#heap.concepts.iterators.synopsis">Synopsis</a> 155 </h6> 156<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">iteratable_heap_interface</span> 157<span class="special">{</span> 158<span class="keyword">public</span><span class="special">:</span> 159 <span class="comment">// types</span> 160 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">iterator</span><span class="special">;</span> 161 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">const_iterator</span><span class="special">;</span> 162 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">ordered_iterator</span><span class="special">;</span> 163 164 <span class="comment">// public member functions</span> 165 <span class="identifier">iterator</span> <span class="identifier">begin</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 166 <span class="identifier">iterator</span> <span class="identifier">end</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 167 <span class="identifier">ordered_iterator</span> <span class="identifier">ordered_begin</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 168 <span class="identifier">ordered_iterator</span> <span class="identifier">ordered_end</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 169<span class="special">};</span> 170</pre> 171<p> 172 Priority queues provide iterators, that can be used to traverse their elements. 173 All heap iterators are const_iterators, that means they cannot be used to 174 modify the values, because changing the value of a heap node may corrupt 175 the heap order. Details about modifying heap nodes are described in the section 176 about the <a class="link" href="concepts.html#heap.concepts.mutability" title="Mutability">mutability interface</a>. 177 </p> 178<p> 179 Iterators do not visit heap elements in any specific order. Unless otherwise 180 noted, all non-const heap member functions invalidate iterators, while all 181 const member functions preserve the iterator validity. 182 </p> 183<div class="note"><table border="0" summary="Note"> 184<tr> 185<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 186<th align="left">Note</th> 187</tr> 188<tr><td align="left" valign="top"><p> 189 Some implementations require iterators, that contain a set of elements, 190 that are <span class="bold"><strong>discovered</strong></span>, but not <span class="bold"><strong>visited</strong></span>. Therefore copying iterators can be inefficient 191 and should be avoided. 192 </p></td></tr> 193</table></div> 194<h6> 195<a name="heap.concepts.iterators.h1"></a> 196 <span class="phrase"><a name="heap.concepts.iterators.example"></a></span><a class="link" href="concepts.html#heap.concepts.iterators.example">Example</a> 197 </h6> 198<p> 199</p> 200<pre class="programlisting"><span class="comment">// PriorityQueue is expected to be a max-heap of integer values</span> 201<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">></span> 202<span class="keyword">void</span> <span class="identifier">iterator_interface</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 203<span class="special">{</span> 204 <span class="identifier">PriorityQueue</span> <span class="identifier">pq</span><span class="special">;</span> 205 206 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> 207 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 208 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> 209 210 <span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">begin</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span> 211 <span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">end</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">end</span><span class="special">();</span> 212 213 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"Priority Queue: iteration"</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 214 <span class="keyword">for</span> <span class="special">(</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">it</span> <span class="special">=</span> <span class="identifier">begin</span><span class="special">;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">end</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> 215 <span class="identifier">cout</span> <span class="special"><<</span> <span class="special">*</span><span class="identifier">it</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 1, 2, 3 in unspecified order</span> 216 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 217<span class="special">}</span> 218</pre> 219<p> 220 </p> 221<div class="section"> 222<div class="titlepage"><div><div><h4 class="title"> 223<a name="heap.concepts.iterators.ordered_iterators"></a><a class="link" href="concepts.html#heap.concepts.iterators.ordered_iterators" title="Ordered Iterators">Ordered 224 Iterators</a> 225</h4></div></div></div> 226<p> 227 Except for <code class="computeroutput"><a class="link" href="../boost/heap/priority_queue.html" title="Class template priority_queue">boost::heap::priority_queue</a></code> 228 all <code class="literal">boost.heap</code> data structures support ordered iterators, 229 which visit all elements of the heap in heap-order. The implementation 230 of these <code class="literal">ordered_iterator</code>s requires some internal bookkeeping, 231 so iterating the a heap in heap order has an amortized complexity of O(N*log(N)). 232 </p> 233<h6> 234<a name="heap.concepts.iterators.ordered_iterators.h0"></a> 235 <span class="phrase"><a name="heap.concepts.iterators.ordered_iterators.example"></a></span><a class="link" href="concepts.html#heap.concepts.iterators.ordered_iterators.example">Example</a> 236 </h6> 237<p> 238</p> 239<pre class="programlisting"><span class="comment">// PriorityQueue is expected to be a max-heap of integer values</span> 240<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">></span> 241<span class="keyword">void</span> <span class="identifier">ordered_iterator_interface</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 242<span class="special">{</span> 243 <span class="identifier">PriorityQueue</span> <span class="identifier">pq</span><span class="special">;</span> 244 245 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> 246 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 247 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> 248 249 <span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">ordered_iterator</span> <span class="identifier">begin</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">ordered_begin</span><span class="special">();</span> 250 <span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">ordered_iterator</span> <span class="identifier">end</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">ordered_end</span><span class="special">();</span> 251 252 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"Priority Queue: ordered iteration"</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 253 <span class="keyword">for</span> <span class="special">(</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">ordered_iterator</span> <span class="identifier">it</span> <span class="special">=</span> <span class="identifier">begin</span><span class="special">;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">end</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> 254 <span class="identifier">cout</span> <span class="special"><<</span> <span class="special">*</span><span class="identifier">it</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 3, 2, 1 (i.e. 1, 2, 3 in heap order)</span> 255 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 256<span class="special">}</span> 257</pre> 258<p> 259 </p> 260</div> 261</div> 262<div class="section"> 263<div class="titlepage"><div><div><h3 class="title"> 264<a name="heap.concepts.comparing"></a><a class="link" href="concepts.html#heap.concepts.comparing" title="Comparing Priority Queues & Equivalence">Comparing Priority Queues & 265 Equivalence</a> 266</h3></div></div></div> 267<p> 268 The data structures of <code class="literal">boost.heap</code> can be compared with 269 standard comparison operators. The comparison is performed by comparing two 270 heaps element by element using <code class="literal">value_compare</code>. 271 </p> 272<div class="note"><table border="0" summary="Note"> 273<tr> 274<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 275<th align="left">Note</th> 276</tr> 277<tr><td align="left" valign="top"><p> 278 Depending on the heap type, this operation can be rather expensive, because 279 both data structures need to be traversed in heap order. On heaps without 280 ordered iterators, the heap needs to be copied internally. The typical 281 complexity is O(n log(n)). 282 </p></td></tr> 283</table></div> 284</div> 285<div class="section"> 286<div class="titlepage"><div><div><h3 class="title"> 287<a name="heap.concepts.merge"></a><a class="link" href="concepts.html#heap.concepts.merge" title="Merging Priority Queues">Merging Priority Queues</a> 288</h3></div></div></div> 289<h4> 290<a name="heap.concepts.merge.h0"></a> 291 <span class="phrase"><a name="heap.concepts.merge.mergable_priority_queues"></a></span><a class="link" href="concepts.html#heap.concepts.merge.mergable_priority_queues">Mergable 292 Priority Queues</a> 293 </h4> 294<h6> 295<a name="heap.concepts.merge.h1"></a> 296 <span class="phrase"><a name="heap.concepts.merge.synopsis"></a></span><a class="link" href="concepts.html#heap.concepts.merge.synopsis">Synopsis</a> 297 </h6> 298<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">mergable_heap_interface</span> 299<span class="special">{</span> 300<span class="keyword">public</span><span class="special">:</span> 301 <span class="comment">// public member functions</span> 302 <span class="keyword">void</span> <span class="identifier">merge</span><span class="special">(</span><span class="identifier">mergable_heap_interface</span> <span class="special">&);</span> 303<span class="special">};</span> 304</pre> 305<p> 306 <code class="literal">boost.heap</code> has a concept of a Mergable Priority Queue. 307 A mergable priority queue can efficiently be merged with a different instance 308 of the same type. 309 </p> 310<h6> 311<a name="heap.concepts.merge.h2"></a> 312 <span class="phrase"><a name="heap.concepts.merge.example"></a></span><a class="link" href="concepts.html#heap.concepts.merge.example">Example</a> 313 </h6> 314<p> 315</p> 316<pre class="programlisting"><span class="comment">// PriorityQueue is expected to be a max-heap of integer values</span> 317<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">></span> 318<span class="keyword">void</span> <span class="identifier">merge_interface</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 319<span class="special">{</span> 320 <span class="identifier">PriorityQueue</span> <span class="identifier">pq</span><span class="special">;</span> 321 322 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 323 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">5</span><span class="special">);</span> 324 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> 325 326 <span class="identifier">PriorityQueue</span> <span class="identifier">pq2</span><span class="special">;</span> 327 328 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> 329 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">4</span><span class="special">);</span> 330 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> 331 332 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">merge</span><span class="special">(</span><span class="identifier">pq2</span><span class="special">);</span> 333 334 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"Priority Queue: merge"</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 335 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"first queue: "</span><span class="special">;</span> 336 <span class="keyword">while</span> <span class="special">(!</span><span class="identifier">pq</span><span class="special">.</span><span class="identifier">empty</span><span class="special">())</span> <span class="special">{</span> 337 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 5 4 3 2 1 0</span> 338 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 339 <span class="special">}</span> 340 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 341 342 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"second queue: "</span><span class="special">;</span> 343 <span class="keyword">while</span> <span class="special">(!</span><span class="identifier">pq2</span><span class="special">.</span><span class="identifier">empty</span><span class="special">())</span> <span class="special">{</span> 344 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 4 2 0</span> 345 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 346 <span class="special">}</span> 347 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 348<span class="special">}</span> 349</pre> 350<p> 351 </p> 352<h4> 353<a name="heap.concepts.merge.h3"></a> 354 <span class="phrase"><a name="heap.concepts.merge.heap_merge_algorithms"></a></span><a class="link" href="concepts.html#heap.concepts.merge.heap_merge_algorithms">Heap 355 Merge Algorithms</a> 356 </h4> 357<p> 358 <code class="literal">boost.heap</code> provides a <code class="literal">heap_merge()</code> 359 algorithm that is can be used to merge different kinds of heaps. Using this 360 algorithm, all <code class="literal">boost.heap</code> data structures can be merged, 361 although some cannot be merged efficiently. 362 </p> 363<h6> 364<a name="heap.concepts.merge.h4"></a> 365 <span class="phrase"><a name="heap.concepts.merge.example0"></a></span><a class="link" href="concepts.html#heap.concepts.merge.example0">Example</a> 366 </h6> 367<p> 368</p> 369<pre class="programlisting"><span class="comment">// PriorityQueue is expected to be a max-heap of integer values</span> 370<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">></span> 371<span class="keyword">void</span> <span class="identifier">heap_merge_algorithm</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 372<span class="special">{</span> 373 <span class="identifier">PriorityQueue</span> <span class="identifier">pq</span><span class="special">;</span> 374 375 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 376 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">5</span><span class="special">);</span> 377 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> 378 379 <span class="identifier">PriorityQueue</span> <span class="identifier">pq2</span><span class="special">;</span> 380 381 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> 382 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">4</span><span class="special">);</span> 383 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">0</span><span class="special">);</span> 384 385 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">heap</span><span class="special">::</span><span class="identifier">heap_merge</span><span class="special">(</span><span class="identifier">pq</span><span class="special">,</span> <span class="identifier">pq2</span><span class="special">);</span> 386 387 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"Priority Queue: merge"</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 388 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"first queue: "</span><span class="special">;</span> 389 <span class="keyword">while</span> <span class="special">(!</span><span class="identifier">pq</span><span class="special">.</span><span class="identifier">empty</span><span class="special">())</span> <span class="special">{</span> 390 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 5 4 3 2 1 0</span> 391 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 392 <span class="special">}</span> 393 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 394 395 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"second queue: "</span><span class="special">;</span> 396 <span class="keyword">while</span> <span class="special">(!</span><span class="identifier">pq2</span><span class="special">.</span><span class="identifier">empty</span><span class="special">())</span> <span class="special">{</span> 397 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 4 2 0</span> 398 <span class="identifier">pq2</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 399 <span class="special">}</span> 400 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 401<span class="special">}</span> 402</pre> 403<p> 404 </p> 405</div> 406<div class="section"> 407<div class="titlepage"><div><div><h3 class="title"> 408<a name="heap.concepts.mutability"></a><a class="link" href="concepts.html#heap.concepts.mutability" title="Mutability">Mutability</a> 409</h3></div></div></div> 410<p> 411 Some priority queues of <code class="literal">boost.heap</code> are mutable, that means 412 the priority of their elements can be changed. To achieve mutability, <code class="literal">boost.heap</code> 413 introduces the concept of <span class="bold"><strong>handles</strong></span>, which 414 can be used to access the internal nodes of the priority queue in order to 415 change its value and to restore the heap order. 416 </p> 417<h6> 418<a name="heap.concepts.mutability.h0"></a> 419 <span class="phrase"><a name="heap.concepts.mutability.synopsis"></a></span><a class="link" href="concepts.html#heap.concepts.mutability.synopsis">Synopsis</a> 420 </h6> 421<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">mutable_heap_interface</span> 422<span class="special">{</span> 423<span class="keyword">public</span><span class="special">:</span> 424 <span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">iterator</span><span class="special">;</span> 425 <span class="keyword">struct</span> <span class="identifier">handle_type</span> 426 <span class="special">{</span> 427 <span class="identifier">value_type</span> <span class="special">&</span> <span class="keyword">operator</span><span class="special">*()</span> <span class="keyword">const</span><span class="special">;</span> 428 <span class="special">};</span> 429 430 <span class="keyword">static</span> <span class="identifier">handle_type</span> <span class="identifier">s_iterator_to_handle</span><span class="special">(</span><span class="identifier">iterator</span> <span class="keyword">const</span> <span class="special">&);</span> 431 432 <span class="comment">// priority queue interface</span> 433 <span class="identifier">handle_type</span> <span class="identifier">push</span><span class="special">(</span><span class="identifier">T</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">v</span><span class="special">);</span> 434 435 <span class="comment">// update element via assignment and fix heap</span> 436 <span class="keyword">void</span> <span class="identifier">update</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">handle</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">v</span><span class="special">);</span> 437 <span class="keyword">void</span> <span class="identifier">increase</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">handle</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">v</span><span class="special">);</span> 438 <span class="keyword">void</span> <span class="identifier">decrease</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">handle</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">v</span><span class="special">);</span> 439 440 <span class="comment">// fix heap after element has been changed via the handle</span> 441 <span class="keyword">void</span> <span class="identifier">update</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">handle</span><span class="special">);</span> 442 <span class="keyword">void</span> <span class="identifier">increase</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">handle</span><span class="special">);</span> 443 <span class="keyword">void</span> <span class="identifier">decrease</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">handle</span><span class="special">);</span> 444<span class="special">};</span> 445</pre> 446<div class="warning"><table border="0" summary="Warning"> 447<tr> 448<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../doc/src/images/warning.png"></td> 449<th align="left">Warning</th> 450</tr> 451<tr><td align="left" valign="top"><p> 452 Incorrect use of <code class="literal">increase</code> or <code class="literal">decrease</code> 453 may corrupt the priority queue data structure. If unsure use <code class="literal">update</code> 454 can be used at the cost of efficiency. 455 </p></td></tr> 456</table></div> 457<h6> 458<a name="heap.concepts.mutability.h1"></a> 459 <span class="phrase"><a name="heap.concepts.mutability.example"></a></span><a class="link" href="concepts.html#heap.concepts.mutability.example">Example</a> 460 </h6> 461<p> 462</p> 463<pre class="programlisting"><span class="comment">// PriorityQueue is expected to be a max-heap of integer values</span> 464<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">></span> 465<span class="keyword">void</span> <span class="identifier">mutable_interface</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 466<span class="special">{</span> 467 <span class="identifier">PriorityQueue</span> <span class="identifier">pq</span><span class="special">;</span> 468 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">handle_type</span> <span class="identifier">handle_t</span><span class="special">;</span> 469 470 <span class="identifier">handle_t</span> <span class="identifier">t3</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 471 <span class="identifier">handle_t</span> <span class="identifier">t5</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">5</span><span class="special">);</span> 472 <span class="identifier">handle_t</span> <span class="identifier">t1</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> 473 474 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">update</span><span class="special">(</span><span class="identifier">t3</span><span class="special">,</span> <span class="number">4</span><span class="special">);</span> 475 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">increase</span><span class="special">(</span><span class="identifier">t5</span><span class="special">,</span> <span class="number">7</span><span class="special">);</span> 476 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">decrease</span><span class="special">(</span><span class="identifier">t1</span><span class="special">,</span> <span class="number">0</span><span class="special">);</span> 477 478 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"Priority Queue: update"</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 479 <span class="keyword">while</span> <span class="special">(!</span><span class="identifier">pq</span><span class="special">.</span><span class="identifier">empty</span><span class="special">())</span> <span class="special">{</span> 480 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 7, 4, 0</span> 481 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 482 <span class="special">}</span> 483 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 484<span class="special">}</span> 485</pre> 486<p> 487 </p> 488<p> 489 Note that handles can be stored inside the <code class="literal">value_type</code>: 490 </p> 491<p> 492</p> 493<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">heap_data</span> 494<span class="special">{</span> 495 <span class="identifier">fibonacci_heap</span><span class="special"><</span><span class="identifier">heap_data</span><span class="special">>::</span><span class="identifier">handle_type</span> <span class="identifier">handle</span><span class="special">;</span> 496 <span class="keyword">int</span> <span class="identifier">payload</span><span class="special">;</span> 497 498 <span class="identifier">heap_data</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">):</span> 499 <span class="identifier">payload</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 500 <span class="special">{}</span> 501 502 <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special"><(</span><span class="identifier">heap_data</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">rhs</span><span class="special">)</span> <span class="keyword">const</span> 503 <span class="special">{</span> 504 <span class="keyword">return</span> <span class="identifier">payload</span> <span class="special"><</span> <span class="identifier">rhs</span><span class="special">.</span><span class="identifier">payload</span><span class="special">;</span> 505 <span class="special">}</span> 506<span class="special">};</span> 507 508<span class="keyword">void</span> <span class="identifier">mutable_interface_handle_in_value</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 509<span class="special">{</span> 510 <span class="identifier">fibonacci_heap</span><span class="special"><</span><span class="identifier">heap_data</span><span class="special">></span> <span class="identifier">heap</span><span class="special">;</span> 511 <span class="identifier">heap_data</span> <span class="identifier">f</span><span class="special">(</span><span class="number">2</span><span class="special">);</span> 512 513 <span class="identifier">fibonacci_heap</span><span class="special"><</span><span class="identifier">heap_data</span><span class="special">>::</span><span class="identifier">handle_type</span> <span class="identifier">handle</span> <span class="special">=</span> <span class="identifier">heap</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="identifier">f</span><span class="special">);</span> 514 <span class="special">(*</span><span class="identifier">handle</span><span class="special">).</span><span class="identifier">handle</span> <span class="special">=</span> <span class="identifier">handle</span><span class="special">;</span> <span class="comment">// store handle in node</span> 515<span class="special">}</span> 516</pre> 517<p> 518 </p> 519<h4> 520<a name="heap.concepts.mutability.h2"></a> 521 <span class="phrase"><a name="heap.concepts.mutability.the_fixup_interface"></a></span><a class="link" href="concepts.html#heap.concepts.mutability.the_fixup_interface">The 522 Fixup Interface</a> 523 </h4> 524<p> 525 There are two different APIs to support mutability. The first family of functions 526 provides update functionality by changing the current element by assigning 527 a new value. The second family of functions can be used to fix the heap data 528 structure after an element has been changed directly via a handle. While 529 this provides the user with a means to modify the priority of queue elements 530 without the need to change their non-priority part, this needs to be handled 531 with care. The heap needs to be fixed up immediately after the priority of 532 the element has been changed. 533 </p> 534<p> 535 Beside an <code class="literal">update</code> function, two additional functions <code class="literal">increase</code> 536 and <code class="literal">decrease</code> are provided, that are generally more efficient 537 than the generic <code class="literal">update</code> function. However the user has 538 do ensure, that the priority of an element is changed to the right direction. 539 </p> 540<h6> 541<a name="heap.concepts.mutability.h3"></a> 542 <span class="phrase"><a name="heap.concepts.mutability.example0"></a></span><a class="link" href="concepts.html#heap.concepts.mutability.example0">Example</a> 543 </h6> 544<p> 545</p> 546<pre class="programlisting"><span class="comment">// PriorityQueue is expected to be a max-heap of integer values</span> 547<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">></span> 548<span class="keyword">void</span> <span class="identifier">mutable_fixup_interface</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> 549<span class="special">{</span> 550 <span class="identifier">PriorityQueue</span> <span class="identifier">pq</span><span class="special">;</span> 551 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">PriorityQueue</span><span class="special">::</span><span class="identifier">handle_type</span> <span class="identifier">handle_t</span><span class="special">;</span> 552 553 <span class="identifier">handle_t</span> <span class="identifier">t3</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">3</span><span class="special">);</span> 554 <span class="identifier">handle_t</span> <span class="identifier">t5</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">5</span><span class="special">);</span> 555 <span class="identifier">handle_t</span> <span class="identifier">t1</span> <span class="special">=</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">push</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> 556 557 <span class="special">*</span><span class="identifier">t3</span> <span class="special">=</span> <span class="number">4</span><span class="special">;</span> 558 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">update</span><span class="special">(</span><span class="identifier">t3</span><span class="special">);</span> 559 560 <span class="special">*</span><span class="identifier">t5</span> <span class="special">=</span> <span class="number">7</span><span class="special">;</span> 561 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">increase</span><span class="special">(</span><span class="identifier">t5</span><span class="special">);</span> 562 563 <span class="special">*</span><span class="identifier">t1</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> 564 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">decrease</span><span class="special">(</span><span class="identifier">t1</span><span class="special">);</span> 565 566 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"Priority Queue: update with fixup"</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 567 <span class="keyword">while</span> <span class="special">(!</span><span class="identifier">pq</span><span class="special">.</span><span class="identifier">empty</span><span class="special">())</span> <span class="special">{</span> 568 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">pq</span><span class="special">.</span><span class="identifier">top</span><span class="special">()</span> <span class="special"><<</span> <span class="string">" "</span><span class="special">;</span> <span class="comment">// 7, 4, 0</span> 569 <span class="identifier">pq</span><span class="special">.</span><span class="identifier">pop</span><span class="special">();</span> 570 <span class="special">}</span> 571 <span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 572<span class="special">}</span> 573</pre> 574<p> 575 </p> 576<p> 577 Iterators can be converted to handles using the static member function <code class="literal">s_handle_from_iterator</code>. 578 However most implementations of <code class="literal">update</code> invalidate all 579 iterators. The most notable exception is the <code class="computeroutput"><a class="link" href="../boost/heap/fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci 580 heap</a></code>, providing a lazy update function, that just invalidates 581 the iterators, that are related to this handle. 582 </p> 583<div class="warning"><table border="0" summary="Warning"> 584<tr> 585<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../doc/src/images/warning.png"></td> 586<th align="left">Warning</th> 587</tr> 588<tr><td align="left" valign="top"><p> 589 After changing the priority via a handle, the heap needs to be fixed by 590 calling one of the update functions. Otherwise the priority queue structure 591 may be corrupted! 592 </p></td></tr> 593</table></div> 594</div> 595<div class="section"> 596<div class="titlepage"><div><div><h3 class="title"> 597<a name="heap.concepts.stability"></a><a class="link" href="concepts.html#heap.concepts.stability" title="Stability">Stability</a> 598</h3></div></div></div> 599<p> 600 A priority queue is `stable', if elements with the same priority are popped 601 from the heap, in the same order as they are inserted. The data structures 602 provided by <code class="literal">boost.heap</code>, can be configured to be stable 603 at compile time using the <code class="computeroutput"><a class="link" href="../boost/heap/stable.html" title="Struct template stable">boost::heap::stable</a></code> 604 policy. Two notions of stability are supported. If a heap is configured with 605 <span class="bold"><strong>no stability</strong></span>, the order of nodes of the 606 same priority is undefined, if it is configured as <span class="bold"><strong>stable</strong></span>, 607 nodes of the same priority are ordered by their insertion time. 608 </p> 609<p> 610 Stability is achieved by associating an integer version count with each value 611 in order to distinguish values with the same node. The type of this version 612 count defaults to <code class="literal">boost::uintmax_t</code>, which is at least 613 64bit on most systems. However it can be configured to use a different type 614 using the <code class="computeroutput"><a class="link" href="../boost/heap/stability_counter_type.html" title="Struct template stability_counter_type">boost::heap::stability_counter_type</a></code> 615 template argument. 616 </p> 617<div class="warning"><table border="0" summary="Warning"> 618<tr> 619<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../doc/src/images/warning.png"></td> 620<th align="left">Warning</th> 621</tr> 622<tr><td align="left" valign="top"><p> 623 The stability counter is prone to integer overflows. If an overflow occurs 624 during a <code class="literal">push()</code> call, the operation will fail and an 625 exception is thrown. Later <code class="literal">push()</code> call will succeed, 626 but the stable heap order will be compromised. However an integer overflow 627 at 64bit is very unlikely: if an application would issue one <code class="literal">push()</code> 628 operation per microsecond, the value will overflow in more than 500000 629 years. 630 </p></td></tr> 631</table></div> 632</div> 633</div> 634<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 635<td align="left"></td> 636<td align="right"><div class="copyright-footer">Copyright © 2010, 2011 Tim Blechmann<p> 637 Distributed under the Boost Software License, Version 1.0. (See accompanying 638 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 639 </p> 640</div></td> 641</tr></table> 642<hr> 643<div class="spirit-nav"> 644<a accesskey="p" href="../heap.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../heap.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="data_structures.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 645</div> 646</body> 647</html> 648
