Why is Vector used as a second argument to Priority Queue?

Question

Why is it that when priority_queue is used with a single data type, like 'int', we initialise it like this: priority_queue<int>; but, when it's initialized with a pair we add a second parameter of type vector priority_queue<pair<int,int>, vector<pair<int,int>>>?

Also, I've noticed several ways to add a third argument that specifies ordering.

Method 1 - Struct

struct myCompare {
   bool operator()(const pair<int, int>& A, const pair<int, int>& B) {
       return A.second < B.second;
   }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, myCompare> leaderBoard;

Method 2 - Lambda

auto myComp = [](const pair<int, int>& A, const pair<int, int>& B) 
              {return A.second < B.second;};

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(myComp)> leaderBoard(myComp);

My Questions

1. Why is the second parameter of priority_queue a vector? What does this mean and when does this second parameter need to be specified?
2. In method 2, why is decltype needed with this lambda?
3. In method 2, why does the object leaderBoard need to be initialised with (myComp)
4. In method 2, why can I not specify my lambda as the third argument directly?
5. What is the difference between A.second > B.second and A.second < B.second? How do you remember which one means ascending order, and which one is descending order?

Answer 1

Why is it that when priority_queue is used with a single data type, like 'int', we initialise it like this: priority_queue<int> [...] ?

Because std::priority_queue is a class template defined as follows:

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

As you can see, you can instantiate this class only providing the T, because the rest of the types will be defaulted. You can read more about template default arguments here.

but, when it's initialized with a pair we add a second parameter of type vector priority_queue<pair<int,int>, vector<pair<int,int>>>?

Because someone wanted to be explicit. priority_queue<pair<int, int>> is equivalent to priority_queue<pair<int,int>, vector<pair<int,int>>>, because the second template type (vector<pair<int, int>>) will be present by default.

1. Why is the second parameter of priority_queue a vector? What does this mean and when does this second parameter need to be specified?

We don't need to specify it explicitly. The second template parameter is a type use for internal representation of data. std::priority_queue is a container adaptor, which means that it's not a container by itself - it uses some other container and wraps it with certain kind of utilities.

2. In method 2, why is decltype needed with this lambda?

Because you need to provide a type. myCompare is a struct, so it's a name of a type. myComp is not a type, it's a variable. You wish to get its declared type? Use decltype.

3. In method 2, why does the object leaderBoard need to be initialised with (myComp)?

Because you cannot default construct an object given a decltype of a lambda (this got relaxed in C++20). You need to use the following constructor:

explicit priority_queue(const Compare& compare)
    : priority_queue(compare, Container()) { }

which expects a callable (in this case - the lambda) that will be used as a comparator.

4. In method 2, why can I not specify my lambda as the third argument directly?

You mean as the third template argument? Because as of right now, lambdas cannot be used in unevaluated contexts, and providing a type for a template is one of those.

5.1. What is the difference between A.second > B.second and A.second < B.second?

The difference is quite blatant. One checks for A.second being greater than the second argument and the other one is the reverse. It is commonly used for sorting (for comparing elements).

5.2 How do you remember which one means ascending order, and which one is descending order?

It's pretty easy - the C++ conception is to use < between the left hand side argument and the right hand side argument, like so: left_hand_side < right_hand_side.