STL标准模板库内容整理
STL标准模板库（重点）：C++工具（类模板与函数模板）
STL标准模板库
本质上就是数据结构和算法
C语言标准库未直接提供
C++标准库直接提供
- 定义：高效C程序库，含基本数据结构和算法，属C标准库，采用泛型编程
泛型编程：抽象数据类型，用泛型代替具体类型，编写通用代码
六大组件
容器（重要）：存储数据（数据结构）
- 序列式容器：vector、list、deque等
- 关联式容器：set、map等
- 无序关联式容器：unordered_set、unordered_map等
迭代器：访问容器元素，泛型指针（例：vector::iterator）
算法：操作容器元素的普通函数（例：std::sort）
适配器：适配作用
- 容器适配器：stack、queue、priority_queue
- 迭代器适配器
- 函数适配器：bind、bind1st、bind2nd、function等
函数对象：实现定制化操作
空间配置器：管理内存（使用、原理、源码）
六大组件
容器
作用：存放数据
1、序列式容器
模型理解
array
- 静态数组，大小固定的数组
vector
动态数组
push_back
- GCC：2倍增长
- VC++：1.5倍增长
支持随机访问迭代器
逻辑结构和物理结构一致
deque
双端队列
支持随机访问迭代器
逻辑结构
连续空间
- 双端开口
物理结构
在内存中的表现形式
由多个片段构成的
- 片段内部是连续的，但是片段之间不连续
- 由中控器进行操作，连接N个片段
forward_list
- 单链表
- 支持前向访问迭代器
list
双向链表
支持双向访问迭代器
物理结构
- 循环双向链表
逻辑结构
- 双向链表
基本操作
初始化：无参、count个value、迭代器范围、拷贝/移动、大括号范围
访问首地址
vector<int> nums1 = {1,2,3,4,5}; - //vector对象的首地址 - cout << &nums1 << endl;//查看vector首元素的地址 - cout << &*nums1.begin() << endl; - cout << &nums1[0] << endl; - cout << &nums1.at(0) << endl;//有越界的判断 - cout << &nums1.front() << endl; - cout << nums1.data() << endl;
遍历：均支持迭代器和增强for循环；vector与deque支持下标，list不支持
auto it = nums.begin();
list
::iterator it2; - it2 = nums.begin()
auto & ele : nums
尾部插入删除：三者均支持
头部插入删除：deque与list支持，vector不支持（vector头部操作复杂度O(N)）
源码阅读（了解）
- vector：迭代器为_Tp*，含动态扩容机制
- deque：迭代器较复杂，含多个指针，缓冲区大小与元素类型相关
insert操作（重要）：均支持在任意位置插入，返回首插入元素迭代器；vector插入可能因扩容导致迭代器失效，需更新
扩容
- //(1) t < n - m 不会扩容
- //(2) n - m < t < m 按照2*size()进行扩容
- //(3) n - m < t, m < t 按照t + m进行扩容
插入方式
(it,80)
(it,5,80)
(it,.begin(),.end())
- 迭代
（it,{80})
- 大括号
erase操作（重要）：删除单个或多个元素，返回被删元素后一位迭代器；list和deque需更新迭代器，vector删除连续元素可能漏元素
- 从逻辑的角度上来说，对应的元素已经变成了被删元素的下一位
元素清空：均有clear、size；vector与deque有shrink_to_fit；vector有capacity
其他成员函数：swap、resize、front、back
emplace_back函数：尾部直接构造对象，比push_back高效（emplace与insert类似）
list的特殊操作（重要）
- sort函数：排序，可自定义比较规则（底层归并排序）
- reverse函数：反转元素顺序（与vector的reserve区分）
- unique函数：去重（需先排序）
- merge函数：合并两个有序list（合并后原list元素清空）
- remove/remove_if函数：移除等于value的元素/符合条件的元素
- splice函数：移动元素到指定位置（注意范围交叉问题，可实现LRU）
线性容器总结
时空效率
1、需要频繁的在容器中间位置添加/删除元素
list
- O(1)
2、需要频繁的在容器头部添加/删除元素
- deque/list
3、需要频繁的在容器尾部添加/删除元素
vector/deque/list
- vector
4、需要频繁的在容器头部/尾部添加/删除元素
deque/list
- deque
5、需要频繁的访问任意位置上的元素
vector/deque
- vector
2、关联式容器
共性
底层实现
红黑树
- 近似的平衡二叉树
查找元素的时间复杂度为O(logN)
- 二分查找
默认情况下会按照升序的方式进行排列
- 如果希望自定义排序方式，可以定制第二个模板参数
不能修改关键字的值
支持的是双向访问迭代器
set
特征：存key，key唯一，默认升序
- 不能存储重复的关键字key
- 不支持下标访问运算符
构造：无参、迭代器范围、拷贝、初始化列表
操作：查找、insert（无头部/尾部操作）、erase；不支持下标和修改元素
insert
- 直接插入一个元素的版本，其返回值是一个std::pair
执行查找操作，查看是否有元素
- count/find
自定义类型：需通过模板特化、运算符重载、函数对象定义比较规则
模板特化
- less
运算符重载
- <
函数对象定义
- compare
multiset
特征：存key，key可重复，默认升序
- 可以存储重复的key
- 范围查找
操作
查找功能（count、find）、插入功能（insert）、删除功能（erase）与set类似
有bound系列函数（lower_bound、upper_bound、equal_range）
equal_range(value)返回一个pair对象，包含两个迭代器：
- first：指向第一个等于value的元素。
- second：指向最后一个等于value的元素的下一个位置。
lower_bound(value)：返回指向第一个不小于value的元素的迭代器。
upper_bound(value)：返回指向第一个大于value的元素的迭代器。
自定义类型：与set相同
map
特征：存key-value，key唯一，默认按key升序
- 存放的关键字key不重复
操作：查找、insert（插入pair）、erase
执行查找操作，查看是否有元素
- count/find
map是具备下标的，其他三种关联式容器没有下标
支持下标访问运算符
1、查找key对象的value
- cout <<cities["100"] << endl
2、如果查询时对用的key不存在，会直接创建该key的记录
3、可以修改key对应的value
- cities["010"] = "武汉"
自定义类型：需通过模板特化、运算符重载、函数对象定义比较规则
multimap
特征：存key-value，key可重复，默认按key升序
- 存放的关键字可以重复
- 返回查找
自定义类型：需通过模板特化、运算符重载、函数对象定义比较规则
3、无序关联式容器
共性
底层实现
hash table
桶 + 单链表
加载因子
- 0.5
hash函数的设计
查找元素的时间复杂度O(1)
空间复杂度
- O(N)
支持前向访问迭代器
存放的元素是无序的
针对于自定义类型
必须给出Hash函数
1、自定义函数对象
- 函数对象的形式
2、扩展std::hash的模板特化版本
模板的特化
- Hash的默认采用的是std::hash
3、要将函数调用运算符设计成const版本
必须重载operator=
第三个模板参数KeyEqual的传参有三种方式：模板的特化、函数对象的形式、运算符重载
- 模板的特化
- 函数对象的形式
- 运算符重载
unordered_set
不能存放关键字相同的元素
不能使用下标访问运算符
执行查找操作，查看是否有元素
- count/find
unordered_map
不能存放关键字相同的元素
可以使用下标访问运算符
- 与map类似
执行查找操作，查看是否有元素
- count/find
unordered_multiset
- 可以存放关键字相同的元素
unordered_multimap
- 可以存放关键字相同的元素
萃取技巧
迭代器
迭代器本身的抽象级别要高于容器
迭代器设计模式的作业
- 将容器的底层实现隐藏起来
作用：对容器中的元素进行访问
广义的指针
种类
输入迭代器
Input Iterator
++/==/!=/*/->
- 可读
- 不需要关注写操作
输出迭代器
Output Iterator
++/*/=
- 可写
前向访问迭代器
Forward Iterator
- ++/==/!=/*/->/=
双向访问迭代器
Bidirectional Iterator
- ++/--/==/!=/*/->/=
随机访问迭代器
Random Access Iterator
- +/+=/-/-=/*/->/++/--/</>/<=/>=/==/!=/=
适配器
1、容器适配器
- stack
- queue
- priority_queue
2、迭代器适配器
流迭代器
- istream_iterator
- ostream_iterator
反向迭代器
- reverse_iterator
插入迭代器
- back_insert_iterator/back_inserter
- front_insert_iterator/front_inserter
- insert_iterator/inserter
3、函数适配器
- std::bind
- std::mem_fn
算法
作用：通过迭代器对容器中的元素进行操作
在操作时，只跟迭代器进行交互，与容器无关
算法在设计时，就不需要考虑容器，实现了算法与容器的解耦
分类
非修改式的序列操作
- 遍历
- 查找
修改式的序列操作
- 拷贝copy
- 替换replace
- 删除erase
排序
- 快排
- 堆排
最大最小值
二分查找
集合操作
- 差集、并集、补集、对称差分、子集
内存分配与释放有关的
- 空间配置器
函数对象(仿函数)
作用：针对于容器中的元素要做定制化操作的时候，需要借助于函数对象完成
包括
std::function
- 函数名
- 函数指针
- 重载了函数调用运算符的类创建的对象
std::function + std::bind
- 基于对象的思想
- 取代虚函数的地位
lambda表达式
空间配置器
作用：分配和释放内存
默认的空间配置器
底层实现(面试精华)
解决的问题
1、多线程
2、内存不足的措施
3、内存碎片的问题
外部碎片
堆空间
- 希望消除外部碎片的影响，节省内存
内部碎片
- 无法优化
os对于内存的管理
页式管理
- 4KB
段式管理
针对于程序
- 代码段
- 读写段
段页式管理
池的技术
- 进程池
- 线程池
- 内存池
- 数据库连接池
std::allocator
特点
针对容器来说，空间的分配与对象的创建是分开进行的，并不是绑定在一起的
是与new表达式不同的
对于批量元素进行操作
对象的创建
- construct
分配内存
- allocate
实现方式
一级配置器
- 当申请的空间大于128字节时，直接使用malloc/free
二级配置器
当申请的空间小于等于128字节时，采用16个自由空闲链表 + 内存池进行管理
16个自由空闲链表
- 指针数组管理
内存池
- 两个指针进行管理
源码
接口层
std::allocator
- allocate
- deallocate
- construct
- destroy
实现层
_Alloc
一级配置器
二级配置器
- 所有的容器最终都会调用它完成空间的分配和释放
总结
针对容器
- 容器操作是批量数据
以空间换时间
- 只有第一次申请空间时，会调用malloc，之后要申请小内存时，以O(1)时间复杂度分配内存
- 释放内存时，只有大于128字节的空间使用free，小于等于128字节的空间直接挂靠到相应的自由空闲链表之上，重复使用
减少系统调用malloc/free是使用频率
- 系统调用的开销比普通函数要大很多
