算法备忘录·STL

本文最后更新于:2021年9月12日 上午

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

STL

vector

  • 变长数组,使用了倍增的思想(每次用完后,空间扩大一倍),为了保证效率,元素的增删一般应该在末尾进行
  • #include<vector>
  • 常见用法
    • size() :返回元素个数,复杂度 O(1)O(1)
    • empty() :返回是否为空,复杂度 O(1)O(1)
    • clear() :清空
    • front()/back() :返回第一个/最后一个元素
    • push_back()/pop_back():插入/弹出最后一个元素
    • begin()/end() :返回第一个元素的迭代器/vector 的尾部
      • 利用迭代器的遍历:
      1
      for (vector <int>::iterator i = a.begin(); i != a.end(); i ++ ) cout << *i << endl;
    • [] : 随机访问
    • 支持比较运算,按字典序

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;

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(1)
    • 不支持随机访问。只能用其迭代器——双向访问迭代器,支持星号(*)解除引用以及++, -- 返回前驱和后继,时间复杂度 O(logn)O(\log{n})
    • insert() 把一个元素 x 插入到集合 s 中,时间复杂度为 O(logn)O(\log{n})
      • 在 set 中,若元素已存在,则不会重复插入该元素
    • find() 查找等于 x 的元素,并返回指向该元素的迭代器。若不存在,则返回 s.end()。时间复杂度为 O(logn)O(\log{n})
    • count() 返回某一个数的个数
    • erase()
      1. 输入是一个数x,删除所有 x。时间复杂度 O(k+logn)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)O(1)
    • insert() 插入的数是一个 pair<key_type, value_type>
    • erase() 输入的参数是 pair<key_type, value_type> 或者迭代器
    • find()
    • [] : 随机访问。时间复杂度是 O(logn)O(\log{n})
      • multimap 不支持此操作
    • lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap

  • 哈希表
  • 常见用法:和上面类似,增删改查的时间复杂度是 O(1)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 取反