注意

请注意，本文尚未完成！您可以通过编辑此文档页面来提供帮助。

概述

简化

template< class T, /* ... */ >
class priority_queue;

详细

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
>
class priority_queue;

优先队列是一个容器**适配器**——它通过为其提供新接口来适配容器。

新接口类似于一个队列，其指定顺序不基于插入顺序，而是基于元素之间的一些指定关系。

优先队列的技术定义

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

可以提供用户定义的`Compare`来改变排序，例如，使用会使最小的元素出现在`top()`。

使用`priority_queue`类似于在一些随机访问容器中管理堆，优点是不会意外地使堆失效。

std::priority_queue

定义于

队列

模板参数

公共	T	存储元素的类型。 自 C++17 起 危险 如果`T`不是`Container::value_type`，则行为未定义。
公共	容器	用于存储元素的底层容器类型。默认情况下为`std::vector`。 容器必须满足SequenceContainer，其迭代器必须满足LegacyRandomAccesIterator。 此外，它必须提供具有通常语义的以下函数 back() front() push_back() pop_front() 标准容器`std::vector`和`std::deque`满足这些要求。
公共	比较器	提供**严格弱**排序的比较器类型。 注意 **Compare** 参数的定义是，如果其第一个参数在**弱**排序中位于第二个参数之前，则返回 `true`。 但由于优先队列首先输出最大元素，因此“排在前面”的元素实际上是最后输出的。也就是说，队列的前端包含根据**Compare**施加的弱排序的“最后一个”元素。

类型名称

公共	容器类型	容器
公共	value_compare	比较器
公共	value_type	Container::value_type
公共	size_type	Container::size_type
公共	reference	Container::reference
公共	const_reference	Container::const_reference

成员函数

公共	（构造函数）	构造一个`priority_queue`。
公共	（析构函数）	销毁一个`priority_queue`。
公共	operator=	将一个优先队列赋值给另一个。

元素访问

公共

top

访问顶部的元素。

容量

公共	empty	如果队列为空则返回`true`，否则返回`false`。
公共	size	返回队列中元素的数量。

修饰符

公共	push	插入一个元素并使用`Compare`对底层容器进行排序。
公共	emplace (C++11 起)	就地构造一个元素并对底层容器进行排序。
公共	pop	移除顶部元素。
公共	swap （自 C++11 起）	交换两个队列。

成员对象

保护	Container C	底层容器。默认情况下为`std::vector`。
保护	Compare comp	比较器对象。

非成员函数

公共

std::swap (std::priority_queue)

std::swap 算法的重载。

辅助类

公共

std::uses_allocator (std::priority_queue)

特化 std::uses_allocator 类型特征。

推导指南 (C++17 起)

点击展开

推导指南

// (1)
template< class Comp, class Container >
priority_queue( Comp, Container )
  -> priority_queue<typename Container::value_type, Container, Comp>;

// (2)
template< class Comp, class Container, class Alloc >
priority_queue( Comp, Container, Alloc )
  -> priority_queue<typename Container::value_type, Container, Comp>;

// (3)
template< class InputIt, class Comp, class Container, class Alloc >
priority_queue( InputIt, InputIt, Comp, Container, Alloc )
  -> priority_queue<typename Container::value_type, Container, Comp>;

(1 - 3) 允许从**底层容器类型**推导

// (4)
template< class InputIt, class Comp, class Alloc >
priority_queue( InputIt, InputIt, Comp, Alloc )
  -> priority_queue<iter_val_t<InputIt>,
                    std::vector<iter_val_t<InputIt>, Alloc>, Comp>;

// (5)
template< class InputIt, class Alloc >
priority_queue( InputIt, InputIt, Alloc )
  -> priority_queue<iter_val_t<InputIt>,
                    std::vector<iter_val_t<InputIt>, Alloc>,
                    std::less<iter_val_t<InputIt>>>;

// (6)
template< class InputIt,
          class Comp = std::less<iter_val_t<InputIt>>,
          class Container = std::vector<iter_val_t<InputIt> >
priority_queue( InputIt, InputIt, Comp = Comp(), Container = Container() )
  -> priority_queue<iter_val_t<InputIt>, Container, Comp>;

(4 - 6) 允许从**迭代器范围**推导

别名`iter_val_t`定义如下

template< class InputIt >
using iter_val_t = typename std::iterator_traits<InputIt>::value_type;

注意

请注意，此别名不保证在标准库的任何地方找到。它仅用于这些推导指南的展示目的，并且在编写本文档时标准库中不存在。

重载决议

为了使任何推导指南参与重载决议，必须满足以下要求

• InputIt 满足 LegacyInputIterator
• Comp 不满足 Allocator
• Container 不满足 Allocator
• 对于(3)和(5)，(自 C++23 起) `Alloc` 满足`Allocator`
• 对于(2)和(4)，`std::uses_allocator_v`为`true`

注意

库确定类型不满足 LegacyInputIterator 的程度是未指定的，但至少

• 整型不符合输入迭代器的条件。

同样，它确定类型不满足 Allocator 的程度是未指定的，但至少

• 成员类型 Alloc::value_type 必须存在。
• 当作为未求值操作数处理时，表达式 std::declval<Alloc&>().allocate(std::size_t{}) 必须是格式良好的。

示例

基本操作

在队列上进行压入和弹出操作，并打印值

#include <iostream>
#include <queue>

int main()
{
	std::priority_queue<int> q;

	queue.push(1);
	queue.push(2);
	queue.push(3);

	while (!queue.empty()) {
		std::cout << queue.top() << '\n';
		queue.pop();
	}
}

结果

3
2
1