[编程笔记]-STLs(STL大整合)
前言
手打STL毕竟只是锦上添花，STL才是雪中送炭。
所以，来一篇STL大杂烩大整合！
注意，这里只整理了常用函数，并不是全部函数！
VECTOR
概念
是一种动态数组，运用到倍增的思想。
按字典序排序。
原理
因为申请空间耗时与空间大小无关、与申请次数有关——
所以vector会倍增申请空间o(￣︶￣)o
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
push_back() |
在队尾加入元素 | vec.push_back(加入元素) |
pop_back() |
在队尾删除元素 | vec.pop_back() |
empty() |
判断是否为空 | vec.empty() |
clear() |
清空 | vec.clear() |
size() |
元素个数 | vec.size() |
find() |
查找元素位置，否则返回队尾 | find(起始位置, 终止位置, 查找元素) |
front() |
返回队头元素 | vec.front() |
back() |
返回队尾元素 | vec.back() |
begin() |
返回队头迭代器 | vec.begin() |
end() |
返回队尾迭代器（最后元素的后一个元素） | vec.end() |
erase() |
删除指定元素 | vec.erase(迭代器) |
erase() |
删除指定区间（左闭右开）元素 | vec.erase(开始迭代器, 结束迭代器) |
[] |
随机选址 | vec[] |
定义方式
vector<TYPE> a，定义一个存储TYPE类型变量vector a。vector<TYPE> a(n)，定义一个大小为n的存储TYPE类型变量vector a。vector<TYPE> a(n, x)，定义一个大小为n的存储TYPE类型变量且初始值全为x的vector a。vector<TYPE> a[n]，定义n个存储TYPE类型变量vector a。
PAIR
概念
两个元素（不限种类）的结合体。
有点就是自带比较函数，先比第一个再比第二个（各自按字典序排序），可以很方便地sort()。
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
first |
第一元素 | p.first |
second |
第二元素 | p.second |
构造
pair<T1, T2> p，定义一个两个元素分别是T1类型和T2类型的pair p。
- make_pair(a, b)，返回一个由a和b构成的pair。
- {a, b}，返回一个由a和b构成的pair。（c++11专用）
STRING
概念
字符串。
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
substr() |
截取子串 | str.substr(起始下标, 截取长度) |
c_str() |
转换为c语言字符串（支持scanf） | str.c_str() |
empty() |
判断是否为空 | str.empty() |
clear() |
清空 | str.clear() |
size() |
字符串长度 | str.size() |
length() |
字符串长度 | str.length() |
find() |
查询字符位置 | str.find(查询字符) |
[] |
随机选址 | str[] |
详细介绍
substr()
如果截取长度超出字符串长度，或没有设定截取长度，默认截取至结尾。
c_str()
1 | |
操作
定义
string a，定义一个string a。string a = str，定义一个内容为str的string a。
修改
- a+=b，在a末尾加上b（string）。
- a+=b，在a末尾加上b（char）。
QUEUE
概念
队列。
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
push() |
入队 | q.push(入队元素) |
pop() |
队头出队 | q.pop() |
front() |
获取队头 | q.front() |
back() |
获取队尾 | q.back() |
empty() |
判断是否为空 | q.empty() |
size() |
队列元素个数 | q.size() |
操作
清空
直接重开一个队列就行了：
1 | |
PRIORITY_QUEUE
概念
优先队列（堆），默认大根堆
比较常用
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
push() |
入堆 | pq.push(入堆元素) |
top() |
获取堆顶 | pq.top() |
pop() |
堆顶出堆 | pq.pop() |
操作
实现小根堆
- 插入-x，最后输出的时候取反。
priority_queue<TYPE, vector<TYPE>, greater<TYPE> >
STACK
概念
栈
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
push() |
入栈 | st.push(入栈元素) |
top() |
获取栈顶 | st.top() |
pop() |
栈顶出栈 | st.pop() |
size() |
获取元素个数 | st.size() |
empty() |
是否为空 | st.empty() |
DEQUE
概念
双端队列
很牛逼哒
效率低的令人发指，慢了好几倍~
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
size() |
获取元素个数 | dq.size() |
empty() |
是否为空 | dq.empty() |
clear() |
清空 | dq.clear() |
front() |
获取队头 | dq.front() |
back() |
获取队尾 | dq.back() |
push_front() |
在队头加入元素 | dq.push_front(加入元素) |
pop_front() |
在队头删除元素 | dq.pop_front() |
push_back() |
在队尾加入元素 | dq.push_back(加入元素) |
pop_back() |
在队尾删除元素 | dq.pop_back() |
[] |
随机选址 | dq[] |
begin() |
返回队头迭代器 | dq.begin() |
end() |
返回队尾迭代器（最后元素的后一个元素） | dq.end() |
SET
set/multiset
原理
基于平衡二叉树（红黑树），动态维护有序序列。
set不能有重复元素，否则会被忽略掉。
而multiset可以。
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
size() |
获取元素个数 | s.size() |
empty() |
是否为空 | s.empty() |
clear() |
清空 | s.clear() |
begin() |
返回第一个迭代器 | s.begin() |
end() |
返回最后的迭代器（最后元素的后一个元素） | s.end() |
insert() |
插入元素 | s.insert(插入元素) |
find() |
查找元素，若无则返回end迭代器 | s.find(查找元素) |
count() |
返回某一元素个数 | s.count(查找元素) |
erase() |
删除所有对应值的元素 | s.erase(删除值) |
erase() |
删除对应迭代器的元素 | s.erase(删除迭代器) |
lower_bound() |
返回大于等于标准值的最小数迭代器 | s.lower_bound(标准值) |
upper_bound() |
返回大于标准值的最小数迭代器 | s.upper_bound(标准值) |
定义方式
set<TYPE> s，定义一个存储TYPE类型变量set s。multiset<TYPE> ms，定义一个存储TYPE类型变量multiset ms。
操作
迭代器可以++/–，前移后移。
时间复杂度
绝大部分O(logn)
unordered_set/unordered_muiltiset
原理
基于哈希表实现
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
size() |
获取元素个数 | us.size() |
empty() |
是否为空 | us.empty() |
clear() |
清空 | us.clear() |
begin() |
返回第一个迭代器 | us.begin() |
end() |
返回最后的迭代器（最后元素的后一个元素） | us.end() |
insert() |
插入元素 | us.insert(插入元素) |
find() |
查找元素，若无则返回end迭代器 | us.find(查找元素) |
count() |
返回某一元素个数 | us.count(查找元素) |
erase() |
删除所有对应值的元素 | us.erase(删除值) |
erase() |
删除对应迭代器的元素 | us.erase(删除迭代器) |
操作
迭代器不可以++/–，前移后移。
时间复杂度
增删改查O(1)
MAP
map/multimap
原理
基于平衡二叉树（红黑树），动态维护有序序列。
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
size() |
获取元素个数 | m.size() |
empty() |
是否为空 | m.empty() |
clear() |
清空 | m.clear() |
begin() |
返回第一个迭代器 | m.begin() |
end() |
返回最后的迭代器（最后元素的后一个元素） | m.end() |
insert() |
插入一对元素 | m.insert(插入pair) |
erase() |
删除对应对元素 | m.erase(删除pair) |
erase() |
删除对应迭代器元素 | m.erase(删除迭代器) |
find() |
查找要求键元素迭代器，若无则返回end迭代器 | m.find(要求查找键) |
count() |
返回某一元素个数 | m.count(查找元素) |
[] |
像使用数组一样使用（查找、修改） | m[] |
lower_bound() |
返回大于等于标准值的最小数迭代器 | m.lower_bound(标准值) |
upper_bound() |
返回大于标准值的最小数迭代器 | m.upper_bound(标准值) |
注意
[]的时间复杂度是O(logn)的。
操作
迭代器可以++/–，前移后移。
时间复杂度
绝大部分O(logn)
unordered_map/unordered_multimap
原理
基于哈希表实现
常用函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
size() |
获取元素个数 | um.size() |
empty() |
是否为空 | um.empty() |
clear() |
清空 | um.clear() |
begin() |
返回第一个迭代器 | um.begin() |
end() |
返回最后的迭代器（最后元素的后一个元素） | um.end() |
insert() |
插入一对元素 | um.insert(插入pair) |
erase() |
删除对应对元素 | um.erase(删除pair) |
erase() |
删除对应迭代器元素 | m.erase(删除迭代器) |
find() |
查找要求键元素迭代器，若无则返回end迭代器 | um.find(要求查找键) |
count() |
返回某一元素个数 | um.count(查找元素) |
[] |
像使用数组一样使用（查找、修改） | um[] |
操作
迭代器不可以++/–，前移后移。
时间复杂度
增删改查O(1)
BITSET
作用
压位
bool数组一个元素占8位，而bitset一个元素只占1位，节省了八倍内存。
定义方式
bitset<n> bs，定义一个存储n个bool的bitset bs。
常见函数
| 函数名 | 函数作用 | 函数用法 |
|---|---|---|
count() |
获取1的个数 | bs.count() |
any() |
判断是否有1 | bs.any() |
none() |
判断是否全是0 | bs.none() |
set() |
把所有位设成1 | bs.set() |
set() |
把要求位置设成要求值 | bs.set(要求位置, 要求值) |
reset() |
把所有位设成0 | bs.reset() |
flip() |
把所有位取反 | bs.flip() |
flip() |
把指定位取反 | bs.flip(指定位) |
操作
支持所有位运算：&, |, ^, ~, <<, >>
支持==和!=
支持[]看某一位
完结撒花o(￣︶￣)o
[编程笔记]-STLs(STL大整合)
http://githarlem.github.io/2024/08/03/STLs/