std::priority_queue

 

C++

语言

标准库头文件

自立与有宿主实现

具名要求

语言支持库

概念库 (C++20)

诊断库

工具库

字符串库

容器库

迭代器库

范围库 (C++20)

算法库

数值库

本地化库

输入/输出库

文件系统库 (C++17)

正则表达式库 (C++11)

原子操作库 (C++11)

线程支持库 (C++11)

技术规范

 

容器库

序列

array (C++11)

vector

deque

forward_list (C++11)

list

关联

set

multiset

map

multimap

无序关联

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

适配器

stack

queue

priority_queue

视图

span (C++20)

 

std::priority_queue

成员函数

priority_queue::priority_queue

priority_queue::~priority_queue

priority_queue::operator=

元素访问

priority_queue::top

容量

priority_queue::empty

priority_queue::size

修改器

priority_queue::push

priority_queue::emplace (C++11)

priority_queue::pop

priority_queue::swap (C++11)

非成员函数

std::swap (C++11)

推导指引(C++17)

 

定义于头文件 <queue>
template<     class T,     class Container = std::vector<T>,     class Compare = std::less<typename Container::value_type> > class priority_queue;

priority_queue 是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与释出。

可用用户提供的 Compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。

用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

模板形参

T	-	存储的元素类型。若 T 与 Container::value_type 不是同一类型则行为未定义。 (C++17 起)
Container	-	用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求，而其迭代器必须满足老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。另外，它必须提供拥有通常语义的下列函数： front() push_back() pop_back() 标准容器 std::vector 和 std::deque 满足这些要求。
Compare	-	提供严格弱序的比较 (Compare) 类型。

注意比较 (Compare) 形参的定义，使得若其第一参数在弱序中先于其第二参数则返回 true 。但因为 priority_queue 首先输出最大元素，故“先来”的元素实际上最后输出。即队列头含有按照比较 (Compare) 所施加弱序的“最后”元素。

成员类型

成员类型	定义
container_type	Container
value_compare	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	检查底层容器是否为空 (公开成员函数)
size	返回容纳的元素数 (公开成员函数)
修改器
push	插入元素，并对底层容器排序 (公开成员函数)
emplace (C++11)	原位构造元素并排序底层容器 (公开成员函数)
pop	删除队首元素 (公开成员函数)
swap (C++11)	交换内容 (公开成员函数)
成员对象
Container c	底层容器 (受保护成员对象)
Compare comp	比较函数对象 (受保护成员对象)

非成员函数

std::swap(std::priority_queue) (C++11)

特化 std::swap 算法 (函数模板)

辅助类

std::uses_allocator<std::priority_queue> (C++11)

特化 std::uses_allocator 类型特征 (类模板特化)

示例

运行此代码

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // 用 lambda 比较元素。
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3);
 
}

输出：

9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
8 9 6 7 4 5 2 3 0 1

缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

DR	应用于	出版时的行为	正确行为
LWG 2684	C++98	priority_queue 接收比较器但缺少对它的成员 typedef	已添加