1,集合set
原理：二叉搜索树O(log n)
优点：*集合内元素唯一 *系统自动按值排序 *元素查找方便
操作： * set<type>A; 定义一个type类型的集合A
* 基本函数：
A.insert(item); --- 存入
A.erase(item); --- 删除 // map既可以通过关键字删除 m.erase(1);
亦可借用迭代器 iter=m.find(1);m.erase(iter);
A.clear(); --- 删除全部
A.empty(); A.size();
A.begin() \ A.end() --- 返回set容器的第\最后一个迭代器
A.max_size() ---- 返回可包含的元素的最大个数
* 迭代器（iterator） set<int>::iterator iter; iter是变量
* 比较查找(以下函数复杂度都是logn)：
A.lower_bound(k); 返回值不小于k的第一个迭代器元素
A.upper_bound(k)；
A.find(k); ---- iter=A.find(k); if（iter！=A.end()) cout<<*iter;
如果 find() 函数找到了元素 k ,则返回 k 在集合中的位置，否则 iter 指向集合的 end()，*iter等于所指向的值;
2.bitset类型
* 头文件： #include<bitset>
* 定义： bitset<MAXN>s; 定义了一个长为 MAXN 的bitset，每一位只有1和0两种情况
eg: bitset<1000>s;
----- 长为1000bit的bitset数组s,有1000位，默认每位都为0，
bitset 看成是一个可以随便定义长度的二进制串，他重载了所有的位运算，并且每一位只占 1 bit
* 函数： s.count() 返回1的个数
s.reset() 重置，全部变成0
s.set() 全部变成1
s.set(p,x) 将第p+1位变成x （bitset从第0位开始）
---- 也可以只写参数p,即默认变成1，reset()函数也有同样操作，但是默认变0
s.flip() 全部取反 --- s.flip(p)如上
习题：状态dphttps://ac.nowcoder.com/acm/problem/17193
dalao的，可以学习一下：
https://www.cnblogs.com/zwfymqz/archive/2018/04/02/8696631.html
3.队列queue（先进先出）
1.操作： * queue<type>q;
q.push(item) 存入
q.front() \ q.back() 返回队首队尾元素
q.pop()
q.queue<point>() 初始化队列q为空
2.优先队列：
* 基本操作相同，可自定义优先级
priority_queue<Type（数据类型）, Container（容器类型）, Functional（比较方式）>q;
两种队列：
//升序队列，小顶堆 priority_queue <int,vector<int>,greater<int> > q; //降序队列，大顶堆 priority_queue <int,vector<int>,less<int> >q; //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
大顶堆（默认情况:priority_queue <int> a） //优先输出最大值
https://www.cnblogs.com/huashanqingzhu/p/11040390.html（有更详细介绍）
* 优先队列存储结构体比较大小：
less函数只能重载 < ，优先输出最大值，比较中值更小的越往堆底放
greater只函数重载 > ，优先输出最小值
//用自定义类型做优先队列元素
struct node{ int x,y,val,to; bool operator<(const node &t)const{ return val>t.val; //该比较中，值越大的越小 } }; priority_queue<node,vector<node>,less<node> >q; //less优先输出最大值
3.双端队列deque
#include<deque> deque<int>q; //定义
支持高效的插入和删除头部/尾部元素
基本函数：
q.push_back() q.push_front() //插入首尾元素
q.pop_back() q.pop_front() //删除首尾元素
q.front() q.back() //首尾元素的引用
q.clear() q.erase() (一般函数都有，不再列举)
4.关联容器map
* 一对一，快速查找，
* 元素是自动按Key升序排序，所以不能对map用sort函数
* map<type1,type2>m; type1为关键字（不可修改），type2为关键字的值
---- map<string,int>m; string str="memory";
* 自动建立 Key － value 的对应，key和value可以是任意你需要的类型，根据key值快速查找记录，查找的复杂度基本是Log(N)
操作： * 插入：m[str] = 1; //（亲试）在没有赋值给m[str]时，m[str]默认等于0，可以直接m[str]++，不需要用find()先查找有没有;
* 迭代器：map<string,int>:: iterator iter;
* 基本函数：
A.insert(item); --- 存入 // m.insert({"andrea",1});
A.erase(item); --- 删除（logn） // map既可以通过关键字删除 m.erase(1);
亦可借用迭代器 iter=m.find(1);m.erase(iter);
A.clear(); --- 删除全部
A.empty(); A.size();
A.begin() \ A.end() --- 返回set容器的第\最后一个迭代器
* 比较查找(以下函数复杂度都是logn)：
A.lower_bound(k); 返回值不小于k的第一个迭代器元素
A.upper_bound(k)；
A.find(k); ---- iter=A.find(k); if（iter！=A.end()) cout<<iter->first<<' '<<iter->second<<endl;
如果 find() 函数找到了元素 k ,则返回 k 在集合中的位置，否则 iter 指向集合的 end()，*iter等于所指向的值;
* 循环：for(iter=m.begin();iter!=m.end();iter++)
if( iter->second > 0 ) cout<<iter->first<<iter->second<<endl;
https://blog.csdn.net/codertcm/article/details/81239487（更详细介绍）
5.字符串string
读入： cin>>s;读入一个串
getline(cin,s);读入一整行，默认以换行符结束，需要getchar();
操作： * 查找函数 find() --- s1.find ( "ab" )；若没找到该子串则返回-1
* 反转函数 reverse() ---(函数头文件）alogrithm,该函数会改变原来的数组，不会创建新的数组
strstr（）和strrve()是C语言的函数，不可混用
* 区间替换 replace（t1,t2,string） ---- 从t1到t2位置的n个字符替换为string字串
单个替换 str[i]="*";
* 加减法：str+=s[i]，减法：s=s.erase(t1,n) ---- 从t1位置开始从串s删去2个字符,erase()复杂度高
* 字串排序： string s; sort(s.begin(),s.end()) --- 一个字符串内的所有字符按ASCII码值排序
| string s[100000]; sort(s,s+n); ---- string数组s内的n个串按ASCII码值排序
* 提取字串：s1=s.substr(t1,n) --- 从s中提取从t1位置开始的连续n个数
6.next_permutation (全排列）
** 按字母表顺序生成给定序列的下一个较大的序列，直到整个序列为减序为止
复杂度 O(n)
int a[];
do
{
}
while(next_permutation(a,a+n));
可产生数组a的 1~n 全排列
7.STL二分查找函数
1）binary_search(a,a+n,element) ,查找a数组中是否存在element元素，n表示数组长度
2）lower_bound(a,a+n,element) ,返回第一个大于等于element的迭代器
3）up_bound(a,a+n,element) ,返回第一个大于element的迭代器
---- 2、3应用：int badge=up_bound(a,a+n,element)-a; 表示第一个大于element的数在a数组中的pos。
8.几点
1）set 、map采用红黑树（平衡二叉树）实现，其插入，删除，查找函数相同，用法相似，且都是logn复杂度
练习：