STL大总结

收下吧，这是我最后的 STL 了。

容器

序列式容器

包含：array、vector、deque、list。
1. .fill(val)
2. .assgin(bgit, edit) / .assgin(cnt, val)
3. .erase(...)
  - 返回值：指向删掉的一个（段）元素的之后的位置的迭代器。
  - 传参格式
    - .erase(it)
    - .erase(bgit, edit)
4. .insert(...)
  
  新插入的值在 it 之前。
  - 返回值：均返回第一个插入的元素的迭代器（即下标最小的）。
  - 传参格式
    - .insert(it, val)
    - .insert(it, cnt, val)
    - .insert(it, bgit, edit)
    - .insert(it, initlist)
      
      示例：
      1
      a.insert(begin(a) + 2, {10, 11, 12, 13});
5. .emplace(it, val)
  
  不能完全替代 insert，只能插入一个元素。
  
  返回插入的元素的迭代器。
6. .emplace_back(val)
  
  可替代 push_back。
7. .emplace_front(val)
  
  可替代 push_front。
8. .capacity()
9. .resize(size)
10. .shrink_to_fit()
  
  所有可增大 size 的函数均可增大 capacity，但上述函数中只有 shrink_to_fit 可减小 capacity。
关联式容器

包含：map、multimap、set、multiset。

因为 map 系和 set 系的查询类的成员函数在传参上有很多相同的不同点，所以以下规定下文中 Btt（by the type）：如果讨论的是 map 系，则 “Btt” 为键值，如果讨论的是 set 系，则 “Btt” 为权值，btt 为类型与 Btt 相同的变量。
1. .find(btt)
  
  返回首个 Btt 与 btt 相等的元素的迭代器。
2. .count(btt)
  
  返回 Btt 与 btt 相等的元素的个数。
3. .lower_bound(btt)
4. .upper_bound(btt)
5. .equal_range(btt)
  
  返回一个 pair 对象，其中包含两个迭代器，其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。
6. .erase(...)
  - 返回值：对于传参为迭代器的，返回指向删掉的一个（段）元素的之后的位置的迭代器；对于传参基于 btt 的，返回删掉的元素个数。
  - 传参格式
    - .erase(btt)
      
      删掉 Btt 为 btt 的全部元素。
    - .erase(it)
    - .erase(bgit, edit)
7. .insert(...)
  
  规定下文中 Btt：如果讨论的是 map 系，则 “Btt” 为键值权值二元组，如果讨论的是 set 系，则 “Btt” 为权值。
  - 返回值（这里提到的返回值只适用于下面三种传参格式）
    - 插入一个元素，非 multi 系返回 pair<iterator, bool>，multi 系返回 iterator
      
      插入成功，iterator 为该元素迭代器，bool 为 true。
      
      插入失败（set 和 map 中已有 Btt 与其相同的元素），iterator 回与他 Btt 相同的那个元素的迭代器，bool 为 false。
    - 插入多个元素，返回 void。
  - 传参格式
    - .insert(btt)
    - .insert(it, beit, edit)
    - .insert(it, initlist)
8. .emplace(...)
  - 返回值：同 insert。
  - 传参格式
    - .emplace(btt)
      
      注意这里如果写成这样会 CE。
      1
      2
      map<int, int> m;
      m.emplace({1, 2});
      原因是编译器把 {1, 2} 当成初始化列表了，虽然你的意思是 {1, 2} 是个 pair 二元组。用 make_pair 就可以了。
    - .emplace(key, val)（对于 map 系）
      
      相当于将创建新键值对所需的数据作为参数直接传入。
上文中 Btt 的概念解释的不是很清楚，我在这里再梳理一遍。对于 set 系而言，一个元素只由一个部分组成，就是他本身的权值，所以 Btt 就是权值。而对于 map 系而言，一个元素由两部分组成，键值和权值，查询、删除时，只需要键值就可以找到相应的元素，所以这时候 Btt 为键值；而插入时需要提供完整的信息，所以 Btt 为键值权值二元组。

无序关联式容器中 Btt 的定义方法与关联式容器的相同。
无序关联式容器

包含：unordered_map、unordered_multimap、unordered_set、unordered_multiset。

与无序式容器的不同点
- 内部存储的元素是无序的。
- 成员函数没有 lower_bound、upper_bound，但是有 equal_range。
- unordered 系的操作不都是 $O(1)$ 的，其通过指定键查找对应的值的操作平均时间复杂度为 $O(1)$ ，但对于插入操作，其复杂度相当于非 unordered 系，且常数大于非 unordered 系。
容器适配器

包含：stack、queue、priority_queue。

容器适配器需要依赖基础容器，而且对于基础容器有一些要求，对于每种适配器满足要求，可以作为其基础容器的容器是：（加粗的为默认使用的）

stack：vector、deque、list。

queue：deque、list。

priority_queue：vector、deque。

算法函数

只列举我认为比较生僻但是在算法竞赛中能派上用场的。

stable_sort(bgit, edit)

稳定排序。
partial_sort(bgit, mdit, edit)

部分排序，参与排序的部分为 $[\mathrm{bgit}, \mathrm{edit})$ ，排好的部分为 $[\mathrm{bgit}, \mathrm{mdit})$ 。复杂度 $O(n\log m)$ 。
nth_element(bgit, mdit, egit)

寻找 $k$ 小数，参与寻找的部分为 $[\mathrm{bgit}, \mathrm{edit})$ ，寻找到的 $k$ 大值下标为 $\mathrm{mdit}$ （也就是 $k=\mathrm{mdit}-\mathrm{bgit}+1$ ），且满足所有左侧的数都比在大小关系中都比他靠左，右侧的数都比在大小关系中都比他靠右，复杂度 $O(n)$ 。
merge(bgit1, edit1, bgit2, edit2, it3)

将 $[\mathrm{bgit_1},\mathrm{edit_1})$ 和 $[\mathrm{bgit_2},\mathrm{edit_2})$ 做归并排序存入以 $\mathrm{it_3}$ 为开始的容器中。
inplace_merge(bgit, mdit, edit)

将 $[\mathrm{bgit},\mathrm{mdit})$ 和 $[\mathrm{mdit},\mathrm{edit})$ 做归并排序存入以 $\mathrm{bgit}$ 为开始的容器中。
find(bgit, edit, val)

返回第一个等于 val 的元素的迭代器，否则返回指向 edit 的迭代器。
find_if(bgit, edit, func)

返回第一个使 func == true 的元素迭代器，否则返回指向 edit 的迭代器。
find_if_not(bgit, edit, func)

与 find_if 正好相反。
equal_range(bgit, edit, val)

用法和效果和前面容器的成员函数一样。
swap_ranges(bgit1, edit1, bgit2)

交换 $[\mathrm{bgit_1},\mathrm{edit_1})$ 和 $[\mathrm{bgit_2},\mathrm{bgit_2}+\mathrm{edit_1}-\mathrm{bgit_1})$ 。
next_permutation(bgit, edit) / prev_permutation(bgit, edit)

这俩函数应该没有人不认识，我就是想提一下他们的复杂度： $O(n)$ 。