之前有介绍过STL标准模板库 但是那时候由于个人的水平还不足与完全理解 于是再写一篇 让我们重新认识一下STL标准模板库
这里需要数据结构和了解进程地址空间的基础知识
STL库可以说是C++最核心的库之一了 提供了丰富的模板类 函数 让我们能够方便的处理常见的数据结构和算法
STL主要由以下的几个部分组成
- 容器 Containers
- 迭代器 iterators
- 算法 algorithm
- 函数对象 functors
- 适配器 adapters
- 空间配置器 allocators
接下来我们一一对其介绍 尽可能详细的讲解其中的原理
容器
容器可以说是STL中最常用的部分之一了 例如vector list map都属于这个内容 主要是为了存储和管理数据
基础的容器主要分为三类 序列式容器 关联式容器 无序容器
还有一种是容器适配器 关于适配器我们后面介绍 这里我们只需要知道他是对上述的三种基础容器进行封装 然后提供特定的功能
每一类下面有很多具体的容器 我们一一来介绍 对于容器中的迭代器和原理我们在迭代器部分介绍
序列式容器
序列式容器的特点就是所有的元素都是按顺序存储的 适合用于按顺序处理顺序的场景
==vector==
vector就是简单的动态数组 可以说是相对来说最简单的容器了
他支持O(1)时间的随机访问 O(n)时间的插入删除 是自动动态扩容和增长的数组
底层原理：
vector的底层原理也很简单 就是一个动态数组 开辟并维护一块内存
通常维护的成员变量就是两种思路
一种是起始地址+当前元素个数+容量元素个数
另一种是起始地址+最后一个元素的地址+1（下一个插入元素的位置）+容量末尾的地址
==deque==
双端队列
双端队列的逻辑上是一个队列 支持常数时间的头部和尾部的插入和删除操作 支持常数时间的随机访问 中间位置的插入和删除是O(n)的
底层原理
双端队列的底层原理是用指针数组+普通数组组成的 每一个指针数组都指向一个普通数组 也就是一个内存块 每个内存块都包含若干个元素
deque要找元素的时候就需要两步 第一步是获取数据中哪一个 第二步是定位到块中的具体位置
deque可以常数时间读取数据很好理解 因为每个内存块的大小都是固定的 因此只要知道序号就能算出具体的位置
例如 每个数组可以存10个元素 我们有10个这样的数组（从0到9） 假设这十个中除了头和尾都存满了 头里面存了3个 尾里面存了几个不重要 现在想访问第57个元素 因为头没存满 所以除了头 57-3=54 也就是除了头的剩下第54号元素 每个都存满了 所以是在第54/10=5 在第5号数组里面 具体是第几个呢 54%10=4 第4个 这样就能常数时间访问数据了
这里需要额外说明的是 在头部插入数据时 需要判断头部是否还有剩余空间 如果没有的话就需要申请新的内存块 然后更新指针数组
==list==
list的内部实现其实是一个双向链表 链表的每一个节点都包含前驱指针 后继指针 数据本身 他说支持常数时间的插入和删除 但是不支持O(1)的随机访问 虽然支持方括号访问数据 但是原理是用迭代器遍历的
初学者容易把指针变量和指针变量存储的地址混淆 要注意区分
==forward_list==
这个是另一种更轻量化的链表 只有向后的next指针 也就是单向链表 适合简单的数据流操作 每个节点包含数据和指向下一个节点的指针
关联式容器
关联式容器是存储的键值对 利用键来进行快速的查找 排序底层原理都是红黑树 是一种自平衡的二叉搜索树 后面我们也会单独出文章介绍
每一个节点存储的数据也是一个简单的容器pair 非常简单就是一个结构体
==set/multiset==
翻译过来就是集合 有O(logn)时间的插入 删除 查找 不允许相同的键
每一次插入的时候会自动排序让二叉树平衡 multi表示可以重复的键 但是不允许完全重复的键和值
==map/multimap==
map也是存储键值对 但是map可以有重复的值 也就是允许不同的键指向相同的值 multimap就允许相同的键和值了
无序容器
无序容器也是存储的键值对 实现原理都是哈希表 元素通过哈希函数计算得到哈希值 把对应的值存储值对应的桶中 当不同元素的哈希值相同冲突时 会采用一些冲突避免算法 线性探测 指数探测 或者用链表
所谓的桶也可以理解为是是固定长度的指针数组+普通数组
基本的时间复杂度都是O(1) 包括插入 删除查找
有 unordered_map/unordered_mutimap/unordered_set/unordered_mutiset
和之前的类似
容器适配器
这个东西其实就是对其他容器进行封装 然后提供特定的功能 例如栈 队列等
==stack==
这个东西就是先进后出 不允许随机访问 只允许值栈顶进行操作 通常是用vector或者deque进行封装
==queue==
这个就是普通的队列 先进先出 只允许队尾插入 队头取出
通常是基于deque实现进行封装
==priority_queue==
这个东西直接翻译过来是优先级队列 实际上所对应的数据结构就是堆 分为大根堆和小根堆 都可以指定 默认是大根堆
所有的元素按照优先级排序 优先级高的优先出队 也就是越大的优先级越高
底层原理就是一个堆 自动排序还是很香的 常用来解决top k问题
迭代器
我们使用容器这种数据结构无非就是因为其中的使用非常方便 其中的一个体现就是可以用一套操作来遍历容器 这里就是迭代器发挥了很重要的作用 而就是一种方便我们遍历容器元素的一种工具
根据不同类型的容器特定 迭代器也有很多不同的类型
- 输入迭代器 单向读取操作 不允许修改或回退 只能用于单向的遍历 一般用的地方就是输入流
- 输出迭代器 单向输出操作 不能读取或者修改 用的地方也就是输出流 或者就是某些容器的输出
- 前向迭代器 可读可写 只支持单向遍历 也就是++ 但是只能从前往后移动 单向链表forward_list用的就是这种
- 双向迭代器 也是可读可写的 支持向前和向后遍历 ++ – 都是可以的 例如list set map 虽然他们都支持方括号访问 但是时间复杂度并非上O(1)的
- 随机访问迭代器 支持常数时间的随机访问 都是通过指针运算来确定位置的 比如说vector deque array都是这样的
常见容器的迭代器类型
上面这种分类方式是根据迭代器提供的功能来分类 然而实际应用中我们也不太关心这里的分类 而是更加在意const迭代器 reverse反向迭代器 const reverse迭代器
额外的这三种难道说我们对每个容器都要重新设计吗 其实并不用 而是我们构建了一种迭代器适配器 将我们自行实现的一般迭代器自动适配到另外三种
常见容器的迭代器实现原理
迭代器的实现一定是跟容器及其特性强相关的 不同容器的迭代器实现起来也不一样
==vector==
vector的底层是一片连续的内存 因此我们可以把原生指针当作一个迭代器 因为他本身就指向元素的地址 + - 解引用 都是原生支持的 因此我们不需要额外定义
==list==
我们想要遍历整个链表 如果没有迭代器的话 是通过指针来进行移动的 但是list在遍历时的单位结构是一个节点 单纯的使用原生指针式不够用的
因此我们在实现list的迭代器时 就需要对节点进行封装 每一个迭代器存储的 或者说管理的是一个节点的指针
需要注意的是 迭代器本身并不知道他本身在链表的什么位置 头尾还是中间 这些东西是由链表来控制的
这其中+-运算符的重载就是把当前指向节点更改成指向上一个或者指向下一个 解引用的操作就是返回节点中数据的引用或者指针 除此之外还应该实现判断等于或者不等于的功能
==deque==
这个东西维护的是一个指针数组及每个指针维护的一片内存区域
因此他的迭代器需要维护的信息也很多 但是我们要知道这其中的数据单元是什么 其实还是元素本体 需要有 指向当前元素的指针（找到元素的基本单位） 指向整个指针数组的指针（用来找具体在哪一个缓冲区的指针）指向具体缓冲区的指针（表示当前元素所在的缓冲区）
+-是通过类似vector的检查越界来实现跨缓冲区访问 解引用是和vector一样的
==树形容器==
这种就包括set map等一系列容器了 维护的内容是指向树节点的指针 类似于list +-操作的顺序是中序遍历的 解引用和list一样
==哈希容器==
这种容器的底层是一个哈希桶 本身维护的是类似于deque一样的东西 只是缓冲区的大小是不定的 根据哈希桶实现的不同 迭代器也就有所不同了
例如和deque一样是数组加连续地址空间的那就是类似deque的模式
如果是和list一样 数组后面加的是链表的内容 就是类似于list的模式来实现迭代器了
适配器
前面我们已经多少用到适配器的内容 能够大概理解适配器这个东西是用来干嘛的 他主要是用来将已有的 容器 函数 迭代器 进行包装或者转换 让其能够满足我们的需求 让我们少写重复实现的代码
例如容器适配器 迭代器适配器 函数适配器
容器适配器
这个就是对我们原有的容器进行封装 提供特定的功能和接口 从一个容器到另一个符合我们要求的容器
例如stack queue priority_queue
迭代器适配器
迭代器适配器是将已有的容器的迭代器进行封装 让其能够实现比如说反向迭代器 或者const迭代器的功能 这就是从一个迭代器到另一个符合我们要求的迭代器
他的模板参数就是原来的普通迭代器
还有其他的比如说insert适配器 让算法能够直接对容器执行插入操作 例如 back_inserter
函数适配器
这里需要结合函数对象来理解
函数对象
这个东西上提供了一种将函数行为转换为类对象的机制，也就是仿函数对象
STL提供了许多仿函数
- 算术运算类（Arithmetic Functors）：
- plus
：加法操作。 - minus
：减法操作。 - multiplies
：乘法操作。 - divides
：除法操作。 - modulus
：取模操作。 - negate
：取负操作。2.
- plus
- 关系运算类（Relational Functors）：
- equal_to
：等于比较。 - not_equal_to
：不等于比较。 - greater
：大于比较。 - less
：小于比较。 - greater_equal
：大于等于比较。 - less_equal
：小于等于比较。
- equal_to
- 逻辑运算类（Logical Functors）：
- logical_and
：逻辑与操作。 - logical_or
：逻辑或操作。 - logical_not
：逻辑非操作。
- logical_and
- 位运算类（Bitwise Functors）：
- bit_and
：按位与操作。 - bit_or
：按位或操作。 - bit_xor
：按位异或操作。
- bit_and
- 通用适配器类（Function Adaptors）：
- 绑定器：如 bind1st、bind2nd，用于将二元函数对象转化为一元函数对象。
- 否定器：如 not1、not2，将函数对象取反，返回相反结果。
- 成员函数适配器：如 mem_fun、mem_fun_ref，用于将成员函数绑定为函数对象。
函数适配器
既然函数对象可以看作对象来传递 看作函数来使用 对于他来说最难以确定的其实就是参数 还有调用方式
最常用的函数适配的一个方法就是bind
在这样一个场景中 在一个类中的成员是一个回调函数 我们想要传递的这个回调函数是另一个类的成员函数 这样的话对于回调函数的设计就很局限了
如果没有函数适配器 我们不得不在回调函数的第一个参数类型设置为第二个类指针 因为成员函数的第一个隐藏参数就是this指针
那想要传入其他类的成员函数不久不行了
bind函数适配器就可以解决这个问题 他可以把原来的函数参数进行绑定 进行预先的传值 例如吧this指针提前传递给这个成员函数 然后生成一个新的函数对象
接着这个新生成的函数对象 就能够作为回调函数传递了 因为这个函数对象接收的参数就是原来成员函数中没有绑定的参数
这个思想就是从一个函数到另一个符合我们要求的函数的思想
空间配置器
空间配置器也是一个宏大的话题 他说未来各个容器高效管理内存空间而存在的 我们中正常使用STL的时候很难察觉到
但是在我们自己模拟实现STL的相关容器时 却从来没有用到 都是用的new
这就有一些不足之处了
- 自行管理空间的申请和释放容易造成内存泄露
- 频繁申请小块内存 容易造成内存碎片 也会影响程序运行的效率
- 申请失败时没有任何办法
- 代码结构比较混乱 复用率也不高
- 没有考虑线程安全问题
我们迫切的需要一个内存管理模块 让我们方便好用的实现内存管理
解决问题时我们需要区分主要矛盾和次要矛盾 这里的主要矛盾其实是由于频繁申请小块内存引起的内存碎片 低效导致的 而这个问题解决了 剩下的也就好说了
STL通常把128字节作为小块内存和大块内存的分界线 我们对大块内存和小块内存分别进行处理和利用
对于大块内存使用一级空间配置器 对于小块内存使用耳机空间配置器
一级空间配置器
一级空间配置器很简单 因为他本身就是为大块内存来服务的 new和malloc就已经足够使用
而对于内存分配失败的情况 也不会单纯的直接抛异常结束程序 而是支持用于传入函数对象来进行内存分配失败时的调用
二级空间配置器
二级空间配置器时专门用来负责处理小块内存的申请的 那要怎么才能提升小块内存申请与释放的效率呢
聪明的你肯定想到了池化技术 之前的文章我们有说过进程池 线程池
这里就是需要内存池了
内存池
内存池就是我们先申请一块比较大的内存作为备用内存 当需要内存的时候 直接到内存中取 当内存池也不够的时候 再去内存本体中去 当用户内存也不够的时候 我们直接把内存池还给用户
这样就能达到一次申请终身适用的效果了
这里的图示是逻辑上的 实际中的实现比这个要略微复杂一点 主要是因为我们无法确定程序何时会归还申请的内存 怎么样尽量提高内存的利用率
二级空间配置器的设计
怎么对每一段还没有利用的内存进行管理成了问题 这又回到了那个熟悉的管理问题 解决方法就是先描述 再组织
我们描述一个内存区域需要什么 其实就是需要起始地址和结束地址就够了 这样既可以分配个给具体的申请请求 有能够知道内存区域的大小
那要怎么组织起来呢 考虑到分配效率 频繁的查找 插入 删除 那肯定是效率越高越好 最好还能排个序 直接分配给刚好够用的就行
答案呼之欲出 那就是 哈希桶 将内存块大小作为索引 将一系列符合要求的小内存块 和大内存块串在一起 用的时候直接取 香啊
这里以8字节作为增量主要是因为内存对其问题 小了不够用 大了用不完
正规空间配置器的使用逻辑就是 先判断申请内存是否大于128字节 大于直接由一级配置器神器 小于则直接去哈希桶中找 找得到就直接给了 找不到就向上继续申请更大一点的内存块
更加详细的实现细节可以看我之后再STL模拟实现的库中的ReadMe和文档
https://github.com/Ye-Yu-Mo/XuSTL
空间配置器的再次封装
申请的内存可能是任意类型的 连续空间或者 单个对象的空间 每一次都让用户自己计算大小就不是很好 要是能像new就好了
对于对象的构造和析构在空间的申请和释放是分开的 有些对象的构造不需要构造函数 有些对象析构不需要析构函数 将这两个过程分开就能提高程序的性能了 前提是我们需要通过类型萃取来获取类型是否调用 可以通过迭代器来获取 这部分也是比较复杂的
接下来这个空间配置器就能正常工作的来 用于我们自行实现的容器
算法
具体的算法原理这里不做讲解 这里只是介绍STL的接口
这里的算法并不限定某一种容器 这得益于迭代器的实现 在算法顶层上看 他们都是一样的
- 非修改序列算法 for_each find count find_if adjacent_find
- 修改序列算法 copy copy_if replace replace_if remove remove_if unique transform
- 排序算法 sort stable_sqrt partial_sort nth_element merge partition stable_partition
- 集合操作 set_union set_intersection set_difference set_symmetric_difference
- 数值算法
- 堆算法 push_heap pop_heap make_heap sort_heap
- 二分查找 binary_search lower_bound upper_bound equal_range