算法备忘录·STL
本文最后更新于 2024年5月15日 凌晨
上一节数据结构中,用代码实现了各个数据结构的基本操作。然而在实际使用中, C++ 中的 STL 已经很好的封装了这些。
STL
vector
- 变长数组,使用了倍增的思想(每次用完后,空间扩大一倍),为了保证效率,元素的增删一般应该在末尾进行
#include<vector>
- 常见用法
-
size()
:返回元素个数,复杂度 -
empty()
:返回是否为空,复杂度 -
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;
-
[] : 随机访问
-
支持比较运算,按字典序
-
两个
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 —— 数字取负数
- 法 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()
:时间复杂度均为- 不支持随机访问。只能用其迭代器——双向访问迭代器,支持星号(*)解除引用以及
++
,--
返回前驱和后继,时间复杂度 insert()
把一个元素 x 插入到集合 s 中,时间复杂度为- 在 set 中,若元素已存在,则不会重复插入该元素
find()
查找等于 x 的元素,并返回指向该元素的迭代器。若不存在,则返回 s.end()。时间复杂度为 。count()
返回某一个数的个数erase()
- 输入是一个数x,删除所有 x。时间复杂度
- 输入一个迭代器,删除这个迭代器指向的元素
lower_bound()
/upper_bound()
lower_bound(x)
:返回大于等于 x 的最小的数的迭代器upper_bound(x)
:返回大于 x 的最小的数的迭代器
map/multimap
- 键值对。实现是以 key 为关键码的红黑树
#include <map>
- 常见用法
size()
empty()
clear()
begin()
/end()
:时间复杂度均为insert()
插入的数是一个pair<key_type, value_type>
erase()
输入的参数是pair<key_type, value_type>
或者迭代器find()
- [] : 随机访问。时间复杂度是
- multimap 不支持此操作
lower_bound()
/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap
- 哈希表
- 常见用法:和上面类似,增删改查的时间复杂度是
- 不支持
lower_bound()
/upper_bound()
, 迭代器的++
,--
- 不支持
bitset
- 压位,最小单位 1 bit
#include <bitset>
- 常见用法
~
,&
,|
,^
>>
,<<
==
,!=
- [] : 随机访问
count()
:求 1 的位数size()
:求总位数any()
/none()
:判断是否有一个 1/ 判断是否全是 0set()
:把所有位置变成 1set(k, v)
: 把位置 k 变成 v
reset()
把所有位置变成 0flip()
等价于~
flip(k)
把位置 k 取反
算法备忘录系列目录:
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·杂项
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析
第九节 算法备忘录·杂项
算法备忘录·STL
https://justloseit.top/算法备忘录·STL/