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?

awesoon · Accepted Answer · 2021-09-29T08:14:05.757

208

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

edited Sep 29 '21 at 08:14

answered Apr 19 '13 at 18:38

awesoon

32,469
11
74
99

1

Perfect, just what I was looking for. I never thought to make a separate class. Would the first example be considered better style? – Steven Morad Apr 19 '13 at 18:42
3

@StevenMorad, I prefer to use class with overloaded `operator()`, it looks simpler. – awesoon Apr 19 '13 at 18:46
6

@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 – Piyush May 28 '16 at 18:00
2

@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. – awesoon May 28 '16 at 21:05
2

@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: https://en.wikipedia.org/wiki/Function_object – yuqli Sep 15 '18 at 00:31
@awesoon would a struct work, or is it necessary to use class only? – Abhay Patil Aug 05 '20 at 20:17
@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. – awesoon Aug 06 '20 at 04:42
NOTE: You should pass `Compare` to the constructor of priority_queue in the second example. – konchy Jul 04 '23 at 12:01
@awesoon in the first example, why is it required to declare another class `Compare`. can we overload the operator in the `Foo` class? – ProgramCpp Aug 14 '23 at 03:26
@awesoon i get an error doing so. can you please help? https://ideone.com/VVHb1L – ProgramCpp Aug 14 '23 at 04:19

Cris Luengo · Answer 2 · 2022-02-13T02:56:12.663

120

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

edited Feb 13 '22 at 02:56

answered Feb 02 '18 at 17:15

Cris Luengo

55,762
10
62
120

3

This is fantastic, I wonder if there are any potential traps (issues) here. Would love to see this answer get more visibility and discussion. – Apollys supports Monica Dec 10 '18 at 18:24
1

@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. – Cris Luengo Dec 10 '18 at 18:26
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`? – Eric Auld Mar 26 '19 at 16:59
@EricAuld: Yes, `Compare` can be a lambda function there, as in `auto Compare = [](){};`. But you need to use `decltype(Compare)`, rather than `decltype(&Compare)`. – Cris Luengo Mar 26 '19 at 17:47
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?! – BitTickler May 04 '21 at 06:34
@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 [mre]. 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. – Cris Luengo May 04 '21 at 13:05
@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 May 04 '21 at 20:51
@CrisLuengo [https://gist.github.com/ruffianeo/55ebe9f921d4f057d979763afc248b23] - the canonical example. – BitTickler May 04 '21 at 21:14
1

@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 May 04 '21 at 21:53

score 29 · Answer 3 · edited Jul 26 '23 at 05:47

29

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;

edited Jul 26 '23 at 05:47

asn

2,408
5
23
37

answered Apr 19 '13 at 18:46

Mic

409
1
4
8

19

The operator method must be public. – knezi Mar 06 '17 at 08:42
1

The third template does not need to be a class. It can be the type of a function. – Cris Luengo Feb 02 '18 at 17:17
1

According to [cpluplus](http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/): _This may be a **function pointer** or function object_ – Benav Aug 11 '20 at 07:09
@Mic can we define the operator() in the Node class itself? – ProgramCpp Aug 14 '23 at 04:20

cute_ptr · Answer 4 · 2016-11-13T11:27:16.060

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)

score 13 · Answer 5 · edited Sep 18 '20 at 12:44

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

score 9 · Answer 6 · answered Apr 13 '19 at 12:10

9

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

answered Apr 13 '19 at 12:10

bornfree

2,308
1
23
33

score 5 · Answer 7 · answered Jul 17 '20 at 13:46

5

In case this helps anyone :

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

answered Jul 17 '20 at 13:46

Mazhar MIK

1,022
12
14

score 3 · Answer 8 · edited Sep 16 '21 at 04:50

3

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;

edited Sep 16 '21 at 04:50

Suraj Rao

29,388
11
94
103

answered Sep 16 '21 at 04:39

Suraj gupta

31
2

I watched this, but I didn't understand why he said operator< is wrong. https://www.youtube.com/watch?v=sbiF1HDcG7U&list=PLs3KjaCtOwSZ2tbuV1hx8Xz-rFZTan2J1&index=97 – Kargath Nov 16 '21 at 15:24
@Kargath 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. – Cris Luengo Aug 19 '22 at 14:11

score 0 · Answer 9 · answered Apr 05 '21 at 13:02

0

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

answered Apr 05 '21 at 13:02

Mital Vora

2,199
16
19

1

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. – Cris Luengo Sep 15 '21 at 15:46

score -1 · Answer 10 · answered Sep 23 '21 at 18:40

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;

score -2 · Answer 11 · answered Nov 23 '19 at 17:58

-2

prefer struct, and it's what std::greater do

struct Compare {
  bool operator()(Node const&, Node &) {}
}

answered Nov 23 '19 at 17:58

Canhua Li

300
2
3

declaring a priority_queue in c++ with a custom comparator

11 Answers11

Linked

Related