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).
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
Changing the declaration to priority_queue <Node, vector<Node>, bool Compare>
gives me 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
?
This question is related to
c++
std
priority-queue
prefer struct, and it's what std::greater do
struct Compare {
bool operator()(Node const&, Node &) {}
}
The accepted answer makes you believe that you must use a class or a std::function
as comparator. This is not true! As cute_ptr's answer shows, you can pass a function pointer to the constructor. However, the syntax to do so is much simpler than shown there:
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
.
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:
auto compare = [](Node a, Node b) { return a.foo < b.foo; }
std::priority_queue<Node, std::vector<Node>, decltype(compare)> openSet(compare);
One can also use a lambda function.
auto Compare = [](Node &a, Node &b) { //compare };
std::priority_queue<Node, std::vector<Node>, decltype(Compare)> openset(Compare);
You have to define the compare first. There are 3 ways to do that:
It's easy to use class/struct because easy to declare just write this line of code above your executing code
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)
}
};
Calling code:
priority_queue<Node,vector<Node>,compare> pq;
Answering your question directly:
I'm trying to declare a
priority_queue
of nodes, usingbool 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
The compiler is telling you exactly what's wrong: Compare
is not a type name, but an instance of a function that takes two Nodes
and 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)
The third template parameter must be a class who has operator()(Node,Node)
overloaded.
So you will have to create a class this way:
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;
In case this helps anyone :
static bool myFunction(Node& p1, Node& p2) {}
priority_queue <Node, vector<Node>, function<bool(Node&, Node&)>> pq1(myFunction);
Source: Stackoverflow.com