C++

参考

<queue>

priority_queue

类模板
<queue>

std::priority_queue

template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> > class priority_queue;
优先队列
优先队列是一种容器适配器，经过专门设计，使其第一个元素始终是它所包含的元素中最大的，这根据某种严格弱序标准来判断。

这个上下文类似于堆，元素可以在任何时候插入，并且只能检索到最大堆元素（即优先队列顶部的元素）。

优先队列以容器适配器的形式实现，这些类使用特定容器类的封装对象作为其底层容器，提供一组特定的成员函数来访问其元素。元素从特定容器的“后端”被弹出，这个位置被称为优先队列的顶部。

底层容器可以是任何标准容器类模板或一些其他专门设计的容器类。该容器应能通过随机访问迭代器访问，并支持以下操作：
  • empty()
  • size()
  • front()
  • push_back()
  • pop_back()

标准容器类 vector 和 deque 满足这些要求。默认情况下，如果某个 priority_queue 类实例化没有指定容器类，则使用标准容器 vector。

需要支持随机访问迭代器，以便在任何时候都能在内部保持堆结构。这是通过容器适配器自动完成的，它会在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap。

模板参数

T
元素的类型。
别名为成员类型 priority_queue::value_type。
Container
存储元素的内部底层容器对象的类型。
其 value_type 必须是 T。
别名为成员类型 priority_queue::container_type。
Compare
一个二元谓词，它接受两个元素（类型为 T）作为参数并返回一个 bool 值。
表达式 comp(a,b)，其中 comp 是此类型的对象，a 和 b 是容器中的元素，如果 a 在该函数定义的严格弱序中被认为排在 b 之前，则应返回 true。
priority_queue 使用此函数来维护元素的排序，以保持堆属性（即，被弹出的元素是根据此严格弱序排在最后的元素）。
这可以是一个函数指针或一个函数对象，默认为 less<T>，其返回值与应用小于运算符（a<b）相同。

成员类型

成员类型定义说明
value_type第一个模板参数 (T)元素的类型
container_type第二个模板参数 (Container)底层容器的类型
size_type一个无符号整数类型通常与 size_t 相同
成员类型定义说明
value_type第一个模板参数 (T)元素的类型
container_type第二个模板参数 (Container)底层容器的类型
引用container_type::reference通常是 value_type&
const_referencecontainer_type::const_reference通常是 const value_type&
size_type一个无符号整数类型通常与 size_t 相同

成员函数

（构造函数）
构造优先队列 (公开成员函数)
empty
测试容器是否为空 (公开成员函数)
size
返回大小 (公开成员函数)
top
访问顶部元素 (公开成员函数)
push
插入元素 (公开成员函数)
emplace
构造并插入元素 (公开成员函数)
pop
移除顶部元素 (公开成员函数)
swap
交换内容 (公开成员函数)

非成员函数重载

swap (queue)
交换优先队列的内容 (公开成员函数)

非成员类特化

uses_allocator<queue>
为优先队列使用分配器 (类模板)