STL源码剖析学习记录(一)

stl六大组件

1.容器(containers):如vector，list，set，map，从实现角度来看stl容器是一种类模板(class template)。

2.算法(algorithms):如sort，search，copy，erase... 从实现的角度来讲stl算法是一种函数模板(function template)

3.迭代器(iterators):算法与容器之间的胶合剂，可以认为是互相使用的工具，所谓的"泛型指针"。

4.仿函数(functors):行为类似函数，可作为算法的某种策略，从实现的角度，仿函数是一种重载了operator()的class或class template，一般函数指针可视为狭义的仿函数。

5.配接器(adaptor) 

6.配置器(allocators):负责空间配置与管理，从实现的角度来说，配置器是一个实现了动态空间配置，空间管理，空间释放的class template。

第二章 allocator

关于一级空间配置器：

直接使用malloc、free、realloc进行内存管理操作。且在内存不足时，会陷入oom_malloc，即模拟C++的set_new_handler。但没有new_handler，则抛出bad_alloc;

关于二级空间配置器：（避免太多小额区块照成内存碎片）

1. 对于大于128bytes的，直接使用malloc和free；
2. 对于小于128bytes的内存申请，使用16个空闲链表维护，每个链表相差8bytes。

a. 对于申请的内存会up到8的整数倍的大小size，再去据此查找合适的空闲链表。

b. 如果该空闲链表足够，则直接分配；

c. 否则，向内存池申请20个这样的size，如果内存池足够，则返回；

d. 否则，内存池如果有这样的size，则尽可能多的返回；

e. 否则，将内存池的剩余的空间赋予对应的空闲链表，并malloc申请40个这样的size的内存；

f. 如果申请成功，则进行正常返回（留20个在内存池）；

g. 如果申请失败，则调用一级空间配置器（其由oom的机制），分配40个这样的size的内存；

h. 如果一级空间配置器成功，则一切ok；否则，会触发bad_alloc；

this chapter fowards from https://zhuanlan.zhihu.com/p/148123661

第三章 迭代器与traits技巧

根据 type_tag 来进行最有效的迭代器操作，比如random access iter 支持 下标操作，bidirectional iterator 支持 ++ -- 操作

traits 编程技巧利用C++ 模板偏特化以及C++ template编译期类型推断的特性 有效解决template<const *T> template<*T> 等类型，在本书中让其直接归属于random access 类别

个人的理解在于添加了一个中间层，并利用C++模板类型推导 使其去执行返回值为模板类型，或者需要在函数中定义的模板类型，另外在处理指针与常量指针的时候，利用模板偏特化来执行特化的版本。从而达到类别推导的效果。此概念已经在effective c++一书中讲到过

第四章 序列式容器

1）vector

采用线性连续空间；（动态空间）

支持Random Access Iterators；（随机访问，时间复杂度为O(1)）

插入会导致之后的迭代器失效，如果引起扩容，则全部失效；删除会使得之后的迭代器失效；

2）list

采用环状循环链表；(有辅助头结点)

插入/接合不会使得迭代器失效；删除只会使得当前迭代器失效；

3）deque

采用分段连续线性空间；

允许在常数时间内对头端/尾端进行插入或删除；（当然中间的位置也可以操作，但复杂度高，设计数据的移动）

提供了Random Access Iterator，但是其内部实现复杂；

实现描述：

1. deque内部会维护一个map数组（存放指针指向一个连续的线性空间）；
2. 在中间删除erase元素时，会使得前面/后面的数据移动（选择需要移动数据少的方面进行移动）；对于插入insert类似；
3. 当map空间不够时，会存在map重分配策略：1）map没有占满一般时，会将map数组中的数据移动在中间，以使得前后空闲（比如一直在push_front，会出现这种情况）；2）否则，进行重新分配一个两倍大的map数组，并将原来的指向连续线性空间的指针拷贝进来，并交换两个map，释放旧map；

注：在动map数组时，由于首尾迭代器会指向map对应位置，因此也需要调整首尾迭代器；

1. 对于递增/递减迭代器，跨不同的连续线性空间时，会根据当前的map上的位置，查询到下一个map位置，再移动；
2. deque的数据存储空间是以连续线性空间为单位的；（多余时释放）

注：连续线性空间也被称为缓冲区；

4）stack（适配器，默认使用deque实现）

5）queue（适配器，默认使用deque实现）

6）heap（默认大顶堆）

实现一颗完全二叉树，且父节点大于子节点，并将其放置于vector数组中；（不提供遍历功能和迭代器）

对于插入节点，将其放置于最后的位置，然后进行percolate up上溯：将新节点与父节点比较，如果其值更大，则交换，直至不满足条件或者已达父节点；

对于删除最大节点（即堆顶节点），将其与最后一个元素的位置交换，然后进行percolate down下溯：将该节点和其较大的子节点对换，并持续下放，直至叶子节点；然后再对该叶子节点进行上溯（不能在中间直接停掉吗？？）

对于make_heap产生一个堆：从下往上构建堆。

注：将一颗完全二叉树存放在数组中，第一个元素不存放数据，之后将该颗完全二叉树层次遍历放入数组中，那么存在性质：在i处的节点，其左节点必然位于2*i，其右节点必然位于2*i+1;

7）priority_queue

采用heap实现，默认为大顶堆（less）；

不提供遍历和迭代器；

8）slist

单向链表；（有辅助头结点）

对于插入、删除、结合等不会使得迭代器失效；但是其中间删除/插入元素的时间复杂度为O(n)，因为其需要遍历以获取当前的前一个节点；因此最好在头部进行删除/插入元素操作；

只提供push_front，而不提供push_back；

this chapter fowards from https://zhuanlan.zhihu.com/p/148123661