priority_queue<T, Sequence, Compare>



类别：容器，适配器	组件类型：类型

说明

Apriority_queue是一个适配器，它提供了一组受限制的Container功能：它提供元素插入以及检查和移除顶部元素。可以保证顶部元素是priority_queue中的最大元素，其中函数对象Compare用于比较。 [1]Priority_queue不允许通过其元素进行迭代。 [2]

Priority_queue是一个容器适配器，这意味着它是在底层容器类型的基础上实现的。默认情况下，底层类型为vector，但可以显式选择不同的类型。

示例

int main() {
  priority_queue<int> Q;
  Q.push(1);
  Q.push(4);
  Q.push(2);
  Q.push(8);
  Q.push(5);
  Q.push(7);
  
  assert(Q.size() == 6);

  assert(Q.top() == 8);
  Q.pop();

  assert(Q.top() == 7);
  Q.pop();

  assert(Q.top() == 5);
  Q.pop();

  assert(Q.top() == 4);
  Q.pop();

  assert(Q.top() == 2);
  Q.pop();

  assert(Q.top() == 1);
  Q.pop();

  assert(Q.empty());
}

定义

定义在标准的头文件queue中，和非标准的后向兼容性头文件中stack.h。

模板参数

参数	说明	默认
`T`	存储在优先队列中的对象的类型。
`Sequence`	用于实现优先队列的底层容器的类型。	`vector<T>`
`Compare`	用于确定一个元素是否小于另一个元素的比较函数。如果`Compare(x,y)`是`true`，则`x`小于`y`。由`Q.top()`返回的元素是优先队列中的最大元素。也就是说，它具有如下属性：对于优先队列中的每个其他元素，`xCompare(Q.top(), x)`是`false`.	`less<T>`

模型

Assignable, Default Constructible

类型要求

T是Assignable的模型。
Sequence是Sequence的模型。
Sequence是Random Access Container的模型
Sequence::value_type与T.
Compare的类型相同。是Binary Predicate的模型
Compare对其参数类型强制执行严格的弱排序，如LessThan Comparable要求中定义的那样
T可转换为Compare的参数类型。

公共基类

无

成员

成员	定义位置	说明
`value_type`	`priority_queue`	见下文。
`size_type`	`priority_queue`	见下文。
`priority_queue()`	Default Constructible	默认构造函数。创建一个空`priority_queue`，使用`Compare()`作为比较函数。
`priority_queue(const priority_queue&)`	Assignable	复制构造函数。
`priority_queue(const Compare&)`	`priority_queue`	见下文。
priority_queue(const value_type, const value_type)	`priority_queue`	见下文。
priority_queue(const value_type, const value_type, const Compare&)	`priority_queue`	见下文。
priority_queue& operator=(const priority_queue&)	Assignable	赋值运算符。
`bool empty() const`	`priority_queue`	见下文。
`size_type size() const`	`priority_queue`	见下文。
`const value_type& top() const`	`priority_queue`	见下文。
`void push(const value_type&)`	`priority_queue`	见下文。
`void pop()` [3]	`priority_queue`	见下文。

新的成员

这些成员未在可赋值和默认构造要求中定义，但特定于priority_queue.

成员	说明
`value_type`	存储在`priority_queue`中的对象类型。这与以下内容相同`T`和`Sequence::value_type`.
`size_type`	无符号整数类型。这与以下内容相同`Sequence::size_type`.
`priority_queue(const Compare& comp)`	构造函数。创建空的`priority_queue`，使用`comp`作为比较函数。默认构造函数使用`Compare()`作为比较函数。
priority_queue(const value_type* first, const value_type* last)	构造函数。创建一个`priority_queue`初始化为包含`[first, last)`中的元素，并使用`Compare()`作为比较函数。
priority_queue(const value_type* first, const value_type* last, const Compare& comp)	构造函数。创建一个`priority_queue`初始化为包含`[first, last)`中的元素，并使用`comp`作为比较函数。
`bool empty() const`	返回`true`如果`priority_queue`不包含任何元素且`false`否则。`S.empty()`等效于`S.size() == 0`.
`size_type size() const`	返回包含在`priority_queue`.
`const value_type& top() const`	中的元素数`Compare`返回对 priority_queue 顶部元素的常量引用。保证顶部元素是 priority_queue 中最大的元素，由比较函数`x`确定。这意味着，对于`priority_queue`, `Compare(Q.top(), x)`是`false`中的其他任何元素`。前提`是`false`.
`empty()`	void push(const value_type& x)`x`插入`到 priority_queue 中。后置条件`size()`1`.
`void pop()`	将增加`。前提`是`false`。从 priority_queue 中移除顶部的元素，即 priority_queue 中最大的元素。 [3] 前提`到 priority_queue 中。后置条件`。后置条件`1`.

将会减少

备注

[1] 优先级队列是一个标准概念，可以用许多不同的方式实现；此实现使用堆。在所有算法书中都有关于优先级队列的讨论；例如，参见 Knuth 的第 5.2.3 节。（D. E. Knuth，计算机编程的艺术。第 3 卷：排序和搜索。阿迪森 - 韦斯利，1975。）priority_queue[2] 这种限制是vector存在的唯一原因。如果通过元素的迭代很重要，则可以使用以排序好的顺序维护，或者setvector，或者使用, make_heappush_heap和. Priority_queuepop_heappriority_queue作为堆维护的

事实上，被实现为作为堆维护的随机访问容器。使用容器适配器的唯一原因是，而不是手动执行堆操作，是为了明确表示你永远不会执行任何可能违反堆不变性的操作。[3] 可能有人会疑惑为什么pop()返回value_typevoid而不是和的唯一原因是，而不是手动执行堆操作，是为了明确表示你永远不会执行任何可能违反堆不变性的操作。。即，为什么必须使用priority_queuetop()的唯一原因是，而不是手动执行堆操作，是为了明确表示你永远不会执行任何可能违反堆不变性的操作。返回栈顶元素，它将通过值返回而不是通过引用返回：通过引用返回将创建一个悬空指针。但是，通过值返回效率低下：它至少要调用一个冗余的复制构造函数。由于不能的唯一原因是，而不是手动执行堆操作，是为了明确表示你永远不会执行任何可能违反堆不变性的操作。用既高效又正确的方式返回一个值，因此它不返回任何值并且要求客户端使用而不是来检查priority_queue.

栈的栈顶值

另请参阅, 堆栈, 以排序好的顺序维护，或者, 使用, make_heap, 和, 队列, is_heap排序