I'm looking for a good data structure that can *maintain* its elements
sorted. Currently I'm trying
Boost.Heaphttp://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
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)
