解决模板中的循环依赖关系

Question

我正在尝试使用Boost实现一个名为Node的类的斐波那契指针堆。

typedef boost::heap::fibonacci_heap<Node*> FibonacciHeap;
typedef FibonacciHeap::handle_type HeapHandle;

目前为止，一切都好。但我也想在 Node 类中存储堆元素的句柄。Boost特别提到"句柄可以存储在value_type内"。提高但是，我无法在类中定义比较运算符，因为堆从不使用它，只比较指针值。

但是定义一个作为模板参数传递给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。

Answer 1

尝试转发声明 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(); 
}