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

Question

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

The top element is the element that compares higher in the priority_queue, and the next that is removed from the container when priority_queue::top is called.

This member function effectively calls member front of the underlying container object.

因此，默认构造的 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，而是 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

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

Explain behavior of default priority_queue::top()?

c++

stl

priority-queue