Re: [Boost-users] [heap] How to orderly traverse a priority queue and update a given element?

Subject: Re: [Boost-users] [heap] How to orderly traverse a priority queue and update a given element?
From: Francisco Lopes (francisco.mailing.lists_at_[hidden])
Date: 2013-02-26 22:04:18

Here's a related stackoverflow question: http://stackoverflow.com/q/15102406
.

Note that at s_handle_from_iterator there's a "no viable conversion", it's
to be used with ordinary iterators obtained from fib_heap.begin().

2013/2/26 Francisco Lopes <francisco.mailing.lists_at_[hidden]>

> I'm looking for a good data structure that can *maintain* its elements
> sorted. Currently I'm trying Boost.Heap<http://www.boost.org/doc/libs/1_53_0/doc/html/heap.html>
> .
>
> 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:
>
> #include <iostream>#include <algorithm>#include <boost/heap/fibonacci_heap.hpp>
> using namespace boost::heap;
> int main(){
>     fibonacci_heap<int> fib_heap;
>
>     fib_heap.push(1);
>     fib_heap.push(2);
>     fib_heap.push(3);
>
>     for(auto i = fib_heap.ordered_begin(); i != fib_heap.ordered_end(); ++i)
>     {
>         auto h = fibonacci_heap<int>::s_handle_from_iterator(i);
>         if(*h == 3)
>         {
>             fib_heap.increase(h, *h + 2);
>             break;
>         }
>     }
>
>     std::for_each(fib_heap.ordered_begin(), fib_heap.ordered_end(),
>     [](const int &e)
>     {
>         std::cout << e << std::endl;
>     });}
>
> How can I orderly traverse the queue and update an element in the
> traversal?
>
> Note that I leave traversal after the update.
>
> (Suggestions of alternative libraries for such purpose are welcome)
>