Ошибка компиляции Boost d_ary_heap/priority_queue: удаленная функция

Я использую Dijkstra для поиска кратчайшего пути в графе. Раньше я использовал 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.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

Я использую gcc 4.6 (-std=c++0x) и boost 1.50.


c++ queue c++11 dijkstra heap
person Heye    schedule 12.12.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваша версия gcc неправильно реализует правила для неявно удаленных функций. Код работает как минимум с gcc 4.7.

Быстрый обходной путь — также объявить оператор присваивания перемещения Entry& operator=(Entry&&).

В общем, я бы не рекомендовал использовать C++11 с компилятором, который не совсем актуален.

Также: вы перемещаете конструктор, а конструктор копирования ведет себя странно. Они не копируют/перемещают строку. Возможно, вы захотите изменить это. Если вам действительно нужна только одна строка, сделайте ее статическим членом.

person pmr    schedule 12.12.2012
comment
Да, это сработало, спасибо! Но мне пришлось сделать это так: Entry operator=(Entry&&). Я компилирую с 4.72, но в конечном итоге код должен компилироваться под 4.6... Я просто вставил строку, чтобы показать, что эта структура содержит больше переменных (также строки-контейнеры и прочее) на самом деле. Это просто пример, где произошла ошибка. - person Heye; 13.12.2012