（二十八）STL set（集合）
set容器是什么？相信学python的都知道
T = set([6,5,1,2,3,4,4,5,3,2,1])
print(T) # 输出 {1, 2, 3, 4, 5, 6}
学过数学的也知道
{
1
,
2
,
3
,
4
,
5
,
6
}
\{1, 2, 3, 4, 5, 6\}
{1,2,3,4,5,6}
对，就是这玩意：集合
他有两种特征：
- 不可重复
- 可以自排序
在C++和Python还有一种特征：不可随机访问。什么叫随机访问？像矢量数组（vector）还是静态数组它们都有这个语法
Array[index] //返回Array的第x项
到了映射容器（set），还是老老实实的用迭代器（iterator）吧。一样的，他的迭代器类型是这个
set<类型>::iterator
一样的遍历方法
for(set<T>::iterator it=T.begin(); it!=T.end(); it++)
cout << *it << ' ';
set容器怎么定义？和vector一样
#include <set> //头文件
set<类型> T;
现在这些是set容器中的基本函数
T.insert(x)：在容器T中填入值x，如果x确实不在容器中，那么往容器中放入x，否则无事发生T.erase(x)：如果容器T中确实存在元素x，那么删除那个元素，否则无事发生T.erase(it)：如果容器T中确实存在迭代器为it的元素，那么删除这个迭代器，否则运行错误（RE）T.count(x)：返回x的出现次数（也就是有返回1，没有返回0，因为set容器有去重特性），返回值类型为size_tT.find(x)：返回x在容器的迭代器，没有这个元素返回T.end()T.size()：返回值类型size_t，函数返回容器中有多少个元素T.empty()：如果容器是空的，返回1，否则返回0（bool类型）T.begin()：返回容器第一个元素的迭代器T.end()：返回容器最后一个有效元素的下一个元素NULL的迭代器T.clear()：清空容器所有值
在C++中基于容器迭代器的遍历给出了一种新的for循环用法，名叫foreach。我们来对比一下
用普通for循环遍历
for(auto it=T.begin(); it!=T.end(); it++)
cout << *it << ' ';
是不是很复杂
用foreach方法遍历
for(auto it: T)
cout << it << ' ';
简洁了许多吧！
用python来说这个是普通for循环
for i in range(0, len(T)):
print(list(T)[i], end=' ')
这个就是foreach循环了
for i in T:
print(i, end=' ')
总之来说不管是C/C++还是python，foreach都是一个良心玩意，直接把复杂的for循环简化了
对了，set容器默认从小到大，怎么变为从大到小呢？
这是set容器定义时的模版
template<
class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>
> class set {
...
};
看不懂？没事
第一行表示它的类型（一般用class类型表示这个主类的类型，也可以把class替换为typename）
第二行表示它的排序器，默认为std::less<Key>，说明这个就是从小到大的排序器
第三行不用管，现在用不上
我们可以发现比较器类型是class（也可以用struct），但一般排序用的函数统一类型_Compare，怎么办呢？
我们可以用一个结构体来进行封装
struct cmp {
bool operator() (int a, int b) {
return a > b;
}
};
再在定义时调用这个模版
set<int,cmp> T;
另外使用迭代器时别把模版忘了
set<int>::iterator //错误
set<int,cmp>::iterator //正确
只不过我们一般用这个
auto //兼容C++11版本
预览：
- 二十一：联合体（union）
- 二十二：类（class）
- 二十三：高精度运算
- 二十四：算法进阶
- 二十五：递归
- 二十六：vector容器
- 二十七：递推
- 二十八：
set容器 - 二十九：
map容器 - 三十：二分查找（
Binary Search, BS） - 三十一：前缀和与差分
- 三十二：栈（
stack） - 三十三：队列（
queue）和双向队列（deque） - 三十四：电脑基础知识
- 三十五：链表
- 三十六：树
- 三十七 ：图
…