8

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?

Improve this question
7
  • 1
    Please explain the downvote. Understanding the behavior of constructs used in STL makes a valid question. Commented Sep 6, 2018 at 15:07
  • 1
    It seems to me like the question you are actually asking is why std::sort sorts in the opposite order of std::priority_queue and has nothing to do with std::greater. Edit : This is not an explanation for the downvote, I didn't downvote. Commented Sep 6, 2018 at 15:08
  • 3
    Still a fairly good question : mcve + clear + specific + well formatted. Commented Sep 6, 2018 at 15:08
  • @FrançoisAndrieux: The title gives the clarity of my question. Plus clean code example is provided so as to leave no scope for ambiguity. All we need is just some patience to read the whole question. Commented Sep 6, 2018 at 15:11
  • 1
    Greater just says if something is greater than another. It doesn’t imply any specific behaviors associated with the result. You could use it to sort in either direction. Commented Sep 6, 2018 at 18:27

1 Answer 1

Reset to default
7

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. using std::greater<T> would cause the smallest element to appear as the top().

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 returns true if the first argument is less than (i.e. is ordered before) the second.

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for explaining the difference in behavior for sort and priority_queue. But still the part of question after "Or similar lines, " remains unanswered. I meant to ask why is it not "A user-provided Compare can be supplied to change the ordering, e.g. using std::**less**<T> would cause the smallest element to appear as the top()."? <functional> less for min heap makes more sense than greater. Right?
@ShridharRKulkarni that is indeed a different (second), question, and the rationale for that choice (from the C++ standard) already has an excellent answer here. I see no reason duplicating that content in my answer here, but I can add the link to it tomorrow when I’m not just accessing SO from my phone.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.