<div dir="ltr"><p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,&#39;Liberation Sans&#39;,&#39;DejaVu Sans&#39;,sans-serif;line-height:18px">
I&#39;m looking for a good data structure that can�<em style="margin:0px;padding:0px;border:0px;vertical-align:baseline;background-color:transparent">maintain</em>�its elements sorted. Currently I&#39;m trying�<a href="http://www.boost.org/doc/libs/1_53_0/doc/html/heap.html" rel="nofollow" style="margin:0px;padding:0px;border:0px;vertical-align:baseline;background-color:transparent;color:rgb(74,107,130);text-decoration:none">Boost.Heap</a>.</p>
<p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,&#39;Liberation Sans&#39;,&#39;DejaVu Sans&#39;,sans-serif;line-height:18px">
I frequently need to orderly traverse the data structure, find a element based on some property and update its priority when it matches. Boost.Heap priority queues provide ordered and non-ordered iterators. Element updates occurs through a element handle, a handle can be obtained from a ordinary non-ordered iterator, but not directly from a ordered one as in the following example:</p>
<div><pre id="vimCodeElement" style="font-size:13px;font-family:consolas,monospace;color:rgb(211,211,211);background-color:rgb(32,32,32)"><span class="" style="font-size:1em;color:rgb(250,244,198)">#include </span><span class="" style="font-size:1em;color:rgb(177,214,49);font-style:italic">&lt;iostream&gt;</span>
<span class="" style="font-size:1em;color:rgb(250,244,198)">#include </span><span class="" style="font-size:1em;color:rgb(177,214,49);font-style:italic">&lt;algorithm&gt;</span>
<span class="" style="font-size:1em;color:rgb(250,244,198)">#include </span><span class="" style="font-size:1em;color:rgb(177,214,49);font-style:italic">&lt;boost/heap/fibonacci_heap.hpp&gt;</span>

<span class="" style="font-size:1em;color:rgb(126,138,162)">using</span> <span class="" style="font-size:1em;color:rgb(126,138,162)">namespace</span> boost<span class="" style="font-size:1em;color:rgb(160,32,240)">::</span>heap<span class="" style="font-size:1em;color:rgb(160,32,240)">;</span>

<span class="" style="font-size:1em;color:rgb(126,138,162)">int</span> main<span class="" style="font-size:1em;color:rgb(0,191,255)">()</span>
<span class="" style="font-size:1em;color:rgb(0,191,255)">{</span>
    fibonacci_heap<span class="" style="font-size:1em;color:rgb(127,255,0)">&lt;</span><span class="" style="font-size:1em;color:rgb(126,138,162)">int</span><span class="" style="font-size:1em;color:rgb(127,255,0)">&gt;</span> fib_heap<span class="" style="font-size:1em;color:rgb(0,191,255)">;</span>

    fib_heap<span class="" style="font-size:1em;color:rgb(0,191,255)">.</span>push<span class="" style="font-size:1em;color:rgb(127,255,0)">(</span><span class="" style="font-size:1em;color:rgb(255,152,0)">1</span><span class="" style="font-size:1em;color:rgb(127,255,0)">)</span><span class="" style="font-size:1em;color:rgb(0,191,255)">;</span>
    fib_heap<span class="" style="font-size:1em;color:rgb(0,191,255)">.</span>push<span class="" style="font-size:1em;color:rgb(127,255,0)">(</span><span class="" style="font-size:1em;color:rgb(255,152,0)">2</span><span class="" style="font-size:1em;color:rgb(127,255,0)">)</span><span class="" style="font-size:1em;color:rgb(0,191,255)">;</span>
    fib_heap<span class="" style="font-size:1em;color:rgb(0,191,255)">.</span>push<span class="" style="font-size:1em;color:rgb(127,255,0)">(</span><span class="" style="font-size:1em;color:rgb(255,152,0)">3</span><span class="" style="font-size:1em;color:rgb(127,255,0)">)</span><span class="" style="font-size:1em;color:rgb(0,191,255)">;</span>

    <span class="" style="font-size:1em;color:rgb(126,138,162)">for</span><span class="" style="font-size:1em;color:rgb(127,255,0)">(</span><span class="" style="font-size:1em;color:rgb(126,138,162)">auto</span> i <span class="" style="font-size:1em;color:rgb(127,255,0)">=</span> fib_heap<span class="" style="font-size:1em;color:rgb(127,255,0)">.</span>ordered_begin<span class="" style="font-size:1em;color:rgb(255,255,0)">()</span><span class="" style="font-size:1em;color:rgb(127,255,0)">;</span> i <span class="" style="font-size:1em;color:rgb(127,255,0)">!=</span> fib_heap<span class="" style="font-size:1em;color:rgb(127,255,0)">.</span>ordered_end<span class="" style="font-size:1em;color:rgb(255,255,0)">()</span><span class="" style="font-size:1em;color:rgb(127,255,0)">;</span> <span class="" style="font-size:1em;color:rgb(127,255,0)">++</span>i<span class="" style="font-size:1em;color:rgb(127,255,0)">)</span>
    <span class="" style="font-size:1em;color:rgb(127,255,0)">{</span>
        <span class="" style="font-size:1em;color:rgb(126,138,162)">auto</span> h <span class="" style="font-size:1em;color:rgb(127,255,0)">=</span> fibonacci_heap<span class="" style="font-size:1em;color:rgb(255,255,0)">&lt;</span><span class="" style="font-size:1em;color:rgb(126,138,162)">int</span><span class="" style="font-size:1em;color:rgb(255,255,0)">&gt;</span><span class="" style="font-size:1em;color:rgb(127,255,0)">::</span>s_handle_from_iterator<span class="" style="font-size:1em;color:rgb(255,255,0)">(</span>i<span class="" style="font-size:1em;color:rgb(255,255,0)">)</span><span class="" style="font-size:1em;color:rgb(127,255,0)">;</span>
        <span class="" style="font-size:1em;color:rgb(126,138,162)">if</span><span class="" style="font-size:1em;color:rgb(255,255,0)">(</span><span class="" style="font-size:1em;color:rgb(255,255,0)">*</span>h <span class="" style="font-size:1em;color:rgb(255,255,0)">==</span> <span class="" style="font-size:1em;color:rgb(255,152,0)">3</span><span class="" style="font-size:1em;color:rgb(255,255,0)">)</span>
        <span class="" style="font-size:1em;color:rgb(255,255,0)">{</span>
            fib_heap<span class="" style="font-size:1em;color:rgb(255,255,0)">.</span>increase<span class="" style="font-size:1em;color:rgb(255,127,80)">(</span>h<span class="" style="font-size:1em;color:rgb(255,127,80)">,</span> <span class="" style="font-size:1em;color:rgb(255,127,80)">*</span>h <span class="" style="font-size:1em;color:rgb(255,127,80)">+</span> <span class="" style="font-size:1em;color:rgb(255,152,0)">2</span><span class="" style="font-size:1em;color:rgb(255,127,80)">)</span><span class="" style="font-size:1em;color:rgb(255,255,0)">;</span>
            <span class="" style="font-size:1em;color:rgb(126,138,162)">break</span><span class="" style="font-size:1em;color:rgb(255,255,0)">;</span>
        <span class="" style="font-size:1em;color:rgb(255,255,0)">}</span>
    <span class="" style="font-size:1em;color:rgb(127,255,0)">}</span>

    std<span class="" style="font-size:1em;color:rgb(0,191,255)">::</span>for_each<span class="" style="font-size:1em;color:rgb(127,255,0)">(</span>fib_heap<span class="" style="font-size:1em;color:rgb(127,255,0)">.</span>ordered_begin<span class="" style="font-size:1em;color:rgb(255,255,0)">()</span><span class="" style="font-size:1em;color:rgb(127,255,0)">,</span> fib_heap<span class="" style="font-size:1em;color:rgb(127,255,0)">.</span>ordered_end<span class="" style="font-size:1em;color:rgb(255,255,0)">()</span><span class="" style="font-size:1em;color:rgb(127,255,0)">,</span>
    <span class="" style="font-size:1em;color:rgb(255,255,0)">[](</span><span class="" style="font-size:1em;color:rgb(126,138,162)">const</span> <span class="" style="font-size:1em;color:rgb(126,138,162)">int</span> <span class="" style="font-size:1em;color:rgb(255,255,0)">&amp;</span>e<span class="" style="font-size:1em;color:rgb(255,255,0)">)</span>
    <span class="" style="font-size:1em;color:rgb(255,255,0)">{</span>
        std<span class="" style="font-size:1em;color:rgb(255,255,0)">::</span>cout <span class="" style="font-size:1em;color:rgb(255,255,0)">&lt;&lt;</span> e <span class="" style="font-size:1em;color:rgb(255,255,0)">&lt;&lt;</span> std<span class="" style="font-size:1em;color:rgb(255,255,0)">::</span>endl<span class="" style="font-size:1em;color:rgb(255,255,0)">;</span>
    <span class="" style="font-size:1em;color:rgb(255,255,0)">}</span><span class="" style="font-size:1em;color:rgb(127,255,0)">)</span><span class="" style="font-size:1em;color:rgb(0,191,255)">;</span>
<span class="" style="font-size:1em;color:rgb(0,191,255)">}</span></pre></div><div><div><span style="color:rgb(0,0,0);font-family:Arial,&#39;Liberation Sans&#39;,&#39;DejaVu Sans&#39;,sans-serif;font-size:14px;line-height:18px">How can I orderly traverse the queue and update an element in the traversal?</span><br>
</div></div><div><p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,&#39;Liberation Sans&#39;,&#39;DejaVu Sans&#39;,sans-serif;line-height:18px">
Note that I leave traversal after the update.</p><p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,&#39;Liberation Sans&#39;,&#39;DejaVu Sans&#39;,sans-serif;line-height:18px">
(Suggestions of alternative libraries for such purpose are welcome)</p></div></div>