此问题在此处已有答案:
[c++ why priority_queue greater<> result is different from sorts greater result?](https://stackoverflow.com/questions/69242776/c-why-priority-queue-greater-result-is-different-from-sorts-greater-result)(2个答案) [Priority queue, overloading less operation](https://stackoverflow.com/questions/11056465/priority-queue-overloading-less-operation)(3个答案) [How to intuitively understand larger than/less than operator in comparator of C++ priority queue container](https://stackoverflow.com/questions/38819467/how-to-intuitively-understand-larger-than-less-than-operator-in-comparator-of-c)(2个答案) 4天前关闭。 编辑:是的,我在定义比较器时犯了一个错误。我将运算符更改为
<`。现在行为已经定义,并且没有更改。
我定义了一个简单的比较器类
class MyCompare {
public:
bool operator()(int a, int b){
return a < b;
}
};
这个函数返回true
,当a
较小时,它会给a
更高的优先级。当如下使用时,它会按升序排序向量,第一个元素是最小的。
但是在priority_queue中使用时,top()
元素是最大的,不知道为什么在priority_queue中取反了,这背后的逻辑是什么?
用于排序时:
vector<int> v = {3,2,1};
sort(v.begin(), v.end(), MyCompare());
for (int i : v) {
cout << to_string(i) << endl;
}
结果是:
1
2
3
在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();
}
结果是:
3
2
1
我期待1,2,3作为较小的元素有较高的优先级,我想知道为什么效果是相反的?
1条答案
按热度按时间fykwrbwg1#
这只是根据cppreference定义优先级队列的方式:
优先级队列是一个容器适配器,它提供最大(默认情况下)元素的恒定时间查找,代价是对数插入和提取。
我认为,基本实现依赖于
std::make_heap
和相关函数,这些函数也将最大元素存储在前面(默认情况下)。