Why does the function comparator not work in the priority queue, as in sorting?

Question

We have a question that discusses how to use a comparator in priority_queue in C ++. It gives an overloaded operator class (or struct ) as the third argument, and it works fine. But the bool function does not work. What for? But it works fine in sort <algorithm> . When I looked at the documents ( priority_queue && algo / sort ), both of them accept class Compare as an 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 also use the function with std::priority_queue . The difference in what you do is that you pass the function std::sort as the parameter of the function, but you are trying to define the function as the parameter of the queue template. This obviously does not work, because the third argument is a type argument, as the error explains. In addition, you cannot even have a pointer or template template.

If you look at reference , you will find that the queue has a constructor for passing the comparison object. This is where you should pass the function.

There is a difference with std::sort . Sorting is a function, and you can let the compiler output its template arguments, so you don't need to explicitly specify them. A queue is a class template, and class template template arguments cannot be output (not in this context, at least).

The template argument defaults to std::less<typename Container::value_type> , but you do not want to use it. Therefore, you must explicitly specify the type of comparison object. You indicate where you are currently trying to pass the object. How to get the type of pointer / link function, you may ask. You can do it this way: decltype(&cmp) . If you have an outdated compiler that does not yet support decltype , you need to specify the type without it: bool (&)(const int&, const int&) .

Here is an example of how to create a queue using your function.

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

Answer 2

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

Answer 3

The answer to the compiler error. The third parameter of the priority queue template is the type of comparator (for example, structure or classes), not a function.