1

要素のソートを維持できる優れたデータ構造を探しています。現在、Boost.Heapを試しています。

データ構造を整然とトラバースし、何らかのプロパティに基づいて要素に到達したら、その優先度を更新する必要があることがよくあります。Boost.Heap 優先度キューは、順序付けされた反復子と順序付けられていない反復子を提供します。要素の更新はノード ハンドルを介して発生します。ハンドルは通常の順序付けされていないイテレータから取得できますが、次の例のように順序付けられたイテレータから直接取得することはできません。

#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;
    });
}

キューを整然とトラバースし、トラバーサル内の要素を更新するにはどうすればよいですか?

更新後にトラバーサルを残すことに注意してください。

（そのような目的のための代替ライブラリの提案は大歓迎です）

4

2 に答える 2

1

より良い代替手段が見つからない場合は、後で使用できるように、対応する各要素内にハンドルを保存する必要があります (c++1y コード):

#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;
    });
}
于 2013-02-27T04:35:47.303 に答える
0

あなたの要件は私にはあまり明確ではありません。しかし、std::multimap や std::multiset はどうでしょうか? 更新操作は O(log n) です。トラバーサルは O(n) ( BST トラバーサル) であるべきだと思いますが、標準の C++ リファレンス (cppreference.com、cplusplus.com) には記載されていません。boost::heap トラバーサルは償却された O(n log n)のように見えます。

于 2013-03-01T08:01:02.343 に答える