常用 STL 整理
vector
可变长数组，变长是基于 倍增 的思想
初始化
vector<typename> name;
vector<int> a(n); // 初始化大小为n的数组，0~n-1
vector<int> a(n,3); //初始化大小为n的数组，所有值均为3
vector<vector<int> > name; // 定义二维的vector，两维都能动态变长
vecotr<int> a[n]; // 第一维已经固定，第二维才是vector访问
(1) 通过下标随机访问 范围是 0 ~ size() - 1
(2) 通过迭代器访问 iterator (类似于指针)
vector<int>::iterator it;
通过 *it 来访问元素//支持++，--- 其中 v[i] 和 *(v.begin() + i) 是等价的
常用函数
push_back(); // 尾端插入 O(1)
pop_back(); // 尾端删除 O(1)
size(); // 返回元素个数 O(1) ,返回的是 unsigned 类型
clear(); // 虚假的清空 不能真正的清空元素个数，放弃使用，直接新定义一个重名的，当做清空
v = vector<int>(); // 真正的清空
insert(it,x); // 在迭代器 it 处，插入一个元素 x, O(n)
erase();// 删除单个元素 O(n)
erase(v.begin(),v.end());// 删除区间的元素 O(n)
// 支持比较运算，按字典序来比较pair
可以看作一个内部有两个元素的结构体，元素类型任意指定
初始化
pair<typename1,typename2> p;// typename 可以为任意类型
pair<int,pair<int,int> > p; // pair支持多重嵌套
//临时构造pair
p = make_pair("123",123);
p = {"123",123}; // C++ 11 写法访问
p.first; // 第一个关键字
p.second; // 第二关键字用途
1.支持比较运算，排序的时候，以first为第一关键字，second为第二关键字
2.用来代替二元结构体及其构造函数
3.作为map的键值对来进行插入
string
C++ 封装好的字符串
初始化
string s = "123";访问
c_str() 可以返回 string 类型的字符串存储的起始地址
通过迭代器访问 string::iterator it;
s[i]; // 像数组一样访问常用函数
size() 与 length() 基本相同，O(1);
支持字典序比较 <=,<,>=,>....
insert(pos,string);// 在pos位置，插入string字符串 O(n)
erase();// O(n)
substr(pos,len); // 返回从 pos 开始，长度为 len 的字符串 O(len)
str1.find(str2); // 返回str2 在 str1 中第一次出现的位置，如果没有出现，返回 npos O(n^2)
string::npos;// 是一个常数 -1
replace(); // 区间替换字符串
+ // 拼接queue
queue , push(),pop(),front()
priority_queue
// 优先队列，堆,默认是大根堆
stack
// 栈
deque
// 双端队列，随机访问
set ， multiset（可以插入重复元素）,
map，multimap
// 平衡树，基于平衡二叉树（红黑树 （平衡二叉树的一种）），hash
动态维护一个有序序列
unordered_set,unodered_map,unordered_multiset,unordered_multimap // 基于hash表
和上面都是类似的，绝大多数操作都是 O(1) 的，都是无序的，
不支持 upper_bound,lower_bound
bitset// 压位，
list // 链表，用的不多
参考
《算法笔记》
《算法竞赛入门经典》
《算法竞赛进阶指南》