c++ - std::sort 和 priority_queue (C++) 的比较顺序之间的区别

Question

我想知道为什么priority_queue并vector以完全不同的方式工作。这是示例：

priority_queue<int, vector<int>, less<int> > pq;
pq.push(1);
pq.push(2);
pq.push(3);
// if we print the elem in pq by pop(), we get 3, 2, 1
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(2);
std::sort(v.begin(), v.end(), less<int>()); 
// but we get 1, 2, 3 for vector

两者都priority_queue使用vector过less，但为什么结果不同？

标签： c++c++11stlpriority-queue

Answer 1

std::less是 的默认比较器priority_queue，并且std::vector是默认容器，因此您的代码可以简化为：

priority_queue<int> pq;

根据文档，预计通过pop

优先级队列是一个容器适配器，它提供对最大（默认情况下）元素的恒定时间查找，代价是对数插入和提取。

实际上，我们得到一个max heapwithstd::less作为比较器，这看起来不是很直观。要获得min heap，我们需要将std::greater其用作比较器。

相关问题以查看更多底层细节