Can someone explain the arguments when creating a priority_queue?

[idknuttin]

I was learning about priority_queues and didn't understand what the second and third arguments are for when creating a priority queue in this example:

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

The way I understand it is the a priority queue orders the list from greatest to smallest, but when you include the third argument from the above example it reverses the queue and stores the values from smallest to largest, why does the std::greater function do this?

Another question I had was when inserting a vector of size 5 into a queue or set for example you need to do this

vector_name.insert(myVect, myVect+5);

why do we need to include the second argument, shouldn't the compiler know how big the vector is?

[kbw]

https://en.cppreference.com/w/cpp/container/priority_queue

[idknuttin]

@kbw

I looked at that but I can't make sense of it.

[George P]

http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

5 examples of constructing a std::priority_queue created with different arguments.

[Enoizat]

The way I understand it is the a priority queue orders the list from greatest to smallest, but when you include the third argument from the above example it reverses the queue and stores the values from smallest to largest, why does the std::greater function do this?

Because that’s how the std::priority_queue has been conceived?
https://en.cppreference.com/w/cpp/container/priority_queue:

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

std::priority_queue uses std::less by default, arguably to order the elements in descending order. Using std::greater you invert the order.

- - -

Another question I had was when inserting a vector of size 5 into a queue or set for example you need to do this
vector_name.insert(myVect, myVect+5);
why do we need to include the second argument, shouldn't the compiler know how big the vector is?

1) Has std::queue got an insert() method?

2) Is “vector_name” your std::queue or std::set? What about a better name?

3) The compiler is not expected to know your will. What if you don’t want to include the entire std::vector? A good insert algorithm lets you decide the range of elements you want to take, for example by an iterator to the first and one to the last one.

[dhayden]

Like most of the standard library, priority_queue is designed to be very flexible so it can meet the needs of many problems.

The second argument exists because you might want to use a different container for the underlying storage. The reference page that kbw mentions indicates that std::vector and std::deque will both work.

The way I understand it is the a priority queue orders the list from greatest to smallest

Technically it does not order the list, at least not completely. It just ensures that when you remove the top item, it will be the largest (by default). If that's all you need to do then priority_queue is faster than a fully sorted container.

The third argument lets you define how the items compare to each other. In other words, what you mean by "largest". Suppose your problem met all the requirements for using a prioirty queue, but you wanted to remove the smallest item, not the largest. Wouldn't it be terrible if you couldn't use std::priority_queue? It meets all your needs except one silly tiny one. For this reason, priority_queue (and all the containers that express an ordering) let you specify the function that orders them.

A great example is an event driven simulator. Events are processed in the order that they occur. So you want to shove events into a container and then each time you remove one, you want the one that occurs earliest - the one whose time stamp is less than all the others, not greater.

Hope this helps.