如何有序地遍历一个Boost.Heap优先级队列和更新给定的元素？ [英] How to orderly traverse a Boost.Heap Priority Queue and update a given element?

问题描述

我在寻找一个好的数据结构，可以的维持整理的的元素。我目前正试图 Boost.Heap 。

I'm looking for a good data structure that can maintain its elements sorted. Currently I'm trying Boost.Heap.

我经常需要有序遍历所述数据结构并到达基于某些特性的元件时，更新其优先权。 Boost.Heap优先级队列提供有序和无序的迭代器。发生元件的更新通过节点手柄，把手可以从普通的非有序迭代来获得，但是从订购一个作为在下面的例子不直接

I frequently need to orderly traverse the data structure and when reaching an element based on some property, update its priority. Boost.Heap priority queues provide ordered and non-ordered iterators. Element updates occurs through a node 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)
    {
        // no viable conversion here
        auto h = fibonacci_heap<int>::s_handle_from_iterator(i);

        if(*h == 2) // dumb test
        {
            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)

推荐答案

如果我发现没有更好的选择，我需要保存每个对应的元素中的手柄供以后使用（C ++ 1Y code）：

If I find no better alternative, I'll need to save the handle inside each corresponding element for later usage (c++1y code):

#include <iostream>
#include <algorithm>
#include <boost/heap/fibonacci_heap.hpp>

using namespace boost::heap;

template<typename T>
struct heap_data
{
    typedef typename fibonacci_heap<heap_data>::handle_type handle_t;
    handle_t handle;
    T data;

    heap_data(const T &data_) : data(data_) {}

    bool operator<(heap_data const & rhs) const
    {
        return data < rhs.data;
    }
};

void setup_handle(fibonacci_heap<heap_data<int>>::handle_type &&handle)
{
    (*handle).handle = handle;
}

int main()
{
    fibonacci_heap<heap_data<int>> heap;

    setup_handle(heap.emplace(1));
    setup_handle(heap.emplace(2));
    setup_handle(heap.emplace(3));

    std::find_if(heap.ordered_begin(), heap.ordered_end(),
    [&heap](const heap_data<int> &e)
    {
        if(e.data == 2)
        {
            const_cast<heap_data<int> &>(e).data += 2;
            heap.increase(e.handle);
            return true;
        }
        return false;
    });

    std::for_each(heap.ordered_begin(), heap.ordered_end(),
    [](const heap_data<int> &e)
    {
        std::cout << e.data << std::endl;
    });
}

这篇关于如何有序地遍历一个Boost.Heap优先级队列和更新给定的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！