boost::fibonacci_heap: 句柄的嵌套定义与比较器重新定义的循环定义错误

Question

Boost 文档和之前的堆栈溢出都给出了如何定义自定义比较器函数的工作示例，以及如何在 boost 堆的节点类型中包含句柄。但是，当我结合这两个功能（自定义比较函数和节点类型中的句柄）时，我收到错误报告 '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

除了预定义 Node 和 compare_Node 的两个结构之外，我不确定在仍将句柄作为 Node 结构中的成员安全地持有时解决循环问题。

#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;
}

Answer 1

仅通过 operator() 的声明定义 compare_Node。指向 Node 的指针不需要 Node 定义。在Node定义后，可以添加operator()的body:

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: 句柄的嵌套定义与比较器重新定义的循环定义错误

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

c++

boost

fibonacci-heap