c++-pbds标准库-自带多种数据结构-考试可用

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

简介

你想要在考场上取得高分，但是苦于背不下来模板？

想要快速实现一个样例程序检验正确性？

没问题，pbds都可以做到，而且绝对不会让您失望！

而且，pbds是ccf明确允许使用的！

前置知识

在使用pbds的模板时，请确保您最好之前已经打过一遍模板了，否则不建议使用。

模板毕竟只是实现算法的工具，而非全部。

讲解

include指令

pbds是c++14的功能，所以请确保您的编译器支持c++14

$ g++ 程序.cpp --std=c++14 -o run && time ./run

首先，要使用任意pbds结构，需要引入

#include<ext/pb_ds/assoc_container.hpp> // 注意！.hpp！

然后是分别的：

#include<ext/pb_ds/trie_policy.hpp> // trie树（字典树）
#include<ext/pb_ds/hash_policy.hpp> // 哈希表
#include<ext/pb_ds/tree_policy.hpp> // 平衡树

你要是嫌懒也可以用万能扩展头（极度不推荐，不知道行不行）：

#include<bits/extc++.h>

这里面字典树不推荐使用（stl的常数都好不到哪去），哈希表和平衡树都比较推荐。

平衡树 tree

__gnu_pbds::tree<
    Type, // Type换成你的类型
    __gnu_pbds::null_type, // 无映射
    std::less<Type>, // 排序规则
    __gnu_pbds::rb_tree_tag or __gnu_pbds::splay_tree_tag, // 推荐使用rbtree，更稳定
    __gnu_pbds::tree_order_statistics_node_update> // 节点更新方式
    tr;

操作（这里给出类的简略定义）：

template<class Type>
class Tree{
	void insert(Type);        //插入
	void erase(Type);         //删除
	int order_of_key(Type);   //求排名
	Type* find_by_order(int); //根据排名找数
	Type* upper_bound(Type);  //后继
	Type* lower_bound(Type);  //前驱
}

但是！！！

理想很丰满，现实很骨感。

平衡树里的元素是不可以重复的。

那我们如何让它不重复还可以排序大小呢？

很显然，使用 pair 。

因为 pair 的第二个元素是次要的，不影响排序，只需要在 first 存值， second 存下标即可。

__gnu_pbds::tree<
    std::pair<int,int>, // Type换成你的类型
    __gnu_pbds::null_type, // 无映射
    std::less<std::pair<int,int>>, // 排序规则
    __gnu_pbds::rb_tree_tag or __gnu_pbds::splay_tree_tag, // 推荐使用rbtree，更稳定
    __gnu_pbds::tree_order_statistics_node_update> // 节点更新方式
    tr;

然后就是秒杀 P3369 的代码：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> tr;

int n, mode, x;
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
  {
    scanf("%d%d", &mode, &x);
    if (mode == 1)
      tr.insert({x, i});
    else if (mode == 2)
      tr.erase(tr.lower_bound({x, 0}));
    else if (mode == 3)
      printf("%d\n", tr.order_of_key({x, 0}) + 1);
    else if (mode == 4)
      printf("%d\n", tr.find_by_order(x - 1)->first);
    else if (mode == 5)
      printf("%d\n", ((--tr.lower_bound({x, 0}))->first));
    else if (mode == 6)
      printf("%d\n", tr.upper_bound({x, 2147483647})->first);
  }
}

哈希表 hash_table

哈希表有两种实现方法，查探法和拉链法，这里不细讲，复杂度都是玄学，均摊 $O(1)$ 。

但是查探法会比拉链快一点。

cc_hash_table<Type1, Type2> mp1;
gp_hash_table<Type1, Type2> mp2;

使用很简单，和 map 一样就行，常数会比 unordered_map 大一点，主要是在 cf 上代替 unordered_map 使用。