declaring a priority_queue in c++ with a custom comparator
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
?
Solution 1:
Note - You may also want to check other answers, especially the one with decltype and lambda
You should declare a class Compare
and overload operator()
for it like this:
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::function
for it:
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;
}
Solution 2:
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);