（二十八）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}

对，就是这玩意：集合
他有两种特征：

1. 不可重复
2. 可以自排序

在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容器中的基本函数

1. T.insert(x)：在容器T中填入值x，如果x确实不在容器中，那么往容器中放入x，否则无事发生
2. T.erase(x)：如果容器T中确实存在元素x，那么删除那个元素，否则无事发生
3. T.erase(it)：如果容器T中确实存在迭代器为it的元素，那么删除这个迭代器，否则运行错误（RE）
4. T.count(x)：返回x的出现次数（也就是有返回1，没有返回0，因为set容器有去重特性），返回值类型为size_t
5. T.find(x)：返回x在容器的迭代器，没有这个元素返回T.end()
6. T.size()：返回值类型size_t，函数返回容器中有多少个元素
7. T.empty()：如果容器是空的，返回1，否则返回0（bool类型）
8. T.begin()：返回容器第一个元素的迭代器
9. T.end()：返回容器最后一个有效元素的下一个元素NULL的迭代器
10. 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）
• 三十四：电脑基础知识
• 三十五：链表
• 三十六：树
• 三十七 ：图
  …