8.C++中的STL(标准模板库)
（1）vector, 变长数组，倍增的思想
-
头文件
#include <vector> -
size() 返回元素个数
-
empty() 返回是否为空
-
clear() 清空
-
front()/back() 返回首、尾元素
-
push_back()/pop_back() 压入、弹出末尾元素
-
begin()/end() begin()=a[0]，end()=a[size]
-
支持比较运算，如a(3,4)，b(3,5)，a<b，即按字典序
（2）pair<int, string> 可以存储一个二元组
- first, 第一个元素
- second, 第二个元素
- 支持比较运算，以first为第一关键字，以second为第二关键字，按字典序
**（3）string，**字符串
-
#include <string> -
size()/length() 返回字符串长度
-
empty() 判断为空
-
clear() 清空
-
substr(起始下标，(子串长度)) 返回子串
-
c_str() 返回字符串所在字符数组的起始地址
（4）queue, 队列
-
#include <queue> -
size()
-
empty()
-
push() 向队尾插入一个元素
-
front() 返回队头元素
-
back() 返回队尾元素
-
pop() 弹出队头元素
（5）priority_queue, 优先队列，即堆，默认是大根堆
-
#include <queue> -
size()
-
empty()
-
push() 插入一个元素
-
top() 返回堆顶元素
-
pop() 弹出堆顶元素
-
定义成小根堆的方式：priority_queue<int, vector
, greater > q;
（6）stack, 栈
-
#include <stack> -
size()
-
empty()
-
push() 向栈顶插入一个元素
-
top() 返回栈顶元素
-
pop() 弹出栈顶元素
（7）deque, 双端队列
-
#include <deque> -
size()
-
empty()
-
clear()
-
front()/back()
-
push_back()/pop_back()
-
push_front()/pop_front()
-
begin()/end()
（8）set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列 size() empty() clear() begin()/end() ++, — 返回前驱和后继，时间复杂度 O(logn)
set/multiset set去重，mulset可以有重复元素
- insert() 插入一个数
- find() 查找一个数
- count() 返回某一个数的个数
- erase()
- (1) 输入是一个数x，删除所有x O(k + logn)
- (2) 输入一个迭代器，删除这个迭代器
- lower_bound()/upper_bound()
- lower_bound(x) 返回大于等于x的最小的数的迭代器
- upper_bound(x) 返回大于x的最小的数的迭代器
**map/multimap **
- insert() 插入的数是一个pair
- erase() 输入的参数是pair或者迭代器
- find() 查找一个数
- map可以像数组一样使用 ：如map<string,int> a; a[“string”]=1；(注意multimap不支持此操作。 时间复杂度是 O(logn))
- lower_bound()/upper_bound()
（9）unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
- 和上面set, map, multiset, multimap类似，增删改查的时间复杂度是 O(1)
- 不支持 lower_bound()/upper_bound()， 迭代器的++，—
（10）bitset, 圧位，可以省8位空间，一个字节当8个字节用 bitset<10000> s;
-
支持各种位运算 ~, &, |, ^、
>>, <<、==, != -
count() 返回有多少个1
-
any() 判断是否至少有一个1
-
none() 判断是否全为0
-
set() 把所有位置成1
-
set(k, v) 将第k位变成v
-
reset() 把所有位变成0
-
flip() 等价于~
-
flip(k) 把第k位取反