Priority Queue Comparison

Question

I'm trying to declare a priority queue in c++ using a custom comparison function...

So , I declare the queue as follows:

std::priority_queue<int,std::vector<int>, compare> pq;

and here's the compare function :

bool compare(int a, int b)
{
   return (a<b);
}

I'm pretty sure I did this before, without a class,in a similar way, but now, this code doesn't compile and I get several errors like this :

type/value mismatch at argument 3 in template parameter list for 'template<class _Tp, class _Sequence, class _Compare> class std::priority_queue'

Is there a way to create a compare function similar to this but without using a class?

Thanks

Solution 1

The template parameter should be the type of the comparison function. The function is then either default-constructed or you pass a function in the constructor of priority_queue. So try either

std::priority_queue<int, std::vector<int>, decltype(&compare)> pq(&compare);

or don't use function pointers but instead a functor from the standard library which then can be default-constructed, eliminating the need of passing an instance in the constructor:

std::priority_queue<int, std::vector<int>, std::less<int> > pq;

http://ideone.com/KDOkJf

If your comparison function can't be expressed using standard library functors (in case you use custom classes in the priority queue), I recommend writing a custom functor class, or use a lambda.

Solution 2

You can use C++11 lambda function. You need to create lambda object, pass it to the template using decltype and also pass it to the constructor. It looks like this:

auto comp = [] (int &a, int &b) -> bool { return a < b; };
std::priority_queue<int,std::vector<int>, decltype(comp) > pq (comp);

Solution 3

you have to specify function type and instantiate the function in priority_queue constructor.

#include <functional>

bool compare(int a, int b)
{
   return (a<b);
}

std::priority_queue<int, std::vector<int>,
                              std::function<bool(int, int)>> pq(compare);

Solution 4

This worked perfectly for me.

struct compare{
    bool operator() (const int& p1,const int& p2 ){
         return p1<p2;
    }
};

int main(){
    priority_queue<int,vector<int>, compare > qu;
return 0;
}

Solution 5

std::priority_queue<int, std::vector<int>, bool (*)compare(int, int)> pq(compare);

Is another way not mentioned.

View more solutions

Comments

[leemes]

Try &compare. If this doesn't work you can also use std::less<int>. It might be the case that the template parameter should be the type of the functor, not a functor/function value.

[user2455103]

Thanks but no, &compare doesn't work.... The reason why I'm asking this is because I want to sort structs, bases on one of their valuse, so std::less wouldn't really work....

[leemes]

But it doesn't work because you didn't pass a function, only a type telling its signature.

[user2455103]

Ahh thanks, this compiles perfectly, but I still don;t understand how this works, and the way I could add my custom comparison with it... It would be nice if you clarified a little bit! Thanks!

[Emil Condrea]

you are right, i forgot to add the function as parameter for constructor

[Emil Condrea]

i updated my answer , not forgeting this time to pass the compare function to the constructor.

[user2455103]

Well... It's so strange but the first one doesn't compile for me.. I copied the code from Ideone and it doesn't work...

[user2455103]

Actually I'm not sure... I'm using codeblocks 12.11 and the compiler installed along with it...

[leemes]

But it has the disadvantage that if you change the signature of compare, you also have to change CompareType accordingly. The other code makes use of decltype which will get you the type of what's in (), but it's only available since C++11.

[user2455103]

Yeah... this works, but as with Emil Condrea's answer I don't understand why......

[user2455103]

Ahh ok ok got it .. You need to pass a type as another guy said to the pqueue... Thanks

[leemes]

The thing is: you need to tell the priority queue both the type and a pointer to your comparison function. The type goes into the template parameter list, but the type is not enough, so the constructor accepts a value of this type, and since the type is a function pointer type, you can then pass a function pointer. The ampersand & gives you a pointer to a function. I hope this explains it. ;)

[user2455103]

Yeah thanks, so that was what the decltype function does.... It feeds the pqueue with the type and then the ampersand gives to the constructor the address of the actual compare function. Yes thanks a lot! I now understand it :)

[Mohammad Mamun Hossain]

what is the purpose of the second parameter "std::vector<int>" in the template?

[Jaa-c]

@MohammadMamunHossain: That's the default value for the underlying container.

[Jesse Ahn]

This looks the simplest among many solutions.