CODEWITHSUNDEEP
c++sortingc++11stdpriority-queue
SGVF
SGVF

Reputation: 51

what leads to the difference of sorting way in priority_queue and sort() function?

I'm learning to use priority_queue container and sort() function in the standard library and am puzzled by the parameters of compare function of priority_queue and sort() function

for the sort() function, my compare function: first argument < second argument will sort from smallest to greatest. just as (1) code below

for priority_queue container, my compare function: first arguemnt > second argument will sort element from smallest to greatest. just like (2) code below

what leads to the difference ?

this is my code of using std::priority_queue:

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
struct Compare {
    bool operator() (int left, int right) {
    //here is left>right  .......... (1)
    return(left>right);
    }
};

template<typename T> 
void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}

int main() {
    std::priority_queue<int,vector<int>,Compare> q;

    for(int n : {1,8,5,6,3,4,0,9,7,2})
    q.push(n);

    print_queue(q);

}

Output:

0 1 2 3 4 5 6 7 8 9

this is my code of using sort():

#include<bits/stdc++.h>
using namespace std;

bool compare(int i1, int i2)
{   //here is i1<i2       .............(2)
    return (i1 < i2);
}

int main()
{
    int arr[] =  { 6,2,1,5,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr+n, compare);

    cout << "Intervals sorted by start time : \n";
    for (int i=0; i<n; i++)
        cout << arr[i]<<",";
    return 0;
}

Output:

1,2,4,5,6,8

Upvotes: 3

Views: 80

Answers (1)

Michael Doubez
Michael Doubez

Reputation: 6863

The short answer is that the c++ standard says so:

  • std::sort sorts the elements in the range [first, last) in ascending order
  • std::priority_queue provides lookup of the largest element (based on std::less)

So you need, to invert the comparison to obtain the same result.

Why std::priority_queue was chosen to expose the greater element, I don't know but I suspect it was inspired by section 5.2.3 of Knuth. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching.) as stated in the notes of good old Stl SGI

Upvotes: 3

Related Questions