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?

Partner

Answer 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;
}

Lavelle

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

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

@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 – Sigismond

@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. – Lavelle

@Sigismond 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 – Yance

@Lavelle would a struct work, or is it necessary to use class only? – Badenpowell

@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. – Lavelle

NOTE: You should pass Compare to the constructor of priority_queue in the second example. – Megaspore

@Lavelle in the first example, why is it required to declare another class Compare. can we overload the operator in the Foo class? – Abuttal

@Lavelle i get an error doing so. can you please help? ideone.com/VVHb1L – Abuttal

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

Bathsheeb

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

@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. – Bathsheeb

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? – Dombrowski

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

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?! – Joanne

@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. – Bathsheeb

@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. – Joanne

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

@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. – Bathsheeb

Answer 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 obj1, Node obj2) {
        //comparison code here
    }
};

And then you will use this class as the third template parameter like this:

priority_queue<Node, vector<Node>, ComparisonClass> q;

Butylene

The operator method must be public. – Fortdefrance

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

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

@Butylene can we define the operator() in the Node class itself? – Abuttal

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

Autostrada

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

Biggerstaff

Answer 6

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

Fulmar

Answer 7

In case this helps anyone :

static bool myFunction(Node& p1, Node& p2) {}
priority_queue <Node, vector<Node>, function<bool(Node&, Node&)>> pq1(myFunction);

Intitule

Answer 8

In the priority queue, there is a predefined boolean function "operator<()", try to overload this function as per your requirement.

bool operator<(const Node& x,const Node& y){
    return x.data>y.data;
}

priority_queue<Node> min_heap;

Grandsire

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

@Vladamar The video says that for some use cases, the sorting does not relate to a “less than” comparison. Defining < to impose your custom sorting would be confusing in this case, because it wouldn’t really be a “less than” comparison. < would return true if one object comes before the other in the sorting, rather than if one is smaller than the other. – Bathsheeb

Answer 9

Since C++ 20, we can more concisely use a lambda for the comparator inline, without needing to assign it to a separate variable. This is because lambdas without any captures are now default constructible.

For example:

std::priority_queue<Node, std::vector<Node>, 
                       decltype([](Node& a, Node& b){return a.x < b.x;})> pq;

Note that we did not need to pass the lambda itself to the constructor, but only its type to the third template parameter. No repetition is necessary.

Fujio

Answer 10

With latest c++ standard, you can actually declare a lambda function for comparator which would make the code much cleaner. Here is a sample code:

#include <queue>

class Foo
{
    public:
        int i;
};


int main()
{
    auto comparator = [](const Foo& a, const Foo& b) {
        return a.i > b.i;
    };

    std::priority_queue<Foo, std::vector<Foo>, decltype(comparator)>  pq(comparator);
    return 0;
}

Cusk

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. – Bathsheeb

Answer 11

With the help of struct also we can do this. The code will go something like below.

struct myCompare{
    bool operator()(Node &a, Node &b){
        // Your own custom logic to compare the two nodes and return a boolean value.
    }
}

priority_queue<Node, vector<Node>, myCompare> openSet;

Pellicle