Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Use of std::greater

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?

like image 845
Shridhar R Kulkarni Avatar asked Sep 06 '18 15:09

Shridhar R Kulkarni


1 Answers

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.

like image 155
dfrib Avatar answered Oct 25 '22 10:10

dfrib