使用自定义比较器在 c + + 中声明一个 first_queue

小开

最佳答案

注意: 您可能还需要检查其他答案，特别是使用 dectype 和 lambda 的答案

您应该像下面这样声明一个类 Compare并重载 operator():

class Foo
{


};


class Compare
{
public:
bool operator() (Foo, Foo)
{
return true;
}
};


int main()
{
std::priority_queue<Foo, std::vector<Foo>, Compare> pq;
return 0;
}

或者，如果由于某些原因无法将其作为类使用，可以使用 std::function:

class Foo
{


};


bool Compare(Foo, Foo)
{
return true;
}


int main()
{
std::priority_queue<Foo, std::vector<Foo>, std::function<bool(Foo, Foo)>> pq(Compare);
return 0;
}

小开

第三个模板参数必须是重载了 operator()(Node,Node)的类。所以你必须这样创建一个类:

class ComparisonClass {
public:
bool operator() (Node, Node) {
//comparison code here
}
};

然后您将使用这个类作为第三个模板参数，如下所示:

priority_queue<Node, vector<Node>, ComparisonClass> q;

小开

直接回答你的问题:

我尝试使用 bool Compare(Node a, Node b) as the comparator function声明节点的 priority_queue

我现在拥有的是:
priority_queue<Node, vector<Node>, Compare> openSet;
出于某种原因，我得到了错误:
"Compare" is not a type name

编译器正在准确地告诉您出了什么问题: Compare不是一个类型名称，而是一个函数的实例，它接受两个 Nodes并返回一个 bool。
你需要指定的是函数指针类型:
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

小开

接受的答案显示了如何使用类或 std::function作为比较器。我们也可以通过一个函数指针，就像可爱的回答已经展示的那样。然而，这样做的语法比这里显示的要简单得多:

class Node;
bool Compare(Node a, Node b);


std::priority_queue<Node, std::vector<Node>, decltype(&Compare)> openSet(Compare);

也就是说，不需要对函数的类型进行显式编码，可以让编译器使用 decltype为您进行编码。

如果比较器是 lambda，这非常有用。除了使用 decltype之外，不能以其他任何方式指定 lambda 的类型。例如:

auto compare = [](Node a, Node b) { return a.foo < b.foo; }
std::priority_queue<Node, std::vector<Node>, decltype(compare)> openSet(compare);

小开

还可以使用 lambda 函数。

auto Compare = [](Node &a, Node &b) { //compare };
std::priority_queue<Node, std::vector<Node>, decltype(Compare)> openset(Compare);

小开

更喜欢 struct，而这正是 std: : more 所做的

struct Compare {
bool operator()(Node const&, Node &) {}
}

小开

以防这对任何人有帮助:

static bool myFunction(Node& p1, Node& p2) {}
priority_queue <Node, vector<Node>, function<bool(Node&, Node&)>> pq1(myFunction);

小开

你必须首先定义比较。有三种方法可以做到这一点:

使用类
使用 struct (与 class 相同)
使用 lambda 函数。

使用 class/struct 很容易，因为很容易声明，只需在正在执行的代码之上编写这行代码

struct compare{
public:
bool operator()(Node& a,Node& b) // overloading both operators
{
return a.w < b.w: // if you want increasing order;(i.e increasing for minPQ)
return a.w > b.w // if you want reverse of default order;(i.e decreasing for minPQ)
}
};

通话代码:

priority_queue<Node,vector<Node>,compare> pq;

小开

使用最新的 c + + 标准，您实际上可以为比较器声明一个 lambda 函数，这将使代码更加简洁。下面是一个示例代码:

#include <queue>


class Foo
{
public:
int i;
};




int main()
{
auto comparator = [](const Foo& a, const Foo& b) {
return a.i > b.i;
};


std::priority_queue<Foo, std::vector<Foo>, decltype(comparator)>  pq(comparator);
return 0;
}

小开

在优先级队列中，有一个预定义的布尔函数“运算符 < ()”，尝试按照您的要求重载这个函数。

bool operator<(const Node& x,const Node& y){
return x.data>y.data;
}


priority_queue<Node> min_heap;

小开

在 struct的帮助下，我们也可以做到这一点。

struct myCompare{
bool operator()(Node &a, Node &b){
// Your own custom logic to compare the two nodes and return a boolean value.
}
}


priority_queue<Node, vector<Node>, myCompare> openSet;