Как использовать 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)

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


c++ boost c++11 binary-heap
person Javi    schedule 04.03.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Поскольку вы объявили свою кучу изменяемой, операция 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 является излишним (по крайней мере, во фрагменте, который вы разместили в вопросе).

person mockinterface    schedule 04.03.2014
comment
Спасибо, теперь компилируется. Я должен сказать, что я уже пробовал это, но, возможно, это было из-за имени типа, которое вы упомянули, или чего-то еще, потому что он жаловался на то, что push вернул пустоту, и я не игнорировал возврат (??). Спасибо за совет, сейчас проверю, работает ли. Однако я не понимаю, почему имя типа лишнее (чем больше я читаю об этом, тем больше запутываюсь). - person Javi; 04.03.2014
comment
Кроме того, для кучи Фибонначи push возвращает handle_type, однако все это: mpl::if_c‹ is_mutable, handle_type, void ›::type что это такое? Потому что в моем коде я делаю это равным моему handle_t - person Javi; 04.03.2014
comment
Имя типа является излишним, потому что здесь нет типа шаблона, который может быть неоднозначным для разрешения компилятором. Что касается определения типа, то оно примерно интерпретируется как: если куча была определена как изменяемая, т.е. с boost::heap::mutable_<true>, иметь handle_type в качестве возвращаемого типа push, в противном случае (если куча неизменяемая) иметь push возвращать void. - person mockinterface; 04.03.2014
comment
Вот хорошее объяснение относительно typename: stackoverflow.com/a/8584507/3099074 - person mockinterface; 04.03.2014