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，为什么结果不一样？

Answer 1

std::less是priority_queue的默认compartor，std::vector是默认的Container，所以你的代码可以简化为：

priority_queue<int> pq;

根据doc，预计通过pop

得到最大值

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.

实际上，我们得到一个max heap和std::less作为比较器，这似乎不是很直观。要获得min heap，我们需要使用std::greater作为比较器。

Related question to see more underly details

Answer 2

std::priority_queue实现为堆，插入元素时会自动排序。 less<int> 表示它是最大堆。当你使用pop()弹出一个元素时，你会得到堆中最大的元素。您可以从 cppreference 获得更详细的描述：

Compare - A Compare type providing a strict weak ordering. Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.

priority_queue

std::sort最有可能使用QuickSort，less<int>表示按升序对元素进行排序。

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

Difference between compare order of std::sort and priority_queue (C++)

c++

stl

priority-queue

c++11