魔法之 pb_ds

pb_ds 简介 与 使用

Part1

pb_ds 是一个基于策略的模板库

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

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

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

由于 pb_ds 库的主要内容在以下划线开头的 __gnu_pbds 命名空间中，在 NOI 系列活动中的合规性一直没有确定。

2021 年 9 月 1 日，根据 《关于 NOI 系列活动中编程语言使用限制的补充说明》，允许使用以下划线开头的库函数或宏（但具有明确禁止操作的库函数和宏除外），在 NOI 系列活动中使用 pb_ds 库的合规性有了文件上的依据。

以上内容主要来自 OIwiki

pb_ds 包含的头文件有如下几个

#include <ext/pb_ds/assoc_container.hpp>  //容器库
#include <ext/pb_ds/tree_policy.hpp>      //各种树 
#include <ext/pb_ds/priority_queue.hpp>   //优先队列
#include <ext/pb_ds/hash_policy.hpp>       //哈希表

Part2 平衡树

所需头文件

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

__gnu_pbds ::tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag,Node_Update = null_tree_node_update,Allocator = std::allocator<char> >

Key : 储存的元素类型，如果想要存储多个相同的 Key 元素，则需要使用类似于 std::pair 和 struct 的方法，并配合使用 lower_bound 和 upper_bound 成员函数进行查找

Mapped: 映射规则（Mapped-Policy）类型，如果要指示关联容器是 集合，类似于存储元素在 std::set 中，此处填入 null_type，低版本 g++ 此处为 null_mapped_type；如果要指示关联容器是 带值的集合，类似于存储元素在 std::map 中，此处填入类似于 std::map<Key, Value> 的 Value 类型

Cmp_Fn: 关键字比较函子，例如 std::less

Tag: 选择使用何种底层数据结构类型，默认是 rb_tree_tag。__gnu_pbds 提供不同的三种平衡树，分别是：
rb_tree_tag：红黑树，一般使用这个，后两者的性能一般不如红黑树
splay_tree_tag：splay 树
ov_tree_tag：有序向量树，只是一个由 vector 实现的有序结构，类似于排序的 vector 来实现平衡树，性能取决于数据想不想卡你

Node_Update：用于更新节点的策略，默认使用 null_node_update，若要使用 order_of_key 和 find_by_order 方法，需要使用 tree_order_statistics_node_update

Allocator：空间分配器类型 一般不用管

---

pb_ds 的平衡树 的成员函数

使用例子 构造一棵可以按元素排名查找的存储字符串的平衡树

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;
__gnu_pbds::tree<std::string,                                  // key值__gnu_pbds::null_type,                        /*这是映射到的值，我们现在不需要，所以填null_type*/std::less<std::string>,                       /*比较规则，对于自己写的结构体，可以使用仿函数的形式*/__gnu_pbds::rb_tree_tag,                      /*树的类型 红黑树一般为最优*/__gnu_pbds::tree_order_statistics_node_update /*节点更新类型*/>  k;int main()
{int cnt = 0;k.insert("man");k.insert("what");k.insert("can");k.insert("i");k.insert("say");// 树上元素 {"can","i","man","say","what"}auto it = k.find("can");cout << *it << endl;it = k.find_by_order(0);//按排名查找 key 值cout << *it << endl;it = k.find_by_order(1);cout << *it << endl;it = k.find_by_order(2);cout << *it << endl;//输出结果//can//i//manint f=k.order_of_key("man");//按key值查找排名cout<<f<<endl;//输出结果 2for(auto kk=k.begin();kk!=k.end();kk++)//用迭代器遍历{cout<<(*kk)<<" ";}//输出结果 can i man say whatreturn 0;
}