C++ STL 六组件介绍
前言
C++ STL 六组件介绍。
概念
C++:编程语言
STL(Standard Template Library,标准模板库):C++ 标准库的一部分,提供相关工具(函数模板、类模板和函数等)
“函数模板” 和 “类模板” 是“抽象”概念,“模板函数” 和 “模板类” 是“具体”概念。
六组件:容器,算法,迭代器,适配器,仿函数,分配器
基础(常用) 三组件:容器,算法,迭代器
拓展(少用) 三组件:适配器,仿函数,分配器
容器(container)
概念
- 组织数据的结构(所以称作:容纳物体的器具 -> 容器)
- 特性:静态
- 类比:数组
类型
顺序容器
- 数组/向量
- 链表
- 队列
- 栈
关联容器
- 图/映射
- 集合
- 对组
- 元组
数组/向量
名称 | 底层原理 | 说明 |
---|---|---|
array | 静态数组 | C++11 标准 |
vector | 动态数组 |
链表
名称 | 底层原理 | 说明 |
---|---|---|
list | 双向链表 | |
forward_list | 单向链表 | C++11 标准 |
队列
名称 | 底层原理 | 说明 |
---|---|---|
deque | 管理数组+多个被管理数组 | |
queue | deque | 容器适配器 |
priority_queue | vector;堆(完全二叉树) | 容器适配器 |
栈
名称 | 底层原理 | 说明 |
---|---|---|
stack | deque | 容器适配器 |
图/映射
名称 | 底层原理 | 说明 |
---|---|---|
map | 红黑树 | |
multimap | 红黑树 | |
unordered_map | 哈希表 | C++11 标准 |
unordered_multimap | 哈希表 | C++11 标准 |
集合
名称 | 底层原理 | 说明 |
---|---|---|
set | 红黑树 | |
multiset | 红黑树 | |
unordered_set | 哈希表 | C++11 标准 |
unordered_multiset | 哈希表 | C++11 标准 |
对组
名称 | 底层原理 | 说明 |
---|---|---|
pair | 结构体struct |
元组
名称 | 底层原理 | 说明 |
---|---|---|
tuple | 递归继承类 | C++11 标准 |
总表
名称 | 底层原理 | 说明 |
---|---|---|
array | 静态数组 | C++11 标准 |
vector | 动态数组 | |
list | 双向链表 | |
forward_list | 单向链表 | C++11 标准 |
deque | 管理数组+多个被管理数组 | |
queue | deque | 容器适配器 |
priority_queue | vector;堆(完全二叉树) | |
stack | deque | 容器适配器 |
map | 红黑树 | |
multimap | 红黑树 | |
unordered_map | 哈希表 | C++11 标准 |
unordered_multimap | 哈希表 | C++11 标准 |
set | 红黑树 | |
multiset | 红黑树 | |
unordered_set | 哈希表 | C++11 标准 |
unordered_multiset | 哈希表 | C++11 标准 |
pair | 结构体 struct | |
tuple | 递归继承类 | C++11 标准 |
代码示例
1 |
|
作用(为什么需要)
- 可以高效地组织数据
- 如:直接使用 vector<> 存储数据,而无需自己编写与数组类似并比数组“高级”的“顺序表”数据结构
- 如:直接使用 list<> 存储数据,而无需自己编写“双向链表”数据结构
算法(algorithm)
概念
- 处理数据的操作(所以称作:算术的法门 -> 算法)
- 特性:动态
- 类比:函数
类型
这里只列举部分算法,更多参见:算法库 - cppreference.com
不修改序列的操作
- count()
- find()
修改序列的操作
- copy()
- swap()
划分操作
- partition()
- stable_partition()
排序操作
- sort()
- stable_sort()
二分搜索操作(在已排序范围上)
- lower_bound()
- binary_search()
其他已排序范围上的操作
- merge()
- inplace_merge()
集合操作(在已排序范围上)
- includes()
- set_difference()
堆操作
- is_heap()
- sort_heap()
最小/最大操作
- max()
- min()
比较操作
- equal()
- lexicographical_compare()
排列操作
- is_permutation()
- next_permutation()
数值运算
- iota()
- accumulate()
未初始化内存上的操作
- destroy_at()
- construct_at()
C 库
- qsort()
- bsearch()
代码示例
1 |
|
作用(为什么需要)
- 可以高效地处理数据
- 如:直接使用 max() 比较数据,而无需自己编写比较并返回数据的比较函数算法
- 如:直接使用 find() 查找数据,而无需自己编写遍历、比较并返回数据的查找函数算法
迭代器(iterator)
概念
- 连接容器和算法
- 代表容器组织的数据:无需关心数据的内部实现细节,以统一的方式表示数据
- 通过算法处理数据:操作数据时,以“逐一访问”/遍历的表现形式(所以称作:迭代物品的器具 -> 迭代器)
- 特性:静 -> 动态
- 类比:数组下标/索引/位置/指针/地址
常用迭代器
- 正向迭代器:iterator<>
- 常量正向迭代器:const_iterator<>
- 反向迭代器:reverse_iterator<>
- 常量反向迭代器:const_reverse_iterator<>
类型和代码示例
类型
- 输入迭代器
- 输出迭代器
- 前向迭代器
- 双向迭代器
- 随机访问迭代器
- 连续迭代器
输入迭代器
- 从输入流中逐个读出数据
- 支持单次遍历
- istream_iterator<>
将“流”看作是一种容器,迭代器可以作用于它。
1 |
|
输出迭代器
- 向输出流中逐个写入数据
- 支持单次遍历
- ostream_iterator<>
1 |
|
前向迭代器
- 支持逐个前进,不支持逐个后退
“前进”指“增加”即“++/+1”操作,“后退”指“减少”即“–/-1”操作。
- 支持多次遍历
- 没有特定的类模板, 是 符合前向迭代器特性的 容器 对应的 迭代器的 类型(如 forward_list<> ,其底层原理是单向链表,支持单向前进顺序访问,不支持反向后退顺序访问,不支持随机访问,是 符合前向迭代器特性的 容器,其对应的 迭代器的 类型 是前向迭代器)
1 |
|
双向迭代器
支持逐个前进,支持逐个后退
支持多次遍历
没有特定的类模板, 是 符合双向迭代器特性的 容器 对应的 迭代器的 类型(如 list<> ,其底层原理是双向链表,支持单向前进顺序访问,支持反向后退顺序访问,不支持随机访问,是 符合双向迭代器特性的 容器,其对应的 迭代器的 类型 是双向迭代器)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// #include <iterator>
using std::cout;
using std::endl;
using std::list;
int main()
{
list<int> li = {0, 1, 2};
// 双向迭代器
list<int>::const_iterator it_beg = li.begin(); // 数据“0”的“位置”
list<int>::const_iterator it_end = li.end(); // 数据“2”的后一个“位置”
for (list<int>::const_iterator it = it_beg; it != it_end; ++it) // 前进遍历
{
cout << *it << " ";
}
cout << endl;
list<int>::const_reverse_iterator it_rbeg = li.rbegin(); // 数据“2”的“位置”
list<int>::const_reverse_iterator it_rend = li.rend(); // 数据“0”的前一个“位置”
for (list<int>::const_reverse_iterator it = it_rbeg; it != it_rend; ++it) // 后退遍历
{
cout << *it << " ";
}
cout << endl;
return 0;
}
// 输出:0 1 2
// 输出:2 1 0随机访问迭代器
支持任意前进和后退
支持多次遍历
没有特定的类模板, 是 符合随机访问迭代器特性的 容器 对应的 迭代器的 类型(如 vector<> ,其底层原理是动态数组,支持随机访问,是 符合随机访问迭代器特性的 容器,其对应的 迭代器的 类型 是随机访问迭代器)
1 |
|
连续迭代器
- C++17 标准引入
- 支持任意前进和后退
- 支持多次遍历
- 与随机访问迭代器不同,连续迭代器保证数据在内存中是连续存储的,可以提供更高效的内存访问
- 没有特定的类模板, 是 符合连续迭代器特性的 容器 对应的 迭代器的 类型(如 vector<> ,其底层原理是动态数组,支持随机访问,数据连续存储,是 符合连续迭代器特性的 容器,其对应的 迭代器的 类型 是连续迭代器)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// #include <iterator>
using std::cout;
using std::endl;
using std::vector;
int main()
{
vector<int> vec = {0, 1, 2};
// 连续迭代器
vector<int>::const_iterator it_beg = vec.begin(); // 数据“0”的“位置”
cout << *(it_beg + 2) << endl; // 数据“2”的“位置” 随机访问
return 0;
}
// 输出:2
容器对应的迭代器的类型
数组/向量
容器 | 对应的迭代器的类型 |
---|---|
array | 随机访问迭代器 |
vector | 随机访问迭代器 |
链表
容器 | 对应的迭代器的类型 |
---|---|
list | 双向迭代器 |
forward_list | 前向迭代器 |
栈
容器 | 对应的迭代器的类型 |
---|---|
stack | 不支持迭代器 |
队列
容器 | 对应的迭代器的类型 |
---|---|
deque | 随机访问迭代器 |
queue | 不支持迭代器 |
priority_queue | 不支持迭代器 |
图/映射
容器 | 对应的迭代器的类型 |
---|---|
map | 双向迭代器 |
multimap | 双向迭代器 |
unordered_map | 前向迭代器 |
unordered_multimap | 前向迭代器 |
集合
容器 | 对应的迭代器的类型 |
---|---|
set | 双向迭代器 |
multiset | 双向迭代器 |
unordered_set | 前向迭代器 |
unordered_multiset | 前向迭代器 |
对组
容器 | 对应的迭代器的类型 |
---|---|
pair | 不支持迭代器 |
元组
容器 | 对应的迭代器类型 |
---|---|
tuple | 不支持迭代器 |
总表
容器 | 对应的迭代器的类型 |
---|---|
array | 随机访问迭代器 |
vector | 随机访问迭代器 |
list | 双向迭代器 |
forward_list | 前向迭代器 |
stack | 不支持迭代器 |
deque | 随机访问迭代器 |
queue | 不支持迭代器 |
priority_queue | 不支持迭代器 |
map | 双向迭代器 |
multimap | 双向迭代器 |
unordered_map | 前向迭代器 |
unordered_multimap | 前向迭代器 |
set | 双向迭代器 |
multiset | 双向迭代器 |
unordered_set | 前向迭代器 |
unordered_multiset | 前向迭代器 |
pair | 不支持迭代器 |
tuple | 不支持迭代器 |
作用(为什么需要)
- 连接容器和算法
- 代表容器组织的数据:无需关心数据的内部实现细节,以统一的方式表示数据
- 通过算法处理数据:操作数据时,以“逐一访问”/遍历的表现形式
- 类比:容器 -> 数组,算法 -> 遍历,迭代器 ->数组下标。为了实现遍历,需要通过数组下标获取数组的数据 -> 为了实现算法,需要通过迭代器获取容器的数据
容器,算法,迭代器代码示例
1 |
|
适配器(adapter)
概念
- 封装已有目标(容器、迭代器和函数),提供不同形式的接口(特性和函数等)
- 类比:电源适配器将 220V 的交流电转换成 20V 的直流电提供给笔记本电脑;设计模式的适配器模式
类型和代码示例
类型
- 容器适配器
- 迭代器适配器 (少用)
- 函数适配器 (少用)
容器适配器
- stack<>
- queue<>
- priority_queue<>
1 |
|
迭代器适配器
- 反向迭代器:reverse_iterator<>
- 插入迭代器:back_insert_iterator<>,front_insert_iterator<>,insert_iterator<>
- 流迭代器:istream_iterator<>,ostream_iterator<>
- 流缓冲迭代器:istreambuf_iterator<>,ostreambuf_iterator<>
- 移动迭代器:move_iterator<>
注意:“迭代器”和“迭代器适配器”的类型中有重叠的类型。如:stream_iterator<>,从“输入”的角度, 是“迭代器”的“输入迭代器”类型;从“流”的角度,是“迭代器适配器”的“流迭代器”类型。
一般不区分容器和容器适配器,迭代器和迭代器适配器。
代码示例见“迭代器”内容。
函数(普通函数、类方法、 仿函数和 Lambda 表达式等) 适配器
注意:很多函数适配器已不推荐/过时/弃用:bind1st()、std::bind2nd() 和 mem_fun() 等,请注意甄别
- 改变函数参数:bind()
1 |
|
- 封装函数:function<>
1 |
|
作用(为什么需要)
适配器
- 可以在已有目标(容器、迭代器和函数)的基础上提供不同形式的接口(特性和函数等),以满足特定场景需求
- 如:已有容器不满足栈数据结构的特性,封装双端队列 deque<> 容器形成 stack<> 容器适配器。直接使用 stack<> 存储数据,而无需自己编写“栈”数据结构
- 如:已有容器不满足队列数据结构的特性,封装双端队列 deque<> 容器形成 queue<> 容器适配器。直接使用 queue<> 存储数据,而无需自己编写“队列”数据结构
仿函数(functor)
概念
- 重载调用运算符(小括号“()”)的类的对象。(所以又称:函数对象)
- 重载调用运算符(小括号“()”)的类的对象 使用调用运算符时,表现形式和普通函数调用一样(所以称作:仿造的函数 -> 仿函数)
- 类比:函数指针;Lambda 表达式
代码示例
一般使用
1 |
|
算法使用
1 |
|
作用(为什么需要)
- 可以代替函数指针(函数指针的签名复杂)
函数指针:指向函数的指针
- 可以通过类的特性封装更多信息,执行更多操作
分配器(allocator)
概念
- 为容器提供自定义的内存分配和释放,对象构造和析构功能(所以称作:分配空间的器具 -> 分配器)
一般类型(内置类型和自定义类型等)内存分配(在堆上的动态内存分配)不推荐使用分配器(难用),容器分配内存可以使用分配器(少用,有需求才用)
分配器本质: 将 1. 内存分配和对象构造 和 2. 对象析构和内存释放 两个过程 拆分成 1. 内存分配 2. 对象构造 3. 对象析构 4. 内存释放 四个过程,通过定制内存管理策略提高灵活性和效率
- 类比:malloc() - free();构造函数 - 析构函数;new - delete
代码示例
一般类型(内置类型和自定义类型等)
1 |
|
容器类型
- 大多数(vector<> 和 list<> 等)容器的实现中,形参有一个默认分配器,其设计得足够安全和高效,一般不需要定制, 容器自动调用该默认分配器管理空间
1 | // vector<> 的声明 |
- 有需求时需要自定义分配器
1 |
|
作用(为什么需要)
- 可以为容器提供自定义的内存分配和释放,对象构造和析构功能
分配器本质: 将 1. 内存分配和对象构造 和 2. 对象析构和内存释放 两个过程 拆分成 1. 内存分配 2. 对象构造 3. 对象析构 4. 内存释放 四个过程,通过定制内存管理策略提高灵活性和效率
- 可以先进行内存分配(占位置),有数据时再进行对象构造,以避免对象构造(二次赋值/拷贝)开销
- 可以先进行对象析构,不需要空间时再进行内存释放,以避免内存释放开销
总结
C++ STL 六组件介绍。
参考资料
作者的话
- 感谢参考资料的作者/博主
- 作者:夜悊
- 版权所有,转载请注明出处,谢谢~
- 如果文章对你有帮助,请点个赞或加个粉丝吧,你的支持就是作者的动力~
- 文章在描述时有疑惑的地方,请留言,定会一一耐心讨论、解答
- 文章在认识上有错误的地方, 敬请批评指正
- 望读者们都能有所收获