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);
    }

 /****/
};

プッシュ関数は、handle_type を返すフィボナッチ ヒープで使用する方法です。しかし、この場合、何を返すべきか理解できません( 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_ttypedefed を次のように返すことになっています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 に答える