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<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 shows how to use a class or a std::function as comparator. We can also pass a function pointer, as cute_ptr's answer already showed. 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);

Solution 3

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 {
public:
    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;

Solution 4

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

Solution 5

You have to define the compare first. There are 3 ways to do that:

1. use class
2. use struct (which is same as class)
3. 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& 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;

View more solutions

Comments

[Steven Morad]

Perfect, just what I was looking for. I never thought to make a separate class. Would the first example be considered better style?

[awesoon]

@StevenMorad, I prefer to use class with overloaded operator(), it looks simpler.

[Piyush]

@soon Why do we overload the operator () ? Is this linked to how priority_queues are implemented internally? overloading > or < makes sense intuitively, but () operator not so much

[awesoon]

@Piyush, the question is about passing a custom comparator to the pritority_queue. It is possible to overload operator< and use built-in std::less comparator, however, the bool Compare(Node a, Node b) declared outside of the class Node, according to the question.

[knezi]

The operator method must be public.

[Cris Luengo]

The third template does not need to be a class. It can be the type of a function.

[yuqli]

@Piyush the syntax of using () is about passing a function as a parameter to another function, not about the specific operators. This is also known as a functor. See this link: en.wikipedia.org/wiki/Function_object

[Apollys supports Monica]

This is fantastic, I wonder if there are any potential traps (issues) here. Would love to see this answer get more visibility and discussion.

[Cris Luengo]

@Apollys: I use this method regularly (usually Compare is a lambda, which is impossible to write a declaration for), I don't know of any traps.

[Eric Auld]

If you were to do this for a lambda function, where would you put the body of the lambda function? Would you store it in a variable f beforehand and then replace Compare with f?

[Cris Luengo]

@EricAuld: Yes, Compare can be a lambda function there, as in auto Compare = [](){};. But you need to use decltype(Compare), rather than decltype(&Compare).

[Amanda Wang]

Hi Chris, this is great, I was looking for some format to use with decltype for priority_queue and without declaring a class, you gave the perfect answer! Thanks!

[Amanda Wang]

This is exactly what I'm looking for to give a function in priority_queue declaration, thanks!

[Abhay Patil]

@awesoon would a struct work, or is it necessary to use class only?

[awesoon]

@AbhayPatil struct will work just fine. They're the same as classes in C++, the only difference is default access level - struct members are public by default.

[Benav]

According to cpluplus: This may be a function pointer or function object

[Rockstar5645]

I keep coming back to this answer, probably like 50 times now, I can never remember the syntax

[BitTickler]

The pretty and concise notation without a function object (decltype(&Compare)) compiled but produced a segmentation fault with Debian clang version 11.0.1-2 Target: x86_64-pc-linux-gnu. When I replaced it with a function object, it works. Compiler bug?!

[Cris Luengo]

@BitTickler: I would think that is highly unlikely to be a compiler bug. Changing one part of a program can bring to light bugs in other parts. I would start by building with the AdressSanitizer on, see if you can catch any out of bounds writes and so on. If that fails, try to create a minimal reproducible example. If you manage that, and the example is so simple that there is no way the error could be yours, then open a ticket at the clang project.

[BitTickler]

@CrisLuengo There is not a single pointer in my whole, quite short program. And from the Compare class I call the same compare function I wanted to use initially. If it is not a compiler bug, it could still be an implementation bug of the priority queue... But I will try to knock up some canonical example, which removes any doubt.

[BitTickler]

@CrisLuengo [gist.github.com/ruffianeo/55ebe9f921d4f057d979763afc248b23] - the canonical example.

[Cris Luengo]

@BitTickler: You need to include a pointer to the comparator function when you construct the queue: Seqs pq(char_range_compare);. The template arguments specify the function type (i.e. what parameters it takes and what type it returns), it doesn't specify an actual function to call. I don't know why this doesn't give a compile-time error. GCC also happily compiles your code without a warning, and produces the same seg fault. It's because there's an attempt to call a function at address 0x0000.

[Cris Luengo]

This was possible since C++11, definitely not the latest standard. Also, when you wrote this, there were already two answers showing how to use a lambda function in this way. Please make sure you add value when you write an answer.

[DzDev]

@Rockstar5645 Hhhh you killed me 😂😂😂

[Kargath]

I watched this, but I didn't understand why he said operator< is wrong. youtube.com/…

[vaeVictis]

@Rockstar5645 I wrote a reference program just to remember this syntax 😂