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);