2

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 に依存します。

4

1 に答える 1

0

Node を宣言して転送し、インラインではない演算子を定義してみてください

// In Node.h

class Node;
struct CompareNode : public std::binary_function<Node*, Node*, bool>
{
    bool operator()(Node* lhs, Node* rhs) const;
};



typedef boost::heap::fibonacci_heap<
        Node*,
        boost::heap::compare<CompareNode> > FibonacciHeap;

typedef FibonacciHeap::handle_type HeapHandle;

class Node{


    HeapHandle handle_;
    int getFScore(); 
};


// In Node.cpp
#include "Node.h"

bool CompareNode::operator()(Node* lhs, Node* rhs) const   {
    return lhs->getFScore() > rhs->getFScore(); 
}
于 2012-11-28T23:26:11.467 に答える