pb_ds简介

pb_ds 库全称 Policy-Based Data Structures，又称平板电视。

pb_ds 库封装了很多数据结构，比如哈希（Hash）表，平衡二叉树，字典树（Trie 树），堆（优先队列）等。

就像 vector 、 set 、 map 一样，其组件均符合 STL 的相关接口规范。部分（如优先队列）包含 STL 内对应组件的所有功能，但比 STL 功能更多。

pb_ds 只在使用 libstdc++ 为标准库的编译器下可以用。

堆

使用方法

1
2
3
4
5
6
7
8
9
10
11
12
#include <ext/pb_ds/priority_queue.hpp>
#include <bits/stdc++.h>
// 注意<ext/pb_ds/priority_queue.hpp>不在<bits/stdc++.h>内

using namespace __gnu_pbds;
//注意pb_ds和std的类名称里有重复的地方

//如果仅写这句话且不写using namespace std; ，则定义priority_queue<T, Compare, Tag, Allocator> 的时候不需要加上 __gnu_pbds ::

//如果用了using namespace std;则不必写using namespace __gnu_pbds; 并且定义 priority_queue<T, Compare, Tag, Allocator> 的时候一定要加上__gnu_pbds :: 

__gnu_pbds ::priority_queue<T, Compare, Tag, Allocator>
  • T : 储存的元素类型
  • Compare : 提供严格的弱序比较类型
  • Tag : 是 __gnu_pbds 提供的不同的五种堆，Tag 参数默认pairing_heap_tag 五种分别是：
    • pairing_heap_tag ：配对堆 官方文档认为在非原生元素（如自定义结构体/ std :: string / pair ) 中，配对堆表现最好
    • binary_heap_tag ：二叉堆 官方文档认为在原生元素中二叉堆表现最好，不过我测试的表现并没有那么好
    • binomial_heap_tag ：二项堆 二项堆在合并操作的表现要优于配对堆*但是其取堆顶元素的
    • rc_binomial_heap_tag ：冗余计数二项堆
    • thin_heap_tag ：除了合并的复杂度都和 Fibonacci 堆一样的一个 tag
  • Allocator ：空间配置器，由于 OI 中很少出现，故这里不做讲解

至少对于 OIer 来讲，除了配对堆的其他四个 tag 都是鸡肋，要么没用，要么常数大到不如 std 的，且有可能造成 MLE，故这里只推荐用默认的配对堆。同样，配对堆也优于 algorithm 库中的 make_heap() 。

构造方式

1
2
3
4
5
6
__gnu_pbds ::priority_queue<int> q1;
__gnu_pbds::priority_queue<int, greater<int> >q2;
__gnu_pbds ::priority_queue<int, greater<int>, pairing_heap_tag>q3;
__gnu_pbds ::priority_queue<int>::point_iterator id; // 迭代器
// 在 modify 和 push 的时候都会返回一个 point_iterator，下文会详细的讲使用方法
id = q1.push(1);

成员函数

  • push() : 向堆中压入一个元素，返回该元素位置的迭代器。
  • pop() : 将堆顶元素弹出。
  • top() : 返回堆顶元素。
  • size() 返回元素个数。
  • empty() 返回是否非空。
  • modify(point_iterator, const key) : 把迭代器位置的 key 修改为传入的 key ，并对底层储存结构进行排序。
  • erase(point_iterator) : 把迭代器位置的键值从堆中擦除。
  • join(__gnu_pbds :: priority_queue &other) : 把 other 合并到 *this 并把 other 清空。

下面是不同tag的各个操作对应的时间复杂度

avartar

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
#include <algorithm>
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
#include <iostream>
using namespace __gnu_pbds;
// 由于面向OIer, 本文以常用堆 : pairing_heap_tag作为范例
// 为了更好的阅读体验，定义宏如下 ：
#define pair_heap __gnu_pbds ::priority_queue<int>
pair_heap q1;  // 大根堆, 配对堆
pair_heap q2;
pair_heap ::point_iterator id;  // 一个迭代器
int main() {
  id = q1.push(1);
  // 堆中元素 ： [1];
  for (int i = 2; i <= 5; i++) q1.push(i);
  // 堆中元素 :  [1, 2, 3, 4, 5];
  std ::cout << q1.top() << std ::endl;
  // 输出结果 : 5;
  q1.pop();
  // 堆中元素 : [1, 2, 3, 4];
  id = q1.push(10);
  // 堆中元素 : [1, 2, 3, 4, 10];
  q1.modify(id, 1);
  // 堆中元素 :  [1, 1, 2, 3, 4];
  std ::cout << q1.top() << std ::endl;
  // 输出结果 : 4;
  q1.pop();
  // 堆中元素 : [1, 1, 2, 3];
  id = q1.push(7);
  // 堆中元素 : [1, 1, 2, 3, 7];
  q1.erase(id);
  // 堆中元素 : [1, 1, 2, 3];
  q2.push(1), q2.push(3), q2.push(5);
  // q1中元素 : [1, 1, 2, 3], q2中元素 : [1, 3, 5];
  q2.join(q1);
  // q1中无元素，q2中元素 ：[1, 1, 1, 2, 3, 3, 5];
}