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

Question

我试图声明一个priority_queue of nodes,bool Compare(Node a, Node b)用作比较器函数(在节点类之外).

我现在拥有的是:

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

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

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

给我 Error: expected a '>'

我也尝试过:

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

我应该如何正确地宣布我的priority_queue？

Answer 1

你应该为它声明一个类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;
}

Answer 2

接受的答案让你相信你必须使用一个类或一个std::function比较器.这不是真的!cute_ptr的答案显示了如何将函数传递给构造函数,但有一种更简单的方法:

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

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

也就是说,不需要显式编码函数的类型,您可以让编译器为您执行此操作.

Answer 3

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

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

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

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

Answer 4

您必须先定义比较。有3种方法可以做到这一点：

1. 使用类
2. 使用结构（与类相同）
3. 使用 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;

Answer 5

直接回答你的问题:

我正在尝试声明一个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

编译器正在告诉你究竟出了什么问题:Compare不是类型名称,而是一个带两个Nodes并返回a 的函数实例bool.
你需要的是指定函数指针类型:
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

Answer 6

还可以使用 lambda 函数。

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

Answer 7

如果这对任何人有帮助：

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