std::priority_queue

来自cppreference.com
< cpp‎ | container
定义于头文件 <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 - 存储的元素类型。TContainer::value_type 不是同一类型则行为未定义。 (C++17 起)
Container - 用于存储元素的底层容器类型。容器必须满足顺序容器 (SequenceContainer) 的要求,而其迭代器必须满足随机访问迭代器 (RandomAccessIterator) 的要求。另外,它必须提供拥有通常语义的下列函数:
  • front()
  • push_back()
  • pop_back()

标准容器 std::vectorstd::deque 满足这些要求。

Compare - 提供严格弱序的比较 (Compare) 类型。

[编辑] 成员类型

成员类型 定义
container_type Container [编辑]
value_compare (C++17) Compare
value_type Container::value_type [编辑]
size_type Container::size_type [编辑]
reference Container::reference [编辑]
const_reference Container::const_reference [编辑]

[编辑] 成员函数

构造 priority_queue
(公开成员函数) [编辑]
析构 priority_queue
(公开成员函数) [编辑]
赋值给容器适配器
(公开成员函数) [编辑]
元素访问
访问栈顶元素
(公开成员函数) [编辑]
容量
检查底层的容器是否为空
(公开成员函数) [编辑]
返回容纳的元素数
(公开成员函数) [编辑]
修改器
插入元素,并对底层容器排序
(公开成员函数) [编辑]
(C++11)
原位构造元素并排序底层容器
(公开成员函数) [编辑]
删除第一个元素
(公开成员函数) [编辑]
交换内容
(公开成员函数) [编辑]

成员对象

Container c
底层容器
(受保护成员对象) [编辑]
Compare comp
比较函数对象
(受保护成员对象)

[编辑] 非成员函数

特化 std::swap 算法
(函数模板) [编辑]

[编辑] 帮助类

特化 std::uses_allocator 类型特性
(函数模板) [编辑]

[编辑] 推导指引(C++17 起)

[编辑] 示例

#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