10-STL、位运算、常用函数库
1-STL
vector
vector是变长数组
//定义vector
vector<int>a;
//第一维长233，第二维长度动态变化
vector<int>b[233];
//自定义的结构体类型也可以保存在vector中
struct res{...};
vector<rec>c;
//函数
a.size();//返回vector的实际长度（包含的元素个数）
a.empty();//返回一个bool类型，表明vector是否为空
a.clear();//把vector清空
迭代器
迭代器是一个类对象，它允许你在容器中按顺序访问元素。通过迭代器，你可以遍历容器而不需要关心容器的具体实现细节。可以类比为“指针”，用于指向容器的元素。
//一个保存int的vector的迭代器声明方法为
vector<int>::iterator it;
a.begin() //指向集合中最小元素的迭代器。
a.end() //指向集合中最大元素的下一个位置的迭代器。
a.front() //返回vector的第一个元素，等价于*a.begin() 和 a[0]。
a.back() //返回vector的最后一个元素，等价于 a[a.size() – 1]。
a.push_back(x) //把元素x插入到vector a的尾部。
b.pop_back() //删除vector a的最后一个元素。
queue
#include 主要包括循环队列queue和优先队列priority_queue两个容器。
//定义
queue<int> q;
struct rec{…}; queue<rec> q; //结构体rec中必须定义小于号
priority_queue<int> q; // 大根堆
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
priority_queue<pair<int, int>>q;
循环队列 queue
push 从队尾插入
pop 从队头弹出
front 返回队头元素
back 返回队尾元素
优先队列 priority_queue
push 把元素插入堆
pop 删除堆顶元素
top 查询堆顶元素（最大值）
stack
//定义
stack<int> q;
struct rec{…}; stack<rec> q; //结构体rec中必须定义小于号
push 向栈顶插入
pop 弹出栈顶元素
deque
双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像vector和queue的结合。
[] 随机访问
begin/end，返回deque的头/尾迭代器
front/back 队头/队尾元素
push_back 从队尾入队
push_front 从队头入队
pop_back 从队尾出队
pop_front 从队头出队
clear 清空队列
set
#include 主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。
set<int> s;
struct rec{…}; set<rec> s; // 结构体rec中必须定义小于号
multiset<double> s;
//函数
a.size();//返回vector的实际长度（包含的元素个数）
a.empty();//返回一个bool类型，表明vector是否为空
a.clear();//把vector清空
迭代器
①begin是指向集合中最小元素的迭代器。
②end是指向集合中最大元素的下一个位置的迭代器。
③insert把一个元素x插入到集合s中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
④find在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。
⑤lower_bound查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
⑥upper_bound查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
⑦erase从s中删除迭代器it指向的元素
count返回集合s中等于x的元素个数
map
map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。
//定义
map<key_type, value_type> name;
//例如：
map<long, long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;
//函数与set类似
//h.find(x) 在变量名为h的map中查找key为x的二元组。
2-位运算
& 与
| 或
~ 非
^ 异或
左移（向左移动n位，在末尾补n个0）
右移（向右移n位，去掉末尾的n位数）
常用操作：
(1)求x的第k位（从右向左看，从0编号）数字 x >> k & 1
(2)lowbit(x) = x & -x，返回x的最后一位1
3-常用库函数
reverse 翻转
//翻转一个vector：
reverse(a.begin(), a.end());
//翻转一个数组，元素存放在下标1~n：
reverse(a + 1, a + 1 + n);
unique 去重
返回去重之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
//把一个vector去重：
int m = unique(a.begin(), a.end()) – a.begin();
//把一个数组去重，元素存放在下标1~n：
int m = unique(a + 1, a + 1 + n) – (a + 1);
random_shuffle 随机打乱
用法与reverse相同
sort
对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。
//把一个int数组（元素存放在下标1~n）从大到小排序，传入比较函数：
int a[MAX_SIZE];
bool cmp(int a, int b) {return a > b; }
sort(a + 1, a + 1 + n, cmp);
//把自定义的结构体vector排序，重载“小于号”运算符：
struct rec{ int id, x, y; }
vector<rec> a;
bool operator <(const rec &a, const rec &b) {
return a.x < b.x || a.x == b.x && a.y < b.y;
}
sort(a.begin(), a.end());
lower_bound/upper_bound 二分
lower_bound 的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound 的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
//在有序int数组（元素存放在下标1~n）中查找大于等于x的最小整数的下标：
int I = lower_bound(a + 1, a + 1 + n,. x) – a;
//在有序vector<int> 中查找小于等于x的最大整数（假设一定存在）：
int y = *--upper_bound(a.begin(), a.end(), x);