Syntax of priority queue-CodePudding

why do we need 3 parameters for creating a priority queue with user-defined comparison .

priority_queue<Node*, vector<Node*>, comp> pq;

why cant we write something like priority_queue<Node*, comp> pq;(removed vector<node*>) to create our own comparison operator. What is the purpose of vector<node*> ?

Also how are the elements taken for comparison, and pushed into the queue after comparison.

How does overloading occur here.

CodePudding user response：

If you see the std::priority_queue delectation, you can see second and third template parameter is defaulted in std implementation.

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

When you do priority_queue<Node*, com> so here com is second parameter, but in the declaration it is third. so to set it to exact third position we need to add the second parameter as well, just like functions where we have to add default parameters to the right of function param list.

This is how std::priority_queue is designed, as std::vector is used as a default container, so adding it at second position gives us flexibility to use our own containers instead of std::vector. As it happens to be in the middle of other default parameter list, so to set the right most default parameters, the default parameters coming its way has to be set as well. It's the language requirement.

If you understand priority-queue, it uses heap which stores your data in such an order based on the comparator you provided, so that the (lets say) maximum element is on top, priority-queue, insert and extract the data using that comparator. Which is by default std::less which require you to provide overload for < operator for your type you are trying to put in prirotiy_queue in you case it is Node. If you want to set your own priority criteria, you can provide such an overload.

CodePudding user response：

why cant we write something like priority_queue<Node*, comp> pq;(removed vector<node*>) to create our own comparison operator.

It is no problem to just define the shortcut you would like to have, by just aliasing the specific type of interest (priority queues with vector as container type):

template<typename T, typename Cmp = std::less<typename std::vector<T>::value_type>
using vector_priority_queue = std::priority_queue<T, std::vector<T>, Cmp>;

vector_priority_queue<int> pq;
vector_priority_queue<int, comp> pq2;