使用自定义比较器在 C++ 中声明 priority_queue

declaring a priority_queue in c++ with a custom comparator

提问by Steven Morad

I'm trying to declare a priority_queue of nodes, using bool Compare(Node a, Node b)as the comparator function (which is outside the node class).

我正在尝试声明一个priority_queue of nodes,bool Compare(Node a, Node b)用作比较器函数（它在节点类之外）。

What I currently have is:

我目前拥有的是：

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

For some reason, I'm getting Error: "Compare" is not a type name

出于某种原因，我得到 Error: "Compare" is not a type name

Changing the declaration to priority_queue <Node, vector<Node>, bool Compare>

将声明更改为 priority_queue <Node, vector<Node>, bool Compare>

gives me Error: expected a '>'

给我 Error: expected a '>'

I've also tried:

我也试过：

priority_queue<Node, vector<Node>, Compare()> openSet;
priority_queue<Node, vector<Node>, bool Compare()> openSet;
priority_queue<Node, vector<Node>, Compare<Node, Node>> openSet; 

How should I correctly declare my priority_queue?

我应该如何正确声明我的priority_queue?

回答by awesoon

You should declare a class Compareand overload operator()for it like this:

您应该像这样声明一个类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;
}

Or, if you for some reasons can't make it as class, you could use std::functionfor it:

或者，如果您由于某些原因无法将其作为类，则可以使用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;
}

回答by Cris Luengo

The accepted answer makes you believe that you must use a class or a std::functionas comparator. This is not true! As cute_ptr's answershows, you can pass a function pointer to the constructor. However, the syntax to do so is much simpler than shown there:

接受的答案让您相信您必须使用类或 astd::function作为比较器。这不是真的！正如cute_ptr 的回答所示，您可以将函数指针传递给构造函数。但是，这样做的语法比此处显示的要简单得多：

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

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

That is, there is no need to explicitly encode the function's type, you can let the compiler do that for you using decltype.

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

This is very useful if the comparator is a lambda. You cannot specify the type of a lambda in any other way than using decltype. For example:

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

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

回答by Mic

The third template parameter must be a class who has operator()(Node,Node)overloaded. So you will have to create a class this way:

第三个模板参数必须是一个operator()(Node,Node)重载的类。因此，您必须以这种方式创建一个类：

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

And then you will use this class as the third template parameter like this:

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

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

回答by cute_ptr

Answering your question directly:

直接回答你的问题：

I'm trying to declare a priority_queueof nodes, using bool Compare(Node a, Node b) as the comparator function

What I currently have is:

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

For some reason, I'm getting Error:

"Compare" is not a type name

我正在尝试声明一个priority_queue节点，使用bool Compare(Node a, Node b) as the comparator function

我目前拥有的是：

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

出于某种原因，我收到错误：

"Compare" is not a type name

The compiler is telling you exactly what's wrong: Compareis not a type name, but an instance of a function that takes two Nodesand returns a bool.
What you need is to specify the function pointer type:
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

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

回答by bornfree

One can also use a lambda function.

还可以使用 lambda 函数。

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

回答by Canhua Li

prefer struct, and it's what std::greater do

更喜欢结构，这就是 std::greater 所做的

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