13

This code works:

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main(){
    priority_queue<int,vector<int>,greater<int> > pq;
    pq.push(1);
    cout<<pq.top()<<endl;
}

But,this code does not compile:

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main(){
    priority_queue<int,vector<int>,greater<int>() > pq;
    pq.push(1);
    cout<<pq.top()<<endl;
}

Why?
All I understand is that greater<int>() is a function object and priority_queue accepts a binary predicate as third argument and that predicates are a special type of functors. But how does the pair of braces make that difference.

Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
Manohar
  • 165
  • 1
  • 1
  • 10

2 Answers2

11

In this declaration

priority_queue<int,vector<int>,greater<int> > pq;

the type template argument greater<int> corresponds to the type of a structure.

In this declaration

priority_queue<int,vector<int>,greater<int>() > pq;

the type template argument greater<int>() corresponds to the type of a function that has no parameters and has the return type greater<int>

The class template std::priority_queue expects that the argument will be of a function object type that is a pointer to function or a class type that has a function operator.

To make it more clear compare for example these declarations

std::vector<int()> v1;

and

std::vector<int (*)()> v2;

For the first declaration the compiler will issue an error because the operator sizeof may not be applied to a function type int() and the vector will be unable to allocate memory for its elements. Here int() used as a type template argument is not an expression. It is a type-id.

In the second declaration the vector deal with pointers to function and it can allocate memory for its elements that are pointers.

Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
3

From cppreference:

template<
     class T,
     class Container = std::vector<T>,
     class Compare = std::less<typename Container::value_type>
 > class priority_queue;

Compare - A Compare type providing a strict weak ordering.

So for std::priority_queue you pass a type of comparator as a template parameter.

On the other hand,

greater<int>()

stands for creation of new object of type greater<int> which is not an option in your case.

Edgar Rokjān
  • 17,245
  • 4
  • 40
  • 67
  • Your answer was meaningful. Can you please provide some insight on how a 'type' can compare things. So far I have used and seen only functions, functors and lamdas for comapring. – Manohar May 29 '17 at 11:14
  • @Manohar I guess that *priority_queue* simply creates an instance of *Comparator* to compare things. – Edgar Rokjān May 29 '17 at 11:20
  • Functions, functors and lambas have a type. Since the class/function should accept any of these, they have to be templated. Most of the time (algorithms library etc.) this type is deduced and you dont need to provide it explicitly https://stackoverflow.com/questions/356950/c-functors-and-their-uses – lars May 29 '17 at 11:31