算法备忘录·STL

上一节数据结构中，用代码实现了各个数据结构的基本操作。然而在实际使用中， C++ 中的 STL 已经很好的封装了这些。

STL

vector

• 变长数组，使用了倍增的思想（每次用完后，空间扩大一倍），为了保证效率，元素的增删一般应该在末尾进行
• #include<vector>
• 常见用法

  • size() ：返回元素个数，复杂度 $O(1)$

  • empty() ：返回是否为空，复杂度 $O(1)$

  • clear() ：清空

  • front()/back() ：返回第一个/最后一个元素

  • push_back()/pop_back()：插入/弹出最后一个元素

  • begin()/end() ：返回第一个元素的迭代器/vector 的尾部

    • 利用迭代器的遍历：

    for (vector <int>::iterator i = a.begin(); i != a.end(); i ++ ) cout << *i << endl;

  • [] ： 随机访问

  • 支持比较运算，按字典序

  • 两个 vector 拼接：vec1.insert(vec1.end(), vec2.begin(), vec2.end())

pair

• 相当于封装好的结构体，且自带比较运算
• #include <utility>
• 常见用法
  • first/second ：第一个/第二个元素
  • make_pair(v1, v2) ： 以 v1 和 v2 的值创建一个 pair 对象
  • 支持比较运算，以 first 为第一关键字，以 second 为第二关键字（按字典序）

string

• 字符串
• #include <cstring>
• 常见用法
  • size()/length()
  • empty()
  • clear()
  • substr(初始下标, (子串长度)) ：返回子串。如果子串长度为空则返回到末尾
  • c_str() ：返回字符串所在字符数组的起始地址——相当于变成 char[] 了

queue

• 队列
• #include <queue>
• 常见用法
  • size()
  • empty()
  • push()/pop() 插入队尾元素/弹出队头元素
  • front()/back() 返回队头元素/返回队尾元素

priority_queue

• 优先队列，默认是大根堆
• #include <queue>
• 常见用法
  • size()
  • empty()
  • push()/pop() 插入一个元素/弹出堆顶元素
  • top() 返回堆顶元素
  • 定义小根堆：
    1. 法 1 —— 数字取负数
    2. 法 2 —— priority_queue<int, vector<int>, greater<int>> q;
• 重载
  • priority_queue 默认使用 less<>, 所以重载 operator <
  • 如果使用 greater<> 则应该重载 operator >

stack

• 栈
• #include <stack>
• 常见用法
  • size()
  • empty()
  • push()/pop() 向栈顶插入一个元素/弹出栈顶元素
  • top() 返回栈顶元素

deque

• 双端队列，加强版的 vector，但是时间复杂度高
• #include <deque>
• 常见用法
  • size()
  • empty()
  • clear()
  • front()/back() ：返回第一个/最后一个元素
  • push_back()/pop_back()：插入/弹出最后一个元素
  • push_front()/pop_front()：插入/弹出第一个元素
  • begin()/end() ：返回第一个元素的迭代器/vector 的尾部
  • [] ： 随机访问

set, multiset

• 分别是“有序集合”和“有序多重集合”。基于平衡二叉树（红黑树），动态维护有序序列
• #include <set>
• 常见用法
  • size()
  • empty()
  • clear()
  • begin()/end() ：时间复杂度均为 $O(1)$
  • 不支持随机访问。只能用其迭代器——双向访问迭代器，支持星号(*)解除引用以及++, -- 返回前驱和后继，时间复杂度 $O(\log{n})$
  • insert() 把一个元素 x 插入到集合 s 中，时间复杂度为 $O(\log{n})$
    • 在 set 中，若元素已存在，则不会重复插入该元素
  • find() 查找等于 x 的元素，并返回指向该元素的迭代器。若不存在，则返回 s.end()。时间复杂度为 $O(\log{n})$。
  • count() 返回某一个数的个数
  • erase()
    1. 输入是一个数x，删除所有 x。时间复杂度 $O(k + \log{n})$
    2. 输入一个迭代器，删除这个迭代器指向的元素
  • lower_bound()/upper_bound()
    • lower_bound(x) ：返回大于等于 x 的最小的数的迭代器
    • upper_bound(x) ：返回大于 x 的最小的数的迭代器

map/multimap

• 键值对。实现是以 key 为关键码的红黑树
• #include <map>
• 常见用法
  • size()
  • empty()
  • clear()
  • begin()/end() ：时间复杂度均为 $O(1)$
  • insert() 插入的数是一个 pair<key_type, value_type>
  • erase() 输入的参数是 pair<key_type, value_type> 或者迭代器
  • find()
  • [] ： 随机访问。时间复杂度是 $O(\log{n})$
    • multimap 不支持此操作
  • lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap

• 哈希表
• 常见用法：和上面类似，增删改查的时间复杂度是 $O(1)$
  • 不支持 lower_bound()/upper_bound()， 迭代器的 ++，--

bitset

• 压位，最小单位 1 bit
• #include <bitset>
• 常见用法
  • ~, &, |, ^
  • >>, <<
  • ==, !=
  • [] : 随机访问
  • count() ：求 1 的位数
  • size() ：求总位数
  • any()/none() ：判断是否有一个 1/ 判断是否全是 0
  • set() ：把所有位置变成 1
    • set(k, v) ： 把位置 k 变成 v
  • reset() 把所有位置变成 0
  • flip() 等价于 ~
    • flip(k) 把位置 k 取反

---

算法备忘录系列目录：
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·杂项
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析
第九节 算法备忘录·杂项