在boost中定义fibonacci堆的比较函数 [英] Defining compare function for fibonacci heap in boost
问题描述
我需要在我的项目中使用Fibonacci堆,我试图使用它从boost库。但我不知道如何为任意数据类型设置用户定义的比较函数。我需要为struct node构造一个最小堆,定义如下:
I need to use Fibonacci heap in my project and I am trying to use it from boost library. But I cannot figure out how to set up a user defined compare function for arbitrary data type. I need to construct a min heap for struct node defined as follows:
struct node
{
int id;
int weight;
struct node* next;
/* dist is a global array of integers */
bool operator > (struct node b) //Boost generates a Max-heap. What I need is a min-heap.
{return dist[id] < dist[b.id] ? 1:0 ;} //That's why "<" is used for "operator >".
bool operator < (struct node b)
{return dist[id] > dist[b.id] ? 1:0 ;}
bool operator >=(struct node b)
{return dist[id] <= dist[b.id] ? 1:0 ;}
bool operator <=(struct node b)
{return dist[id] >= dist[b.id] ? 1:0 ;}
node()
{
id=0;
weight=0;
next=NULL;
}
};
我查找了文档,还有一个比较类。但它没有包含任何元素。请告诉我如何设置一个用户定义的比较功能。
提前谢谢。
I looked up the documentation and there was a compare class. But it did not contain any element. Please tell me how to set up a user defined compare function. Thank you in advance.
推荐答案
fibonacci_heap
比较函子,其实际上是具有函数调用操作符的 struct
或 class
code>运算符()。我将简化你的节点
结构,但你应该能够使用这个稍作修改:
fibonacci_heap
takes a comparison functor, which is effectively a struct
or class
with a function call operator - operator()
. I'm going to simplify your node
struct, but you should be able to use this with minor modifications:
struct node
{
int id;
node(int i)
: id(i)
{ }
};
现在,我们需要定义一个比较 node
s。这将有一个运算符()
需要2个节点通过const引用,并返回 bool
:
Now, we need to define a class that compares node
s. This will have an operator()
that takes 2 nodes by const reference, and return a bool
:
struct compare_node
{
bool operator()(const node& n1, const node& n2) const
{
return n1.id > n2.id;
}
};
我们可以如下声明我们的堆:
We can then declare our heap as follows:
boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>> heap;
完整示例:
#include <boost/heap/fibonacci_heap.hpp>
#include <iostream>
struct node
{
int id;
node(int i)
: id(i)
{ }
};
struct compare_node
{
bool operator()(const node& n1, const node& n2) const
{
return n1.id > n2.id;
}
};
int main()
{
boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>> heap;
heap.push(node(3));
heap.push(node(2));
heap.push(node(1));
for(const node& n : heap) {
std::cout << n.id << "\n";
}
}
这篇关于在boost中定义fibonacci堆的比较函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!