I am curious about the use of std::greater.
When used with sort
, it outputs the numbers in descending order. But when used with priority_queue
, numbers are output in ascending order. Why so?
Example:
#include <iostream> // std::cout
#include <functional> // std::greater
#include <algorithm> // std::sort
#include <queue> // std::priority_queue
int main () {
int numbers[]={20,40,50,10,30};
std::priority_queue<int, std::vector<int>, std::greater<int>> pq (numbers, numbers+5);
std::sort(numbers, numbers + 5, std::greater<int>());
while(!pq.empty()){
std:: cout << pq.top() << ' ';
pq.pop();
}
std::cout << '\n';
for (int i=0; i<5; i++)
std::cout << numbers[i] << ' ';
return 0;
}
The output of above code is:
10 20 30 40 50
50 40 30 20 10
Or similar lines,
std::priority_queue<int, std::vector<int>, std::greater<int> >
creates a min heap whereas std::priority_queue<int, std::vector<int>, std::less<int> >
creates a max heap. Could have been the other way round. Why is it so?
Citing std::priority_queue
at cppreference [emphasis mine]
A priority queue is a container
adaptor
that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.A user-provided
Compare
can be supplied to change the ordering, e.g. usingstd::greater<T>
would cause the smallest element to appear as thetop()
.
So this order is expected, and does not really relate to how std::sort
sorts element based on a supplied binary comparison function.
Sorts the elements in the range
[first, last)
in ascending order....
Parameters
first
,last
- the range of elements to sort
policy
- the execution policy to use. See execution policy for details.
comp
- comparison function object (i.e. an object that satisfies the requirements of Compare) which returnstrue
if thefirst
argument is less than (i.e. is ordered before) thesecond
.
As std::greater
will return true
if its first argument is greater than its second one, we expect the elements to be sorted in descending order when using std::sort
with std::greater
as function object for performing comparisons.
I.e., std::greater
just happens to be the function object used for performing comparisons in these two different contexts of your example.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With