diff options
Diffstat (limited to 'doc/html/boost/heap/fibonacci_heap.html')
| -rw-r--r-- | doc/html/boost/heap/fibonacci_heap.html | 235 |
1 files changed, 89 insertions, 146 deletions
diff --git a/doc/html/boost/heap/fibonacci_heap.html b/doc/html/boost/heap/fibonacci_heap.html index 80915e91a3..2f537585c7 100644 --- a/doc/html/boost/heap/fibonacci_heap.html +++ b/doc/html/boost/heap/fibonacci_heap.html @@ -4,7 +4,7 @@ <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> <title>Class template fibonacci_heap</title> <link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css"> -<meta name="generator" content="DocBook XSL Stylesheets V1.76.1"> +<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> <link rel="home" href="../../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> <link rel="up" href="../../heap/reference.html#header.boost.heap.fibonacci_heap_hpp" title="Header <boost/heap/fibonacci_heap.hpp>"> <link rel="prev" href="d_ary_heap.html" title="Class template d_ary_heap"> @@ -51,48 +51,48 @@ <span class="keyword">typedef</span> <span class="identifier">implementation_defined</span><span class="special">::</span><span class="identifier">handle_type</span> <a name="boost.heap.fibonacci_heap.handle_type"></a><span class="identifier">handle_type</span><span class="special">;</span> <span class="comment">// <a class="link" href="fibonacci_heap.html#boost.heap.fibonacci_heapconstruct-copy-destruct">construct/copy/destruct</a></span> - <span class="keyword">explicit</span> <a class="link" href="fibonacci_heap.html#idp14226576-bb"><span class="identifier">fibonacci_heap</span></a><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><span class="special">)</span><span class="special">)</span><span class="special">;</span> - <a class="link" href="fibonacci_heap.html#idp14230192-bb"><span class="identifier">fibonacci_heap</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> - <a class="link" href="fibonacci_heap.html#idp14233536-bb"><span class="identifier">fibonacci_heap</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span><span class="special">)</span><span class="special">;</span> - <a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idp14237696-bb"><span class="keyword">operator</span><span class="special">=</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span><span class="special">)</span><span class="special">;</span> - <a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idp66124224-bb"><span class="keyword">operator</span><span class="special">=</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> - <a class="link" href="fibonacci_heap.html#idp66128144-bb"><span class="special">~</span><span class="identifier">fibonacci_heap</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">explicit</span> <a class="link" href="fibonacci_heap.html#idm46563409901408-bb"><span class="identifier">fibonacci_heap</span></a><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><span class="special">)</span><span class="special">)</span><span class="special">;</span> + <a class="link" href="fibonacci_heap.html#idm46563409898032-bb"><span class="identifier">fibonacci_heap</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> + <a class="link" href="fibonacci_heap.html#idm46563409894912-bb"><span class="identifier">fibonacci_heap</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span><span class="special">)</span><span class="special">;</span> + <a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idm46563409890912-bb"><span class="keyword">operator</span><span class="special">=</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span><span class="special">)</span><span class="special">;</span> + <a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idm46563409886336-bb"><span class="keyword">operator</span><span class="special">=</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> + <a class="link" href="fibonacci_heap.html#idm46563409882656-bb"><span class="special">~</span><span class="identifier">fibonacci_heap</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span> - <span class="comment">// <a class="link" href="fibonacci_heap.html#idp44878032-bb">public member functions</a></span> - <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idp44878592-bb"><span class="identifier">empty</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="identifier">size_type</span> <a class="link" href="fibonacci_heap.html#idp83572944-bb"><span class="identifier">size</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="identifier">size_type</span> <a class="link" href="fibonacci_heap.html#idp83576832-bb"><span class="identifier">max_size</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp83580720-bb"><span class="identifier">clear</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span> - <span class="identifier">allocator_type</span> <a class="link" href="fibonacci_heap.html#idp83584336-bb"><span class="identifier">get_allocator</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp83588256-bb"><span class="identifier">swap</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> - <span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idp83592160-bb"><span class="identifier">top</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="identifier">handle_type</span> <a class="link" href="fibonacci_heap.html#idp83596048-bb"><span class="identifier">push</span></a><span class="special">(</span><span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span><span class="special">...</span> Args<span class="special">></span> <span class="identifier">handle_type</span> <a class="link" href="fibonacci_heap.html#idp83600192-bb"><span class="identifier">emplace</span></a><span class="special">(</span><span class="identifier">Args</span> <span class="special">&&</span><span class="special">...</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp83605600-bb"><span class="identifier">pop</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39157152-bb"><span class="identifier">update</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39162000-bb"><span class="identifier">update_lazy</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39168112-bb"><span class="identifier">update</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39172832-bb"><span class="identifier">update_lazy</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39178256-bb"><span class="identifier">increase</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39183952-bb"><span class="identifier">increase</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39188672-bb"><span class="identifier">decrease</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp39194368-bb"><span class="identifier">decrease</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp88173584-bb"><span class="identifier">erase</span></a><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> - <span class="identifier">iterator</span> <a class="link" href="fibonacci_heap.html#idp88178048-bb"><span class="identifier">begin</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="identifier">iterator</span> <a class="link" href="fibonacci_heap.html#idp88181936-bb"><span class="identifier">end</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="identifier">ordered_iterator</span> <a class="link" href="fibonacci_heap.html#idp88185824-bb"><span class="identifier">ordered_begin</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="identifier">ordered_iterator</span> <a class="link" href="fibonacci_heap.html#idp88189392-bb"><span class="identifier">ordered_end</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idp88192960-bb"><span class="identifier">merge</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> - <span class="identifier">value_compare</span> <span class="keyword">const</span> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idp88196576-bb"><span class="identifier">value_comp</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idp88199616-bb"><span class="keyword">operator</span><span class="special"><</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idp88204768-bb"><span class="keyword">operator</span><span class="special">></span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idp14205488-bb"><span class="keyword">operator</span><span class="special">>=</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idp14210640-bb"><span class="keyword">operator</span><span class="special"><=</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idp14215792-bb"><span class="keyword">operator</span><span class="special">==</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idp14221104-bb"><span class="keyword">operator</span><span class="special">!=</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="comment">// <a class="link" href="fibonacci_heap.html#idm46563410039504-bb">public member functions</a></span> + <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idm46563410038944-bb"><span class="identifier">empty</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="identifier">size_type</span> <a class="link" href="fibonacci_heap.html#idm46563410035264-bb"><span class="identifier">size</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="identifier">size_type</span> <a class="link" href="fibonacci_heap.html#idm46563410031584-bb"><span class="identifier">max_size</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563410027904-bb"><span class="identifier">clear</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span> + <span class="identifier">allocator_type</span> <a class="link" href="fibonacci_heap.html#idm46563410024512-bb"><span class="identifier">get_allocator</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563410020880-bb"><span class="identifier">swap</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idm46563410017216-bb"><span class="identifier">top</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="identifier">handle_type</span> <a class="link" href="fibonacci_heap.html#idm46563410013552-bb"><span class="identifier">push</span></a><span class="special">(</span><span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span><span class="special">...</span> Args<span class="special">></span> <span class="identifier">handle_type</span> <a class="link" href="fibonacci_heap.html#idm46563410009280-bb"><span class="identifier">emplace</span></a><span class="special">(</span><span class="identifier">Args</span> <span class="special">&&</span><span class="special">...</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563410003824-bb"><span class="identifier">pop</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563410000400-bb"><span class="identifier">update</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409995392-bb"><span class="identifier">update_lazy</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409989408-bb"><span class="identifier">update</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409984624-bb"><span class="identifier">update_lazy</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409979008-bb"><span class="identifier">increase</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409973136-bb"><span class="identifier">increase</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409968352-bb"><span class="identifier">decrease</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">,</span> <span class="identifier">const_reference</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409962480-bb"><span class="identifier">decrease</span></a><span class="special">(</span><span class="identifier">handle_type</span><span class="special">)</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409957648-bb"><span class="identifier">erase</span></a><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="identifier">iterator</span> <a class="link" href="fibonacci_heap.html#idm46563409953088-bb"><span class="identifier">begin</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="identifier">iterator</span> <a class="link" href="fibonacci_heap.html#idm46563409949392-bb"><span class="identifier">end</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="identifier">ordered_iterator</span> <a class="link" href="fibonacci_heap.html#idm46563409945728-bb"><span class="identifier">ordered_begin</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="identifier">ordered_iterator</span> <a class="link" href="fibonacci_heap.html#idm46563409941984-bb"><span class="identifier">ordered_end</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">void</span> <a class="link" href="fibonacci_heap.html#idm46563409938256-bb"><span class="identifier">merge</span></a><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="identifier">value_compare</span> <span class="keyword">const</span> <span class="special">&</span> <a class="link" href="fibonacci_heap.html#idm46563409934592-bb"><span class="identifier">value_comp</span></a><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idm46563409931760-bb"><span class="keyword">operator</span><span class="special"><</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idm46563409926784-bb"><span class="keyword">operator</span><span class="special">></span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idm46563409921808-bb"><span class="keyword">operator</span><span class="special">>=</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idm46563409916832-bb"><span class="keyword">operator</span><span class="special"><=</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idm46563409911856-bb"><span class="keyword">operator</span><span class="special">==</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> + <span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a class="link" href="fibonacci_heap.html#idm46563409906720-bb"><span class="keyword">operator</span><span class="special">!=</span></a><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> - <span class="comment">// <a class="link" href="fibonacci_heap.html#idp66129120-bb">public static functions</a></span> - <span class="keyword">static</span> <span class="identifier">handle_type</span> <a class="link" href="fibonacci_heap.html#idp66129680-bb"><span class="identifier">s_handle_from_iterator</span></a><span class="special">(</span><span class="identifier">iterator</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> + <span class="comment">// <a class="link" href="fibonacci_heap.html#idm46563409881680-bb">public static functions</a></span> + <span class="keyword">static</span> <span class="identifier">handle_type</span> <a class="link" href="fibonacci_heap.html#idm46563409881120-bb"><span class="identifier">s_handle_from_iterator</span></a><span class="special">(</span><span class="identifier">iterator</span> <span class="keyword">const</span> <span class="special">&</span><span class="special">)</span><span class="special">;</span> <span class="comment">// public data members</span> <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> @@ -102,10 +102,10 @@ <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="special">}</span><span class="special">;</span></pre></div> <div class="refsect1"> -<a name="idp143468176"></a><h2>Description</h2> +<a name="idm45928042785280"></a><h2>Description</h2> <p>The template parameter T is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.</p> <p>The container supports the following options:</p> -<div class="itemizedlist"><ul class="itemizedlist" type="disc"> +<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> <li class="listitem"><p><code class="computeroutput">boost::heap::stable<></code>, defaults to <code class="computeroutput">stable<false></code> </p></li> <li class="listitem"><p><code class="computeroutput">boost::heap::compare<></code>, defaults to <code class="computeroutput">compare<std::less<T></code> ></p></li> <li class="listitem"><p><code class="computeroutput">boost::heap::allocator<></code>, defaults to <code class="computeroutput">allocator<std::allocator<T></code> ></p></li> @@ -115,7 +115,7 @@ <p> </p> <div class="refsect2"> -<a name="idp143478432"></a><h3> +<a name="idm45928042775024"></a><h3> <a name="boost.heap.fibonacci_heaptypes"></a><code class="computeroutput">fibonacci_heap</code> public types</h3> @@ -123,269 +123,212 @@ <p> <span class="keyword">typedef</span> <span class="identifier">implementation_defined</span><span class="special">::</span><span class="identifier">iterator</span> <a name="boost.heap.fibonacci_heap.iterator"></a><span class="identifier">iterator</span><span class="special">;</span></p> <p><span class="bold"><strong>Note:</strong></span> The iterator does not traverse the priority queue in order of the priorities. </p> -<p> - </p> </li></ol></div> </div> <div class="refsect2"> -<a name="idp143486368"></a><h3> +<a name="idm45928042767408"></a><h3> <a name="boost.heap.fibonacci_heapconstruct-copy-destruct"></a><code class="computeroutput">fibonacci_heap</code> public construct/copy/destruct</h3> <div class="orderedlist"><ol class="orderedlist" type="1"> <li class="listitem"> -<pre class="literallayout"><span class="keyword">explicit</span> <a name="idp14226576-bb"></a><span class="identifier">fibonacci_heap</span><span class="special">(</span><span class="identifier">value_compare</span> <span class="keyword">const</span> <span class="special">&</span> cmp <span class="special">=</span> <span class="identifier">value_compare</span><span class="special">(</span><span class="special">)</span><span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">explicit</span> <a name="idm46563409901408-bb"></a><span class="identifier">fibonacci_heap</span><span class="special">(</span><span class="identifier">value_compare</span> <span class="keyword">const</span> <span class="special">&</span> cmp <span class="special">=</span> <span class="identifier">value_compare</span><span class="special">(</span><span class="special">)</span><span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> constructs an empty priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><a name="idp14230192-bb"></a><span class="identifier">fibonacci_heap</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><a name="idm46563409898032-bb"></a><span class="identifier">fibonacci_heap</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> copy-constructs priority queue from rhs.</p> <p><span class="bold"><strong>Complexity:</strong></span> Linear. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><a name="idp14233536-bb"></a><span class="identifier">fibonacci_heap</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span> rhs<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><a name="idm46563409894912-bb"></a><span class="identifier">fibonacci_heap</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span> rhs<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> C++11-style move constructor.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant.</p> <p><span class="bold"><strong>Note:</strong></span> Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a name="idp14237696-bb"></a><span class="keyword">operator</span><span class="special">=</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span> rhs<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a name="idm46563409890912-bb"></a><span class="keyword">operator</span><span class="special">=</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&&</span> rhs<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> C++11-style move assignment.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant.</p> <p><span class="bold"><strong>Note:</strong></span> Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a name="idp66124224-bb"></a><span class="keyword">operator</span><span class="special">=</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> <a name="idm46563409886336-bb"></a><span class="keyword">operator</span><span class="special">=</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Assigns priority queue from rhs.</p> <p><span class="bold"><strong>Complexity:</strong></span> Linear. </p> -<p> - </p> </li> -<li class="listitem"><pre class="literallayout"><a name="idp66128144-bb"></a><span class="special">~</span><span class="identifier">fibonacci_heap</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span></pre></li> +<li class="listitem"><pre class="literallayout"><a name="idm46563409882656-bb"></a><span class="special">~</span><span class="identifier">fibonacci_heap</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span></pre></li> </ol></div> </div> <div class="refsect2"> -<a name="idp143539568"></a><h3> -<a name="idp44878032-bb"></a><code class="computeroutput">fibonacci_heap</code> public member functions</h3> +<a name="idm45928042715536"></a><h3> +<a name="idm46563410039504-bb"></a><code class="computeroutput">fibonacci_heap</code> public member functions</h3> <div class="orderedlist"><ol class="orderedlist" type="1"> <li class="listitem"> -<pre class="literallayout"><span class="keyword">bool</span> <a name="idp44878592-bb"></a><span class="identifier">empty</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">bool</span> <a name="idm46563410038944-bb"></a><span class="identifier">empty</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns true, if the priority queue contains no elements.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">size_type</span> <a name="idp83572944-bb"></a><span class="identifier">size</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="identifier">size_type</span> <a name="idm46563410035264-bb"></a><span class="identifier">size</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns the number of elements contained in the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">size_type</span> <a name="idp83576832-bb"></a><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></pre> +<pre class="literallayout"><span class="identifier">size_type</span> <a name="idm46563410031584-bb"></a><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></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns the maximum number of elements the priority queue can contain.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp83580720-bb"></a><span class="identifier">clear</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563410027904-bb"></a><span class="identifier">clear</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Removes all elements from the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Linear. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">allocator_type</span> <a name="idp83584336-bb"></a><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></pre> +<pre class="literallayout"><span class="identifier">allocator_type</span> <a name="idm46563410024512-bb"></a><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></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns allocator.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp83588256-bb"></a><span class="identifier">swap</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563410020880-bb"></a><span class="identifier">swap</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Swaps two priority queues.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> <a name="idp83592160-bb"></a><span class="identifier">top</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> <a name="idm46563410017216-bb"></a><span class="identifier">top</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns a const_reference to the maximum element.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">handle_type</span> <a name="idp83596048-bb"></a><span class="identifier">push</span><span class="special">(</span><span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> v<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="identifier">handle_type</span> <a name="idm46563410013552-bb"></a><span class="identifier">push</span><span class="special">(</span><span class="identifier">value_type</span> <span class="keyword">const</span> <span class="special">&</span> v<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Adds a new element to the priority queue. Returns handle to element</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant.</p> <p><span class="bold"><strong>Note:</strong></span> Does not invalidate iterators. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span><span class="special">...</span> Args<span class="special">></span> <span class="identifier">handle_type</span> <a name="idp83600192-bb"></a><span class="identifier">emplace</span><span class="special">(</span><span class="identifier">Args</span> <span class="special">&&</span><span class="special">...</span> args<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span><span class="special">...</span> Args<span class="special">></span> <span class="identifier">handle_type</span> <a name="idm46563410009280-bb"></a><span class="identifier">emplace</span><span class="special">(</span><span class="identifier">Args</span> <span class="special">&&</span><span class="special">...</span> args<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant.</p> <p><span class="bold"><strong>Note:</strong></span> Does not invalidate iterators. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp83605600-bb"></a><span class="identifier">pop</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563410003824-bb"></a><span class="identifier">pop</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Removes the top element from the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Logarithmic (amortized). Linear (worst case). </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39157152-bb"></a><span class="identifier">update</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563410000400-bb"></a><span class="identifier">update</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Assigns <code class="computeroutput">v</code> to the element handled by <code class="computeroutput">handle</code> & updates the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Logarithmic if current value < v, Constant otherwise. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39162000-bb"></a><span class="identifier">update_lazy</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409995392-bb"></a><span class="identifier">update_lazy</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Assigns <code class="computeroutput">v</code> to the element handled by <code class="computeroutput">handle</code> & updates the priority queue.</p> -<p><span class="bold"><strong>Complexity:</strong></span> Logarithmic if current value < v, Constant otherwise. </p> -<p> -</p> +<p><span class="bold"><strong>Complexity:</strong></span> Logarithmic if current value < v, Constant otherwise.</p> <p><span class="bold"><strong>Rationale:</strong></span> The lazy update function is a modification of the traditional update, that just invalidates the iterator to the object referred to by the handle. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39168112-bb"></a><span class="identifier">update</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409989408-bb"></a><span class="identifier">update</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Updates the heap after the element handled by <code class="computeroutput">handle</code> has been changed.</p> <p><span class="bold"><strong>Complexity:</strong></span> Logarithmic.</p> <p><span class="bold"><strong>Note:</strong></span> If this is not called, after a handle has been updated, the behavior of the data structure is undefined! </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39172832-bb"></a><span class="identifier">update_lazy</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre> -<p><span class="bold"><strong>Effects:</strong></span> Assigns <code class="computeroutput">v</code> to the element handled by <code class="computeroutput">handle</code> & updates the priority queue.</p> -<p><span class="bold"><strong>Complexity:</strong></span> Logarithmic if current value < v, Constant otherwise. </p> -<p> - (handle_type handle)</p> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409984624-bb"></a><span class="identifier">update_lazy</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre>(handle_type handle) <p><span class="bold"><strong>Effects:</strong></span> Assigns <code class="computeroutput">v</code> to the element handled by <code class="computeroutput">handle</code> & updates the priority queue.</p> +<p><span class="bold"><strong>Complexity:</strong></span> Logarithmic if current value < v, Constant otherwise. (handle_type handle)</p> <p><span class="bold"><strong>Rationale:</strong></span> The lazy update function is a modification of the traditional update, that just invalidates the iterator to the object referred to by the handle. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39178256-bb"></a><span class="identifier">increase</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409979008-bb"></a><span class="identifier">increase</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Assigns <code class="computeroutput">v</code> to the element handled by <code class="computeroutput">handle</code> & updates the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant.</p> <p><span class="bold"><strong>Note:</strong></span> The new value is expected to be greater than the current one </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39183952-bb"></a><span class="identifier">increase</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409973136-bb"></a><span class="identifier">increase</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Updates the heap after the element handled by <code class="computeroutput">handle</code> has been changed.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant.</p> <p><span class="bold"><strong>Note:</strong></span> If this is not called, after a handle has been updated, the behavior of the data structure is undefined! </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39188672-bb"></a><span class="identifier">decrease</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409968352-bb"></a><span class="identifier">decrease</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">,</span> <span class="identifier">const_reference</span> v<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Assigns <code class="computeroutput">v</code> to the element handled by <code class="computeroutput">handle</code> & updates the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Logarithmic.</p> <p><span class="bold"><strong>Note:</strong></span> The new value is expected to be less than the current one </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp39194368-bb"></a><span class="identifier">decrease</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409962480-bb"></a><span class="identifier">decrease</span><span class="special">(</span><span class="identifier">handle_type</span> handle<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Updates the heap after the element handled by <code class="computeroutput">handle</code> has been changed.</p> <p><span class="bold"><strong>Complexity:</strong></span> Logarithmic.</p> <p><span class="bold"><strong>Note:</strong></span> The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined! </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp88173584-bb"></a><span class="identifier">erase</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> handle<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409957648-bb"></a><span class="identifier">erase</span><span class="special">(</span><span class="identifier">handle_type</span> <span class="keyword">const</span> <span class="special">&</span> handle<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Removes the element handled by <code class="computeroutput">handle</code> from the <code class="computeroutput"><a class="link" href="priority_queue.html" title="Class template priority_queue">priority_queue</a></code>.</p> <p><span class="bold"><strong>Complexity:</strong></span> Logarithmic. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">iterator</span> <a name="idp88178048-bb"></a><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></pre> +<pre class="literallayout"><span class="identifier">iterator</span> <a name="idm46563409953088-bb"></a><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></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns an iterator to the first element contained in the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">iterator</span> <a name="idp88181936-bb"></a><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></pre> +<pre class="literallayout"><span class="identifier">iterator</span> <a name="idm46563409949392-bb"></a><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></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns an iterator to the end of the priority queue.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">ordered_iterator</span> <a name="idp88185824-bb"></a><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></pre> +<pre class="literallayout"><span class="identifier">ordered_iterator</span> <a name="idm46563409945728-bb"></a><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></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns an ordered iterator to the first element contained in the priority queue.</p> <p><span class="bold"><strong>Note:</strong></span> Ordered iterators traverse the priority queue in heap order. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">ordered_iterator</span> <a name="idp88189392-bb"></a><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></pre> +<pre class="literallayout"><span class="identifier">ordered_iterator</span> <a name="idm46563409941984-bb"></a><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></pre> <p><span class="bold"><strong>Effects:</strong></span> Returns an ordered iterator to the end of the priority queue.</p> <p><span class="bold"><strong>Note:</strong></span> Ordered iterators traverse the priority queue in heap order. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">void</span> <a name="idp88192960-bb"></a><span class="identifier">merge</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">void</span> <a name="idm46563409938256-bb"></a><span class="identifier">merge</span><span class="special">(</span><a class="link" href="fibonacci_heap.html" title="Class template fibonacci_heap">fibonacci_heap</a> <span class="special">&</span> rhs<span class="special">)</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effects:</strong></span> Merge with priority queue rhs.</p> <p><span class="bold"><strong>Complexity:</strong></span> Constant. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="identifier">value_compare</span> <span class="keyword">const</span> <span class="special">&</span> <a name="idp88196576-bb"></a><span class="identifier">value_comp</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="identifier">value_compare</span> <span class="keyword">const</span> <span class="special">&</span> <a name="idm46563409934592-bb"></a><span class="identifier">value_comp</span><span class="special">(</span><span class="keyword">void</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Effect:</strong></span> Returns the value_compare object used by the priority queue </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idp88199616-bb"></a><span class="keyword">operator</span><span class="special"><</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idm46563409931760-bb"></a><span class="keyword">operator</span><span class="special"><</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Returns:</strong></span> Element-wise comparison of heap data structures</p> <p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idp88204768-bb"></a><span class="keyword">operator</span><span class="special">></span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idm46563409926784-bb"></a><span class="keyword">operator</span><span class="special">></span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Returns:</strong></span> Element-wise comparison of heap data structures</p> <p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idp14205488-bb"></a><span class="keyword">operator</span><span class="special">>=</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idm46563409921808-bb"></a><span class="keyword">operator</span><span class="special">>=</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Returns:</strong></span> Element-wise comparison of heap data structures</p> <p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idp14210640-bb"></a><span class="keyword">operator</span><span class="special"><=</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> +<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idm46563409916832-bb"></a><span class="keyword">operator</span><span class="special"><=</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> <p><span class="bold"><strong>Returns:</strong></span> Element-wise comparison of heap data structures</p> <p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> -<p> - </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idp14215792-bb"></a><span class="keyword">operator</span><span class="special">==</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> -<p>Equivalent comparison <span class="bold"><strong>Returns:</strong></span> True, if both heap data structures are equivalent. </p> -<p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> -<p> - </p> +<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idm46563409911856-bb"></a><span class="keyword">operator</span><span class="special">==</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre>Equivalent comparison <span class="bold"><strong>Returns:</strong></span> True, if both heap data structures are equivalent. <p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> </li> <li class="listitem"> -<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idp14221104-bb"></a><span class="keyword">operator</span><span class="special">!=</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre> -<p>Equivalent comparison <span class="bold"><strong>Returns:</strong></span> True, if both heap data structures are not equivalent. </p> -<p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> -<p> - </p> +<pre class="literallayout"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> HeapType<span class="special">></span> <span class="keyword">bool</span> <a name="idm46563409906720-bb"></a><span class="keyword">operator</span><span class="special">!=</span><span class="special">(</span><span class="identifier">HeapType</span> <span class="keyword">const</span> <span class="special">&</span> rhs<span class="special">)</span> <span class="keyword">const</span><span class="special">;</span></pre>Equivalent comparison <span class="bold"><strong>Returns:</strong></span> True, if both heap data structures are not equivalent. <p><span class="bold"><strong>Requirement:</strong></span> the <code class="computeroutput">value_compare</code> object of both heaps must match. </p> </li> </ol></div> </div> <div class="refsect2"> -<a name="idp143831520"></a><h3> -<a name="idp66129120-bb"></a><code class="computeroutput">fibonacci_heap</code> public static functions</h3> -<div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"> -<pre class="literallayout"><span class="keyword">static</span> <span class="identifier">handle_type</span> <a name="idp66129680-bb"></a><span class="identifier">s_handle_from_iterator</span><span class="special">(</span><span class="identifier">iterator</span> <span class="keyword">const</span> <span class="special">&</span> it<span class="special">)</span><span class="special">;</span></pre> -<p> - </p> -</li></ol></div> +<a name="idm45928042428256"></a><h3> +<a name="idm46563409881680-bb"></a><code class="computeroutput">fibonacci_heap</code> public static functions</h3> +<div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><pre class="literallayout"><span class="keyword">static</span> <span class="identifier">handle_type</span> <a name="idm46563409881120-bb"></a><span class="identifier">s_handle_from_iterator</span><span class="special">(</span><span class="identifier">iterator</span> <span class="keyword">const</span> <span class="special">&</span> it<span class="special">)</span><span class="special">;</span></pre></li></ol></div> </div> </div> </div> |