编辑:是的,我在定义比较器时犯了一个错误。我已将运算符更改为
<
。行为现已定义且不会更改。
我定义了一个简单的比较器类
class MyCompare {
public:
bool operator()(int a, int b){
return a < b;
}
};
这将返回
true
,并在 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,因为较小的元素具有较高的优先级 我想知道为什么效果是相反的?
根据cppreference,这就是优先级队列的定义方式:
优先级队列是一个提供恒定时间的容器适配器 查找最大的(默认)元素,代价是 对数插入和提取。
我认为,基本实现依赖于
std::make_heap
和相关函数,这些函数也在前面存储最大元素(默认情况下)。