C++ priority_queue 学习笔记

本文整理自:https://zh.cppreference.com/w/cpp/container/priority_queue

priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数的插入与释出。可用用户提供的 Compare 更改顺序,例如,用 std::greater<T> 将导致最小元素作为 top() 出现。定义于头文件<queue>

1
2
3
4
5
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;

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

  1. 成员函数

    1
    2
    3
    4
    5
    6
    7
    8
    // constructor
    priority_queue():priority_queue(Compare(), Container()) {} // 默认构造函数
    priority_queue( const Compare& compare, const Container& cont ); // 用 cont 的内容复制构造底层容器 c, compare 的内容复制构造比较函数对象 comp
    priority_queue( const priority_queue& other ); // 复制构造函数
    priority_queue( priority_queue&& other ); // 移动构造函数

    // deconstructor
    ~priority_queue()
  2. 元素访问

    1
    const_reference top() const; // 返回到 priority_queue 顶元素的引用。此元素将在调用 pop() 时被移除。若使用默认比较函数,则返回的元素亦为优先队列中最大的元素。
  3. 容量

    1
    2
    bool empty() const; // 检查底层容器是否为空,即是否 c.empty()
    size_type size() const; // 返回底层容器中的元素数
  4. 修改器

    1
    2
    3
    4
    5
    6
    7
    void push( const value_type& value ); // 推给定的元素 value 到 priority_queue 中

    void emplace( Args&&... args ); // 推入新元素到 priority_queue ,原位构造元素,即不进行移动或复制操作

    void pop(); // 从 priority_queue 移除顶元素

    void swap( priority_queue& other ) ); // 交换容器适配器与 other 的内容。
  5. 成员对象

    1
    2
    Container c // 底层容器
    Compare comp // 比较函数对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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);
}

// output
// 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++

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×