declaring a priority queue in c with a custom comparator

Question

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 lt Node  vector lt Node gt   Compare gt  openSet    For some reason  I m getting Error   Compare  is not a type name  Changing the declaration to priority queue  lt Node  vector lt Node gt   bool Compare gt   gives me Error  expected a   gt    I ve also tried   priority queue lt Node  vector lt Node gt   Compare   gt  openSet  priority queue lt Node  vector lt Node gt   bool Compare   gt  openSet  priority queue lt Node  vector lt Node gt   Compare lt Node  Node gt  gt  openSet     How should I correctly declare my priority queue

User · Answer

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);

User · Answer

Answering your question directly      I m trying to declare a priority queue of nodes  using bool Compare Node a  Node b  as the comparator function      What I currently have is   priority queue lt Node  vector lt Node gt   Compare gt  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 lt Node  std  vector lt Node gt   bool     Node  Node  gt  openSet Compare

User · Answer

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 lt Node  vector lt Node gt   ComparisonClass gt  q

User · Answer

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 lt Foo  std  vector lt Foo gt   Compare gt  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 lt Foo  std  vector lt Foo gt   std  function lt bool Foo  Foo  gt  gt  pq Compare       return 0

User · Answer

In case this helps anyone   static bool myFunction Node amp  p1  Node amp  p2     priority queue  lt Node  vector lt Node gt   function lt bool Node amp   Node amp   gt  gt  pq1 myFunction

User · Answer

prefer struct  and it s what std  greater do  struct Compare     bool operator   Node const amp   Node  amp

User · Answer

You have to define the compare first  There are 3 ways to do that   use class use struct  which is same as class  use lambda function   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 amp  a Node amp  b     overloading both operators            return a w  lt  b w     if you want increasing order  i e increasing for minPQ        return a w  gt  b w    if you want reverse of default order  i e decreasing for minPQ           Calling code  priority queue lt Node vector lt Node gt  compare gt  pq

User · Answer

One can also use a lambda function   auto Compare      Node  amp a  Node  amp b      compare    std  priority queue lt Node  std  vector lt Node gt   decltype Compare  gt  openset Compare

[c++] declaring a priority_queue in c++ with a custom comparator

Examples related to c++

Examples related to std

Examples related to priority-queue