Why function comparator doesn't work in priority queue like it does in sort?

Question

We have a question, which discusses how to use a comparator in priority_queue in C++. He gives the overloaded operator class (or struct) as the third argument and it works fine. But bool function doesn't work. Why ? But it works fine in sort of the <algorithm>. When I looked into docs (priority_queue && algo/sort), both of them take the class Compare as their optional third argument.

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp (const int &a,const int &b){ return a > b; }

struct cmp2
{
    bool operator() (const int &p1,const int &p2)
    {
        return p1 > p2;
    }
};

int main ()
{
//  freopen("test.txt","r",stdin);
    int a[10];
    vector<int> b(10);
    sort( a , a + 10, cmp );    // working cool
    sort( b.begin() , b.end() , cmp);   // working great
    priority_queue<int, vector<int> , cmp2 > x;    // as usual, working....
    priority_queue<int, vector<int> , cmp > y;   // not working why ?

    return 0;
}

Errors:

A:\pqvsarray.cpp    In function 'int main()':
27  40  A:\pqvsarray.cpp    [Error] type/value mismatch at argument 3 in template parameter list for 'template<class _Tp, class _Sequence, class _Compare> class std::priority_queue'
27  40  A:\pqvsarray.cpp    [Error] expected a type, got 'cmp'
27  43  A:\pqvsarray.cpp    [Error] invalid type in declaration before ';' token

So, why the difference ?

Answer 1

You can use a function with std::priority_queue as well. The difference in what you're doing is that you pass the function to std::sort as a function parameter, but you try to define the function as a template parameter of the queue. This obviously does not work because the third argument is a type argument as the error explains. Besides, you cannot even have pointer or reference template arguments.

If you take a look at the reference, you'll find that the queue has a constructor for passing the comparison object. That's where you must pass the function.

There is a difference with std::sort. Sort is a function, and you can let the compiler deduce it's template arguments so you don't have to specify them explicitly. The queue is a class template, and template arguments of a class template can not be deduced (not in this context at least).

The template argument is defaulted to std::less<typename Container::value_type>, but you don't want to use that. Therefore, you must specify explicitly the type of the comparison object. You specify it where you're now trying to pass the object. How to get the type of the function pointer/reference, you may ask. You can do it like this: decltype(&cmp). If you have an outdated compiler that does not support decltype yet, then you'll need to specify the type without it: bool (&)(const int&, const int&).

Here is an example of how you would create a queue that uses your function.

std::priority_queue<int, std::vector<int>, decltype(&cmp)> x(cmp);

Answer 2

As the error message implies, functions cannot be used as template parameters. The priority_queue will copy an object of the comparison type. For example, this might be std::less<int>, where an object of that type is std::less<int>(), and it being called is std::less<int>()(x, y). In C++11, you could use decltype, but in C++03 the "canonical" way is to create a "functor" (an entire type dedicated to being used as a function object.) This is one of the reasons why lambdas were created.