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?
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).