1

我正在尝试使用 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 函数是我在斐波那契堆中使用它的方式，它返回一个句柄类型。但在这种情况下，我无法理解它应该返回什么（http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/d_ary_heap.html#idp52218904-bb）

欢迎在推动时如何获得把手的任何帮助！谢谢。

4

1 回答 1

1

由于您将堆声明为可变的，因此该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是多余的（至少在您在问题中发布的片段中。）

于 2014-03-04T12:04:57.777 回答