解释默认 priority_queue::top() 的行为？

Question

在std::priority_queue默认情况下使用std::vector<int>和std::less比较。默认情况下，priority_queue 是最大堆。

top()的文档指出：

所述顶部元件是比较在较高的元件priority_queue，和被从容器中取出时，下一个priority_queue::top将被调用。

这个成员函数有效地调用front了底层容器对象的成员。

因此，默认构造priority_queue的整数构造如下：

auto maxheap = priority_queue<int>();
maxHeap.push(1);
maxHeap.push(3);
cout << maxHeap.top(); // outputs 3

然而，回到对 的描述top()，文档指出，实际上，front底层容器对象上的成员被调用。如果我创建一个向量并使用排序std::less来模拟我们的 maxHeap 的底层容器：

auto vec = vector<int>{3, 1};
sort(vec.begin(), vec.end(), less<int>()); // {1, 3}
cout << vec.front(); // outputs 1

因为std::less按升序排序，调用vec.front()最终返回最小值。

我对priority_queue::top()文档的默认行为和内容的理解存在一些脱节。有人可以向我解释一下吗？

Answer 1

您使用了错误的算法，您可以在https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue阅读 ，std::priority_queue它不使用std::sort, but std::make_heap。

如果你也在你的例子中使用它，你会得到你期望的输出。

std::vector<int> queue{1, 3};
std::make_heap(queue.begin(), queue.end(), std::less<>{});
std::cout << queue.front() << '\n';

Output: 3