简介

pb_ds 封装了很多常用数据结构。本次介绍常用的哈希表和平衡树。
pb_ds 可以在比赛中使用，请放心食用。
为什么用 pb_ds？因为相较于 std 命名空间提供的数据结构，pb_ds 更加灵活和高效。

用法

pb_ds 需要头文件：

1
2
3
#include<ext/pb_ds/assoc_container.hpp>//容器支持,必加
#include<ext/pb_ds/hash_policy.hpp>//哈希表
#include<ext/pb_ds/tree_policy.hpp>//平衡树

同时，pb_ds 有专门的命名空间：

1
using namespace __gnu_pbds;

为了方便，下文全部默认你已使用了 __gnu_pbds 命名空间，省去 __gnu_pbds::。
这头文件又臭又长，不想背怎么办？有两种解决办法：

  • 直接用扩展库万能头
    1
    #include<bits/extc++.h>
    但是 Dev-C++ 不支持这个头文件。
  • 观察发现，ext/pb_ds/hash_policy.hpp 等是一个头文件的路径，那么我们可以去这个路径下找到头文件，直接复制文件名，具体地，对于 3 机房电脑，路径在 C:\Program Files (x86)\Dev-Cpp\MinGW64\lib\gcc\x86_64-w64-mingw32\4.9.2\include\c++\ext\pb_ds。

哈希表

pb_ds 提供两种哈希表，用法均与 std::unordered_map 相同：

1
2
gp_hash_table<T1,T2> mp1;
cc_hash_table<T1,T2> mp2;

gp_hash_table 使用开放寻址（探测法），通过线性探查或二次探查处理哈希冲突，内存占用相对较小，在哈希冲突严重时插入和删除操作性能下降明显。
cc_hash_table 使用链地址法（拉链法），通过在每个哈希桶维护链表处理哈希冲突，内存占用相对较大，在哈希冲突严重时查询性能下降明显。
个人推荐使用 gp_hash_table，它的平均性能更优。
Upd：如果你想以 std::pair 作为键（如双哈希）时，必须提供一个哈希函数和等价比较函数，因为 C++ 标准库的 std::hash 没有为 std::pair 提供哈希函数，我们要自定义一个哈希函数。

1
2
3
4
5
6
7
8
struct pair_hash{
    size_t operator()(const pair<int,int> &x)const{
        size_t h1=hash<int>{}(x.first);
        size_t h2=hash<int>{}(x.second);
        return h1^(h2<<1);
    }
};
gp_hash_table<pair<int,int>,int,pair_hash> mp;

如果你想要更强力和更高质量的哈希可以把哈希计算方式写的更为复杂，如：

1
2
3
4
5
6
7
8
9
struct pair_hash{
    size_t operator()(const pair<int,int> &x)const{
        size_t seed=0;
        seed^=hash<int>{}(x.first)+0x9e3779b9+(seed<<6)+(seed>>2);
        seed^=hash<int>{}(x.second)+0x9e3779b9+(seed<<6)+(seed>>2);
        return seed;
    }
};
gp_hash_table<pair<int,int>,int,pair_hash> mp;

由于 std::pair 已经重载了 ==，就不用我们写等价比较函数了。

平衡树

pb_ds 提供多种平衡树实现方式，一般来说，我们只需要用到平均性能最优的红黑树。
pb_ds 的平衡树与 std::set 和 std::map 相比，优势在于高度的灵活性。
我们先看看 tree 模板类，熟悉一下它的实现方式：

1
2
3
4
5
6
7
template<
    typename Key,//键类型
    typename Mapped,//值类型，默认null_type
    typename Cmp_Fn=std::less<Key>,//比较函数，默认升序
    typename Tag=rb_tree_tag,//实现方式，默认红黑树
    typename Node_Update=tree_order_statistics_node_update//节点更新策略，默认null_node_update
>

Mapped 如果设为 null_type，则无映射（即与 std::set 相同）；Node_Update 常用的是 tree_order_statistics_node_update，这个更新策略支持查询排名和第 kk 小。
例如，我们想实现一个 int 的集合和 std::string 到 int 的映射，我们可以

1
2
3
4
5
6
7
8
9
10
11
#include<set>
#include<map>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<string>
using namespace std;
using namespace __gnu_pbds;
set<int> st1;
tree<int,null_type> st2;
map<string,int> mp1;
tree<string,int> mp2;

我们举个更具体的例子，对于受害者，我们写出超短代码：

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
44
45
46
47
48
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<cstdio>
#include<utility>
template<typename T>
inline void read(T &x){
    x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
using namespace __gnu_pbds;
using namespace std;
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> st;
//为了防去重，使用pair
int n,opt,x;
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(opt,x);
        if(opt==1) st.insert(make_pair(x,i));
        else if(opt==2){
            auto it=st.lower_bound(make_pair(x,-1e9));
            if(it->first==x) st.erase(it);
        }
        else if(opt==3)
            printf("%d\n",(int)st.order_of_key(make_pair(x,-1e9))+1);
        else if(opt==4)
            printf("%d\n",st.find_by_order(x-1)->first);
        else if(opt==5){
            auto it=st.lower_bound(make_pair(x,-1e9));
            printf("%d\n",(--it)->first);
        }
        else{
            auto it=st.upper_bound(make_pair(x,1e9));
            printf("%d\n",it->first);
        }
    }
    return 0;
}

实测跑的飞快。