0

グラフ内の最短経路を見つけるためにダイクストラを使用しています。以前はstd::setを使用していましたが、ヒープのパフォーマンスが向上すると思います。しかし、d_ary_heapまたはpriority_queueの使用に問題があります。これは簡略化されたバージョンです。

#include <string>
#include <inttypes.h> // for uint32_t
#include <boost/heap/fibonacci_heap.hpp>
#include <boost/heap/binomial_heap.hpp>
#include <boost/heap/d_ary_heap.hpp>
#include <boost/heap/priority_queue.hpp>

using namespace std;

struct __attribute__ ((__packed__)) __attribute__((aligned(8)) Cmp {
    // Do *not* reorder the following two fields or comparison will break.
    const int32_t _id;
    const float _cost;

    Cmp(int32_t id, float cost) : _id(id), _cost(cost) {
        } 
};

struct Entry {
    Cmp _cmp;
    string str = "some variable";

    Entry(int32_t id, float cost) : _cmp(id, cost) {}
    Entry(Entry &&e) : _cmp(e._cmp._id, e._cmp._cost) {}
    Entry(const Entry &e) : _cmp(e._cmp._id, e._cmp._cost) {}
};

template<class T>
struct gt_entry: public binary_function <T, T, bool>
{
    bool operator()(const T &l, const T &r) const
    {
        return *(int64_t const *)&l > *(int64_t const *)&r;
    }
};


typedef boost::heap::d_ary_heap<
    Entry,
    boost::heap::arity<2>,
    boost::heap::compare<gt_entry<Entry> > > DHeap;

typedef boost::heap::binomial_heap<
    Entry,
    boost::heap::compare<gt_entry<Entry> > > BHeap;

typedef boost::heap::fibonacci_heap<
    Entry,
    boost::heap::compare<gt_entry<Entry> > > FHeap;


typedef boost::heap::priority_queue<
    Entry,
    boost::heap::compare<gt_entry<Entry> > > PQueue;



int main() {
    //DHeap h; // Doesn't compile
    //PQueue h; // Doesn't compile
    //BHeap h; // Works but slower than FHeap
    FHeap h; // Works but only  3% performance increase vs std::set

    h.push(Entry(1, 500.1));
    h.top();
    h.pop();

    return 0;
}

（比較を高速化するために_costと_idのパッケージを使用しています。興味がある場合はC ++ Optimize if / else条件を参照してください。）

これは関連するエラー行のようです。moveまたはcopyコンストラクターと関係があると思います。

.../move.h:177:7: error: use of deleted function ‘Entry& Entry::operator=(const Entry&)’
heaps.cpp:19:8: note: ‘Entry& Entry::operator=(const Entry&)’ is implicitly declared as deleted because ‘Entry’ declares a move constructor or move assignment operator

私はgcc4.6（-std = c ++ 0x）とブースト1.50を使用しています。

4

1 に答える 1

1

gccバージョンは、暗黙的に削除された関数のルールを正しく実装していません。このコードは、少なくともgcc4.7で機能します。

簡単な回避策は、ムーブ代入演算子Entry& operator=(Entry&&)も宣言することです。

C++11一般に、完全に最新ではないコンパイラで使用することはお勧めしません。

また、コンストラクターを移動し、コンストラクターをコピーすると、動作がおかしくなります。文字列をコピー/移動しません。あなたはそれを変えたいかもしれません。本当に必要な文字列が1つだけの場合は、それを静的メンバーにします。

于 2012-12-12T17:47:12.773 に答える