Resolve cyclic dependency in template

Question

I'm trying to implement a Fibonacci heap of pointers of a class called Node using Boost.

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

So far, so good. But I also want to store handles for the heap elements in the Node class. Boost specifically mentions that "handles can be stored inside the value_type". Boost However, I can't define a comparison operator inside the class, because the heap never uses it and only compares the pointer values.

But defining a comparison struct which is passed as a template parameter to fibonacci_heap introduces a cyclic dependency:

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 depends on HeapHandle and HeapHandle depends on Node.

Answer 1

Try forwarding declaring Node and then defining the operator not inline

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