STL 容器以及各函数及其复杂度

主要是实质、函数、性质。
如果没有特殊提出，那么是常数复杂度。

vector

相当于变长数组。

• 支持随机访问（可以直接查询 \(v_i\)），但是不任意位置 \(O(1)\) 插入。通常为了保证效率，只在末尾加入删除元素。
• size：返回实际长度（通常声明的长度会大于实际长度），也就是包含的元素个数。
• empty：判断是否为空，是返回 \(1\)，不是返回 \(0\)。
• clear：直接清空。时间复杂度线性。
• 迭代器：随机访问迭代器（注意），可以直接进行加减操作（作差、求和也可）。
• begin/end：返回第一个和最后一个函数的迭代器，如果想返回值的话，可以用 *v.begin ()，与数组的 \(a_0\) 效果相同。注意下标是从零开始，所以 *a.end () 是越界访问。
• front/back：返回第一个或最后一个元素，即 a.front () = *a.begin ()，a.back () = *--a.end ()。
• push_back/pop_back：在末尾插入或者删除元素。

可以代替邻接表存边，如果想连一条 \(x\) 到 \(y\) 的有向边，那么只需：

v[x].push_back (y) ;

无向边同理。

queue

FIFO，从队尾进入，队头出去。

• push：入队。
• pop：出队。
• front：询问队头元素。
• back：询问队尾元素。

用于 SPFA 和其他的什么东西，只不过快死掉就是了。

priority_queue

默认是一个大根二叉堆（其实不能算队列，但是它叫 queue，那就算到这里面好了）。

• 相比 queue 多了一个 top 函数，可以查询堆顶元素（也就是最大值）。
• 支持重载小于号。
• 也可以实现小根堆，有这么两个方法：
  1.插入原数的相反数，这个方法容易废。
  2.priority_queue < int ,vector < int > ,greater < int > > q。

deque

双端队列，相当于一个头朝左和一个头朝右的队列混到了一起，也可以看做一个 queue 和 vector 的结合。

• 相比 queue，它支持随机访问。
• 除了 front 和 back，它具有 begin/end 两个头、尾迭代器。
• 不仅有 push_back 和 pop_back，还有 push_front 和 pop_front（因为是双端）。
• 线性的 clear。

有人用这个玩意写单调队列，但是 STL 让人感觉不靠谱，不如手写。

set

只要你学过高中数学（其实不学也知道），就会知道 set（集合）具有互异性，也就是这个玩意可以自动帮你去重，但是他们同时是有序的默认可以单增排序，所以不具有无序性。

• size/empty/clear 同 vector。
• 迭代器：是双向访问迭代器，不支持随机访问，只能 ++ 或者 --。
• begin/end 同 vector。
• insert：插入操作，复杂度 \(\mathcal{O}(\log n)\)，所以要是插入量大有可能炸掉，但是几率不很大。
• find：在本集合中寻找是否有给定值，要是有返回迭代器，否则返回 s.end ()，仍然带一个 \(\log\)。
• lower(upper)_bound：形式稍有不同，只需 s.lower(upper)_bound (x) 即可返回迭代器。
• erase：如果给出的是迭代器，就删除迭代器指向位置的元素（\(\mathcal{O}(\log n)\)），如果给出的是值，那么会删除等于这个值的元素（\(\mathcal{O}(k+\log n)\)，其中 \(k\) 是被删除的元素个数），在 set 下等效，但是到 multimap 就不一样了。这个玩意好用，但是复杂度让人隐隐约约不太放心。
• count：返回集合中等于给定值的元素的个数，\(\mathcal{O}(k+\log n)\)。

multiset

与 set 大致相同，但是允许重复。
唯一需要注意的是 erase，如果你给的是迭代器当然没有问题，但是如果是数值就需要注意了，因为它可能会删好几个。

map

不是地图，是映射。
其形式为：

map < key_type ,value_type > m ;

通常是把一个比较复杂的（如字符串）键值映射到比较简单的域上（如整数）。

• size/empty/clear/begin/end/迭代器/insert/erase/find：同 set。
• map 支持随机访问，这是最吸引人的地方。

但是由于它自带一个 \(\log\)，可能会被爆破，比如我。

unordered_map

这个东西不像 map 一样有序，但是 hash 很喜欢它。
在单个查找的时候比 map 优秀，平均是常数复杂度。

bitset

好像没什么存在感，懒得弄。