Как использовать Boost d_ary_heap?

Question

Как использовать Boost d_ary_heap?

Я пытаюсь использовать Boost d_ary_heap, но не могу понять, как получить дескриптор для толкаемого элемента. В моем случае мне потребуется обновить значение на более поздней итерации, поэтому мне нужен этот дескриптор. Я смог сделать это с кучей Фибоначчи, но в этом случае это выглядит намного сложнее.

Это то, что я до сих пор:

struct compare_cells_d_ary {
inline bool operator()
(const myType * c1 , const myType * c2) const {

return c1->getValue() > c2->getValue(); // I want a min heap.
}
};class MyHeap {

typedef typename boost::heap::d_ary_heap<const myType *, boost::heap::mutable_<true>, boost::heap::arity<2>, boost::heap::compare<compare_cells_d_ary>>::handle_type handle_t;

protected:
boost::heap::d_ary_heap<const myType *, boost::heap::arity<2>, boost::heap::mutable_<true>, boost::heap::compare<compare_cells_d_ary>> heap_;
std::vector<handle_t> handles_; // I store the handles in an specific order.

public:
/****/
void push (const myType * c) {
handles_[c->getIndex()] = heap_.push(c);
}

/****/
};

Функция push — это то, как я использую ее в куче Фибоначчи, которая возвращает тип handle_type. Но в этом случае я не могу понять, что он должен вернуть (http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/d_ary_heap.html#idp52218904-bb)

Любая помощь в том, как получить ручку при нажатии, приветствуется! Благодарю.

1

binary-heap boost c++c++11

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Так как вы объявили свою кучу изменяемой, push операция должна вернуть handle_t вы определили как handle_type:

mpl::if_c< is_mutable, handle_type, void >::type push(value_type const & v);

В отношении получения дескриптора, ваш код в порядке. Чтобы немного упростить, чтобы было понятнее:

void push (const myType * c) {
handle_t handle = heap_.push(c);
handles_[c->getIndex()] = handle;
}

Как примечание: у вас должна быть typedef для кучи, а не повторять ее в объявлениях, и typename является излишним (по крайней мере, во фрагменте, который вы разместили в вопросе.)

1