boost::fibonacci_heap: Nested define of handle with comparator redefined circular definition errors

Question

Boost documentation and previous stack overflow both give working examples of how to define custom comparator functions and include handle in the node type of a boost heap. However when I combine both of these features (a custom defined compare function and a handle within the node type) I get errors reporting invalid use of incomplete type of 'struct compare_Node'.

https://www.boost.org/doc/libs/1_63_0/doc/html/heap/concepts.html#heap.concepts.mutability

Using boost fibonacci_heap

Defining compare function for fibonacci heap in boost

Decrease operation in fibonacci heap, boost

Other than predefining both structs of Node and compare_Node I'm not sure to solve the circularity while still holding the handle's safely as a member within the Node struct.

#include <boost/heap/fibonacci_heap.hpp>

struct compare_Node; //predefine to avoid circular issues
struct Node; //predefine to avoid circular issues

using fib_heap = boost::heap::fibonacci_heap<struct Node*,
    boost::heap::compare<struct compare_Node>>;

// 6-byte struct total
struct Node {
    double value; 

    fib_heap::handle_type* handle; // orig
};

// override for min_heap
struct compare_Node
{
    bool operator() (struct Node* const n1, struct Node* const n2) const
    {
        return n1->value > n2->value;
    }
};

int main() {
    fib_heap heap;
    return 0;
}

score 0 · Accepted Answer · answered Jun 26 '19 at 08:13

Define compare_Node only with the declaration of operator(). Pointers to Node don't need Node definition. After Node definition, you can add the body of operator():

struct compare_Node
{
    bool operator() (struct Node* const n1, struct Node* const n2) const;
};

using fib_heap = boost::heap::fibonacci_heap<struct Node*,
    boost::heap::compare<struct compare_Node>>;

// 6-byte struct total
struct Node {
    double value; 

    fib_heap::handle_type* handle; // orig
};

bool compare_Node::operator() (struct Node* const n1, struct Node* const n2) const
{
        return n1->value > n2->value;
}

Online demo.

boost::fibonacci_heap: Nested define of handle with comparator redefined circular definition errors

1 Answers1