C++ STL 简介
前言
STL，英文全称 standard template library，中文可译为 标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入 / 输出、数学计算等功能。
vector
vector 容器是 STL 中最常用的容器之一，vector 实现的是一个动态数组，即可以进行元素的插入和删除。
vector 常被称为 向量容器，在尾部插入或删除元素，时间复杂度为 O(1)；而在容器头部或者中部插入或删除元素，时间复杂度为 O(n)。
1
2
3
4
5
| vector<int> nums; # 空 vector
nums.resize(20); # 指定大小
vector<int> nums(20); # 创建时指定大小，默认初始值都为 0
vector<int> nums(20,1); # 创建时指定大小，初始值为 1
vector<int> nums {1, 2, 3, 4, 5};
|
1
2
3
4
5
6
7
8
9
10
| size() # 返回元素个数
empty() # 返回是否为空
clear() # 清空
front()/back() # 第一个/最后一个元素
push_back()/pop_back() # 插入/移除最后一个元素
begin()/end() # 返回第一个元素/最末元素下一个位置的迭代器
insert() # 插入元素到 vector 中
resize() # 改变 vector 元素数量的大小
[] # 下标访问
支持比较运算，按字典序
|
pair
pair 专门用来将 2 个普通元素 first 和 second 创建成一个新元素 <first, second>
1
2
3
4
| pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以 first 为第一关键字，以 second 为第二关键字（字典序）
|
string
string 是 C++ 标准库的一个重要的部分，主要用于字符串处理。
1
2
3
4
| string s1; # 默认初始化，空串
string s2(s1); # 使用s1初始化s2
string s3("Hello"); # 字符串初始化
string s4(n,'c'); # 使用 n 个字符 'c' 初始化
|
1
2
3
4
5
6
7
8
| size()/length() # 返回字符串长度
empty() # 判空
clear() # 清空
substr(pos,len) # 返回pos开始长度为len的子串
find(s)/rfind(s) # 查找 s 第一次/最后一次出现位置
+= # 重载 += 运算符
[] # 下标访问
字典序比较
|
queue
queue 只能在容器的末尾添加新元素，只能从头部移除元素，FIFO 准则
1
2
3
4
5
6
| size() # 返回队列中元素的个数
empty() # 判空
push() # 向队尾插入一个元素
front() # 返回队头元素
back() # 返回队尾元素
pop() # 弹出队头元素
|
priority_queue
priority_queue, 优先队列，元素按照一定的规则排列有序，在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。默认是大根堆
1
2
3
4
5
6
| size() # 返回队列中元素的个数
empty() # 判空
push() # 插入一个元素
top() # 返回堆顶元素
pop() # 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
|
deque
deque, 双端队列，允许在容器头部/尾部快速插入和删除
1
2
3
4
5
6
7
| size() # 返回队列中元素的个数
empty() # 判空
clear() # 清空
front()/back() # 返回第一个/最后一个元素
push_back()/pop_back() # 在尾部加入/删除一个元素
push_front()/pop_front() # 在头部加入/删除一个元素
[] # 下标访问
|
stack
stack 实现了一个先进后出（FILO）的数据结构
1
2
3
4
5
| size() # 返回栈中元素的个数
empty() # 判空
push() # 向栈顶插入一个元素
top() # 返回栈顶元素
pop() # 弹出栈顶元素
|
set
集合中以一种特定的顺序保存唯一的元素，自动递增去重。
unordered_set，multiset 类似
1
2
3
4
5
6
7
8
9
| size() # 返回集合中元素的个数
empty() # 判空
begin()/end() # 返回第一个元素/最末元素下一个位置的迭代器
find(val) # 查找值为 val 的元素
count(val) # 查找值为 val 的元素的个数
insert() # 插入元素到集合
erase() # 删除集合中的元素
lower_bound(val) # 返回指向第一个大于或等于val的元素的迭代器
upper_bound(val) # 返回指向第一个大于val的元素的迭代器
|
map
map 容器存储的都是 pair 对象，包含 “关键字 / 值” 对
unordered_map，multimap 类似
1
2
3
4
5
6
7
8
9
10
| size() # 返回map中元素的个数
empty() # 判空
begin()/end() # 返回第一个元素/最末元素下一个位置的迭代器
find(key) # 查找键为 key 的键值对
count(key) # 查找键为 key 的键值对的个数
insert() # 插入键值对
erase() # 删除键值对
lower_bound(key) # 返回指向第一个大于或等于key的元素的迭代器
upper_bound(key) # 返回指向第一个大于key的元素的迭代器
[] # 重载 [] 运算符
|
参考
wechat
