为什么C++比较器在priority_queue和sort()中的行为相反?[duplicate]

5ktev3wc  于 2023-03-20  发布在  其他
关注(0)|答案(1)|浏览(151)

此问题在此处已有答案

[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作为较小的元素有较高的优先级,我想知道为什么效果是相反的?

fykwrbwg

fykwrbwg1#

这只是根据cppreference定义优先级队列的方式:
优先级队列是一个容器适配器,它提供最大(默认情况下)元素的恒定时间查找,代价是对数插入和提取。
我认为,基本实现依赖于std::make_heap和相关函数,这些函数也将最大元素存储在前面(默认情况下)。

相关问题