Boost を使用して Node というクラスのポインターのフィボナッチ ヒープを実装しようとしています。
typedef boost::heap::fibonacci_heap<Node*> FibonacciHeap;
typedef FibonacciHeap::handle_type HeapHandle;
ここまでは順調ですね。しかし、ヒープ要素のハンドルも Node クラスに格納したいと考えています。Boostは、「ハンドルはvalue_type内に格納できる」と具体的に述べています。Boost ただし、クラス内で比較演算子を定義することはできません。ヒープはそれを使用せず、ポインター値のみを比較するためです。
ただし、テンプレート パラメーターとして fibonacci_heap に渡される比較構造体を定義すると、循環依存が導入されます。
struct CompareNode : public std::binary_function<Node*, Node*, bool>
{
bool operator()(Node* lhs, Node* rhs) const {
return lhs->getFScore() > rhs->getFScore();
}
};
typedef boost::heap::fibonacci_heap<
Node*,
boost::heap::compare<CompareNode> > FibonacciHeap;
Node は HeapHandle に依存し、HeapHandle は Node に依存します。