Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 878
Steven Morad Avatar asked Apr 19 '13 18:04

Steven Morad


People also ask

How does comparator work C++ priority queue?

priority_queue is categorized as a STL container adaptor. It is like a queue that keeps its element in sorted order. Instead of a strict FIFO ordering, the element at the head of the queue at any given time is the one with the highest priority.

Can we use comparator function in priority queue C++?

You may have often come to a situation when you need to use a priority queue, but your datatype is something else that can't be compared by default (using '<' operator what is used by default). In such cases, we need to declare our comparator function. We can use the lambda function for that.

How does custom comparator work?

Custom Comparator are used to compare the objects of user-defined classes. The above comparator function comp() take two pair of objects at a time and return true if data members of the two operators are the same. There can be any condition as per the need of the problem in the comparator function.


1 Answers

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; } 
like image 111
awesoon Avatar answered Oct 15 '22 11:10

awesoon