关于pb_ds容器和一些STL

## STL
### set
它可以相对较快的处理元素，并且把它们排序。

#### 1.定义
```c
#include <set>
using namespace std;
set<int> s;
int main()
{

}
```
关于相关的迭代器
```
set<int/*类型*/> :: iterator it/*迭代器的名称*/;
```

#### 2.相关操作
这里引用 旧林墨烟 在csdn上博客的一些内容，并且添加一些解释。
```c
insert() //插入元素（值） O(logN)
count() //判断容器中是否存在某个元素（值） O(1)
size() //返回容器的尺寸，也可以元素的个数 O(1)
erase() //删除集合中某个元素（迭代器或者具体的值） O(logN)（两个迭代器就是删除从it1到it2，左闭右开）
clear() //清空集合 O(N)
empty() //1表示set为空，否则不为空 O(1)
begin() //返回第一个节点的迭代器 O(1)
end() //返回最后一个节点加1的迭代器 O(1)
find() //查找某个指定元素的迭代器(值) O(1)
lower_bound() //二分查找第一个不小于某个值的元素的迭代器 O(logn)
upper_bound() //二分查找第一个大于某个值元素的迭代器O(logn)

```
set<string>按照字符串的字典序排序，这里有一份亲测代码
```c
#include <bits/stdc++.h>
using namespace std;
#define It set<string> :: iterator
set<string> s;
string a;
int main()
{
while(cin >> a)
{
s.insert(a);
s.erase(s.find(a));
for (It it = s.begin(); it != s.end(); ++ it) cout << *it << " ";
putchar('\n');
}
return 0;
}
```
当然了你问我set里面有重复的元素那怎么办。

**小技巧**
set使用pair类型，会按照第一关键字从小到大，第二关键字从小到大进行排序，我们让第二关键字全部都不一样就可以了。不仅是set，其它不能重复但是在相关实现中又存在重复的容器中可以使用。
#### 3.进阶
(1)从大到小对set进行排序
```
set<int, greater<int> > s;
```
(2)结构体内部排序
```c
struct node
{
int x, y;
bool operator < (const node &a) const
{
if(a.x == x) return y < a.y;
return x < a.x;
}
/*写法二
friend bool operator < (node a, node b)
{
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}*/
};
set<node> s;
```
补充一下结构体的封装函数

```c
node (int a, int b) {x = a, y = b; }
```
如果要给一个node的x和y赋值的话就是
```c
node qwq = node(1, 2);//随便两个值
```

当然set对于我来说最大的用处是写那个什么珂朵莉还是珂莉*（老司机树，骗分使我快乐）。详见Astatinear的文章（洛谷居民，我......）。这里怎么使用的就不详细说了。
### unordered_map
用Dev的时候记得使用c++11或者c++14。

相较于map而言，它的查找更加快速。而且key1和key2是互相一一对应的。

有一份遍历其中所有元素和关于如何定义的代码。
```c
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int main()
{
for (auto it = mp.begin(); it != mp.end(); ++ it) ;
}
```
## pb_ds
pb_ds 全称是policy based date structures，俗称是平板电视。
其实Ca也不太明白这些东西。只是求助过大家怎么用set模拟权值线段树的功能。大家都说不可以，建议启用pb_ds.
pb_ds里面包含了很多东西，例如hash表，平衡树以及功能更强大优先队列。
### 前言
启用任何pb_ds之前一定要加上
```c
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
```
的头文件
### tree
也就是平衡树。
头文件需要在前言的基础上加上
```c
#include <ext/pb_ds/tree_policy.hpp>
```
#### 一些操作
以下来源于幻想繁星的blog，Ca为了方便复习，于是粘贴过来。
insert(x) 向树中插入一个元素 x。

erase(x) 从树中删除一个元素/迭代器 x。

order_of_key(x) 返回 x 以 Cmp_Fn 比较的排名。

find_by_order(x) 返回 Cmp_Fn 比较的排名所对应元素的迭代器。

lower_bound(x) 以 Cmp_Fn 比较做 lower_bound 返回迭代器。

upper_bound(x) 以 Cmp_Fn 比较做 upper_bound 返回迭代器。

join(x) 将 x 树并入当前树，前提是两棵树的类型一样，x 树被删除。

split(x,b) 以 Cmp_Fn 比较，小于等于 x 的属于当前树，其余的属于 b 树。

empty() 返回是否为空。

size() 返回大小。

至此，感谢幻想繁星（洛谷居民）为Ca提供了学习帮助。

下面是“**普通平衡树**”的有关代码
```c
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
const int inf = 0x3f3f3f3f;
tree <pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> t;
int n, opt, x, cnt = 0;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
{
scanf("%d %d", &opt, &x);
if(opt == 1) t.insert({x, ++ cnt});
else if(opt == 2) t.erase(t.lower_bound({x, 0}));
else if(opt == 3) printf("%d\n", t.order_of_key({x, 0}) + 1);
else if(opt == 4) printf("%d\n", t.find_by_order(x - 1)->first);
else if(opt == 5) printf("%d\n", t.find_by_order(t.order_of_key({x, 0}) - 1)->first);
else if(opt == 6) printf("%d\n", t.find_by_order(t.order_of_key({x, inf}))->first);
}
}
```
### hash表
```c
cc_hash_table<int, int> m;//拉链法
gp_hash_table<int, int> m;//探测法
```
拉链法就是遇见相同的往这个位置上面加。
探测法就是往后面移动。

关于“**查字典**”代码
```c
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
gp_hash_table<string, int> vs;
int n, num;
string s;
int main()
{
scanf("%d", &n);
while(n --)
{
cin >> s >> num;
vs[s] = num;
}
scanf("%d", &n);
while(n --)
{
cin >> s;
printf("%d\n", vs[s]);
}
return 0;
}
```

有问题一定要给Ca及时指出。谢谢OvO啦。