stl源码剖析

源码之前　了无秘密

STL概述

stl 不仅时可复用组件库还是包罗算法与数据结果的软件框架有六大组件容器算法迭代器仿函数配接器

GPL协议使用者可以自由阅读与修改GPL软件的源代码但如果使用着要传播借助GPL软件而完成的软件他们必须同意GPL规范

SGI STL 时可读性最高的一份STL

模板全特化对于特定类型需要对模板特化
eg:

template <class T>
class Compare
{
     public:
     bool IsEqual(const T& arg, const T& arg1);};

template <>
class Compare<float>
{
     public:
     bool IsEqual(const float& arg, const float& arg1);};

template <class T> 
bool Compare<T>::IsEqual(const T& arg, const T& arg1)
{
     cout<<"Call Compare<T>::IsEqual"<<endl;
     return (arg == arg1);}

bool Compare<float>::IsEqual(const float& arg, const float& arg1){
     cout<<"Call Compare<float>::IsEqual"<<endl;
     return (abs(arg - arg1) < 10e-3);}

模板偏特化提供另一份template定义式本身仍然时模板化的只是针对template参数更一步的条件限制所设计出来的特化版本。

eg:

template <class _Iterator>
struct iterator_traits{
 typedef typename _Iterator::iterator_category iterator_category;
 typedef typename _Iterator::value_type        value_type;
 typedef typename _Iterator::difference_type   difference_type;
 typedef typename _Iterator::pointer           pointer;
 typedef typename _Iterator::reference         reference;};

// specialize for _Tp*
template <class _Tp>
struct iterator_traits<_Tp*> {
 typedef random_access_iterator_tag iterator_category;
 typedef _Tp                         value_type;
 typedef ptrdiff_t                   difference_type;
 typedef _Tp*                        pointer;
 typedef _Tp&                        reference;};

空间配置器

class Foo{…}
Foo *pf = new Foo;
deflete pf

new有两段操作调用::operater new 配置内存调用 Foo::Foo() 构造对象内容 delete也有两段操作 Foo::~Foo() 将对象析构调用::operator delete释放内存
内存配置alloc::allocate()由负责内存释放由alloc::deallocate()负责对象构造由::construct()负责对象析构由::destroy()负责
stl 规定配置器：

construct 和 destroy

construct 接受一个指针和一个初值value 通过placement new 将初值设置到指定空间上

destroy 一个时只接受一个指针调用该对象的析构函数另一个时接受first和last迭代器将[first,last)范围内的对象析构并通过 typetraist判断该类型的析构函数是否无关痛痒
若是什么都不做如不是则析构该对象

alloc设计哲学：向heap请求空间考虑多线程应对内存不足应对内存碎片问题

SGI设计了双层配置器配置区超过128字节采用第一级配置器 malloc + free 第二级配置器根据不同情况采取不同策略

第一级配置器使用malloc和free 并封装一层接口

第二级配置器维护一个free_list[16] 分别指向8的倍数且不大于128区块，当free list喂初始化或空间不够从内存池申请空间。

POD意指 Plain Old Data 也就是标量型别或传统的C struct型别。POD型别必然拥有trivial ctor/dtor/copy/assignment函数可以对POD型采用最有效率的填写法对非POD采用保险的构造函数做法。

迭代器与traits编程技法

迭代器一种设计模式提供一种方法能够依次访问聚合物的各个元素而又无需暴露该聚合物的内部表达方式。迭代器是一种智能指针。
迭代器相应的型别：利用function template的参数推到机制
ctor == constructor
dtor == destructor

traits扮演“特性萃取机” 萃取各个迭代器特性。若要traits有效工作每个迭代器需要遵循约定自行以内嵌型别定义的方式定义出相应型别。对于原型指针可以使用偏特化模板

最常用的迭代器型别 value type , difference type, pointer, reference, iterator category

value type 迭代器所指对象的型别

difference type 两个迭代器之间的距离

reference type 迭代器所指之物引用

pointer type 迭代器所指之物的指针

iterator category 迭代器的类别，不同类别，函数实现方式不同，类别如下所示：

traits编程技法利用 “内嵌型别”的编程技巧和编译器template参数推导功能，增强c++未能提供的关于型别认证方面的能力。

序列式容器

vector 动态空间实现的关键是大小的控制和重新配置时数据移动的效率

vector insert的三种情况

插入点后元素个数大于插入元素个数

插入点后元素个数小于插入元素个数

空间不够

list 双向链表环状双向链表使用一个空白节点标记环链表的尾端

transfer操作源代码修改六个结点的指针 6次指针修改

list的transfer操作

list的sort算法

list<T, Alloc> counter[64]存放归并过程的中间变量
counter[0]里存放小于2^1次方个元素个数为2时进位并置空
counter[1]里存放小于2^2次方个元素个数为4时进位并置空
counter[2]里存放小于2^3次方个元素个数为8时进位并置空

使用merge进行归并排序

参考链接：

https://blog.csdn.net/qq276592716/article/details/7932483

deque
双向开口的连续线性空间，通过指针的指针map来管缓冲区

deque 迭代器示意图

deque的构造设置map_pointer的大小为每个node分配空间设置iterator start finish

stack 后进先出 container adapter 没有迭代器底层可以是list或deque

queue 先进先出 container adapter 没有迭代器底层可以是list或deque

heap 没有迭代器
完全二叉树最大堆或最小堆 stl提供的是最大堆

push_heap 算法将插入值放入尾端根据值大小向上调整

pop_heap算法根据值向下调整将头结点置于尾端

sort_heap算法不断使用pop_heap使之有序排序后的heap不是合法的

priority_queue 优先队列缺省情况下利用max-heap实现底端插入顶层输入权值最大的元素 container adapter 没有迭代器

slist 单向链表

关联式容器

avl树左右子树的高度最多相差1 单旋转双旋转
红黑树平衡二叉搜索树双向迭代器
(1) 每个节点不是红就是黑
(2) 根是黑
(3) 节点为红其子节点必须为黑
(4) 任一节点至NULL的任何路径其黑色节点数相同

插入操作详见算法导论

set 底层为RB-tree RB-tree是set中的成员变量 insert erase操作基于RB-tree的insert erase，multiset 允许键值重复调用的是RB-tree的insert_equal() 而不是insert-unique()

map 所有元素是pair两个元素不能拥有相同的键值底层为RB-tree RB-tree中元素是pair<key, value> RB-tree是set中的成员变量 insert erase操作基于RB-tree的insert erase，multimap 允许键值重复调用的是RB-tree的insert_equal() 而不是insert-unique()

hashtable
插入删除查询常数时间

散列函数计算出某个函数的插入位置若位置已经被用则顺序向下寻找到空位置为止
线性探测两个条件表格足够大每个元素相互独立

二次探测计算出的位置是H 依序尝试的H+1^2 H+2^2 H+3^2 … H+i^2 假设表格大小为质数且永远保持负载系数为0.5以下每插入一个元素探测次数不多于2

开链 hash函数为我们分配某一个list 在这个list上进行插入删除查询操作如果list足够短速度还是很快的。
维护linked list的桶子不是STL中的list或slist 而是vector

hashtable iterator 中包含hashtable的成员变量标记是forward_iterator_tag 只重载了operator++ 没有重载operator–

hashtable vector<node*, Alloc> buckets作为成员变量管理
所有节点 size_type num_elements 存储元素总数
参数：
Value 节点实值型别
Key 节点键值型别
HashFunc 哈希函数
ExtractKey 从节点中取出键值的方法（函数或仿函数）
EqualKey 判断键值相同与否
Alloc 空间配置器

SGI STL以质数设计表格大小先将28个质数计算好提供最接近某数并大于某数的质数

表格重建判断条件插入后元素总数大于 bucket vector的大小

resize 更加元素总数重新筛选质数并分配大小并将原来vector中的list 链接到新的vector中