Search code examples
c++comparatorpriority-queue

Why does C++ comparator behaves inversly in priority_queue and sort()?


Edit: Yes I have made a mistake defining the comparator. I have changed the operator to <. The behavior is now defined and does not change.

I defined a simple comparator class

class MyCompare {
    public:
       bool operator()(int a, int b){
           return a < b;
      }
};

This returns true, and gives a more priority when it is smaller. When used as follow, it sorts the vector in ascending order, first element is the smallest.

However, when it is used in priority_queue, the top() element is the largest. I wonder why it is inversed in the priority_queue? What's the logic behind this?

When used in sort:

vector<int> v = {3,2,1};
sort(v.begin(), v.end(), MyCompare());
for (int i : v) {
    cout << to_string(i) << endl;
}

The result is:

1
2
3

When used in priority_queue:

priority_queue<int, vector<int>, MyCompare> pq;
pq.push(3);
pq.push(2);
pq.push(1);

while (!pq.empty()) {
   cout << pq.top() << " " << endl;
   pq.pop();
}

The result is:

3
2
1

I am expecting 1, 2, 3 as smaller element has higer priority I'm wondering why the effect is inversed?


Solution

  • This simply how priority queue is defined, according to cppreference:

    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.

    I presume, basic implementions rely on std::make_heap and related functions that also store maximal element in the front (by default).