vector

先导

变长数组，倍增的思想

初始化

• vector<int> a;
• vector<int> a(n); 　 // 定义长度为 n
• vector<int> a(n, x); 　 // 定义长度为 n 且每个元素值为 x

支持函数

• size()
• empty() 　 // 这两个函数所有容器都有 -> o(1)
• clear() 　// 清空，不是所有容器都有
• front()/back()
• push_back()/pop_back()
• begin()/end()
• []
• 支持比较运算 　 // 根据两个 vector 从前到后元素大小比较，长度不影响。
• erase()

倍增思想

操作系统的思路：系统为某一程序分配空间所需的时间基本与空间大小无关 -> 与申请次数有关！！！
例如申请 1000 个长度为 1 的数组的时间是申请 1 个长度为 1000 的数组的 1000 倍。

上述内容就给了我们一个原则，就是变长数组要尽量减少申请空间的次数。
-> 倍增思想 -> 例如一开始申请 n 大小，用完之后就申请 2n 个空间，并把前 n 个从旧的数组里 copy 来。

知道了倍增思想之后，来看具体：
当我们保存 10^6 大小的数组时，vector 要复制多少次呢？
答：1 + 2 + 4 + … + 5*10^5 = 10^6 // 第一次复制一个，第二次复制两个，…… ；申请的次数是 logn 。
因为加在一块儿大概是 10^6，所以当我们插入 10^6 个元素大概就要复制一次，所以每次插入操作应该是 o(1) 的（平均情况）。

pair

创建

• p = make_pair(first, second)
• p = {first, second}

支持函数

• 支持比较运算：以 first 作为第一关键字，second 为第二关键字（字典序）

额外用法

pair<int, pair<int, int>>

string

先导

字符串，常用函数有：substr(), c_str()

支持函数

• 支持 +、比较 操作
• size()/length()
• str.empty()
• str.clear()
• str.substr(u， len) -> 返回 str 从 u 开始长度为 len 的子串（len > size -> 则到 size 截至；没有 len -> 返回 u 到最后）
• to_string
• printf(“%s”, str.c_str());
• find()

queue

支持函数

• que.size()
• que.empty()
• que.clear() -> 想清空 -> 直接重新构造一个
• que.push() -> 向队尾插入一个元素
• que.pop() -> 弹出队头元素
• que.front() -> 返回队头元素
• que.back() -> 返回队尾元素

priority_queue

先导

includ<queue>
优先队列，其实是个堆，默认是大根堆
常用函数：push()、top()、pop()

支持函数

• heap.clear()
• heap.push() -> 插入一个元素
• heap.top() -> 返回堆顶
• heap.pop() -> 弹出堆顶元素

常用操作

• 当需要一个小根堆时：
  方法一：heap.push(-x) -> 插入负数
  方法二：直接定义成小根堆 -> priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> heap;

stack

支持函数

• stk.size()
• stk.empty()
• stk.clear()
• stk.push()
• stk.pop()
• stk.top()

deque

先导

双端队列 -> 队头队尾都可以插入删除，并且支持随机访问 -> 等于加强版的 vector
但速度很慢 -> 比一般数组慢好几倍 -> 一般不用

支持函数

• deq.size()
• deq.empty()
• deq.clear()
• deq.front()
• deq.back()
• deq.push_pack()/pop_back()
• deq.push_front()/pop_front()
• []

set、map、multiset、multimap

先导

<set> <map>
都是基于平衡二叉树（红黑树，是平衡二叉树的一种），动态维护有序序列。

set/multiset

能/不能有重复元素
所有操作都是 o(logn)

支持函数、操作

• size()
• empty()
• clear()
• st.insert()
• st.find() -> 不存在返回 end()
• st.count() -> 某一个数的个数 -> 只有0和1两种情况
• erase()
  1. 输入是x，删除所有 x -> o(k + longn)，k 是 x 的个数
  2. 输入是一个迭代器，删除这个迭代器。
• lower_bound()/upper_bound()

map/multimap

• insert()
• erase()
• find()
• [] -> o(logn)
• lower_bound()/upper_bound()

unordered_set、unordered_map、unordered_multiset、unordered_multimap

和上面类似，增删改查时间复杂度都是 o(1) 的
但不支持 lower_bound() 和 upper_bound()，迭代器的 ++、–

bitset

先导

压位