本文预览：
- 源代码分布
- OOP(面向对象编程) 和 GP(泛型编程)
- STL内核基础：操作符重载与模板
- 分配器(Allocator)
- 探索std::list源码
- 迭代器的设计原则与Iterator Traits(萃取机)的设计与作用
- 探索std::vector源码
- 探索std::array源码
概述
对于C++的STL源码，相信大多数人没有看过的，即使看过也未必看得懂。为什么写了很久的C++代码却看不懂标准库的源码，原因也很简单，我们写的代码使用OOP编程，而模板使用的是GP编程，内部全是模板、迭代器，各种操作符重载，各种的typedef与预编译宏，再加上不同编译器以及同编译器不同版本的实现方式不同，使得阅读STL源码如同阅读天书一般。OOP企图将data和method结合起来放在class里，而GP企图将data和method分开。操作符重载和模板是阅读标准库源码的基础。
源代码分布
不同的编译器分布是不同的，但是所有的源码都在include文件夹下面。以mac为例：
bogon:include alex$ which g++
/opt/local/bin/g++
bogon:include zhouzhan$ cd ..
bogon:usr zhouzhan$ ls
bin lib local share
include libexec sbin standalone
include这里面就是我的GNU编译器存放的源代码了。Linux和这个做法应该是相同的。windows请自行百度。
OOP(面向对象编程) 和 GP(泛型编程)
- OOP企图将data和method关联起来
list为什么提供了自己的sort()
- GP企图将data和method分开
algorithms提供了sort()，vector和deque不需再写
GP将算法和数据分开的好处：
- 算法和容器独立开发，其间通过迭代器沟通。
- Algorithms可以通过Iterator来确定操作范围，并通过Iterator取用Container元素。
STL内核基础：操作符重载与模板
操作符重载之前在语言部分就讲过了，我们这儿就不再重复了，需要注意的是有四个操作符是不能重载的，(:: and . and .* and ?:)这四个知道就可以了，一般也没有人会去想重载他们。
模板分为：类模板、函数模板和成员模板，其核心就是类型替换。
关于类模板需要说的是特化和偏特化，这个在使用模板的时候用到的还是非常多的：
模板的特化
特化：顾名思义就是特殊处理，模板的意图就是泛化，恨不得所有的代码就用一个模板实现，但是有这是很难做到兼顾所有，即使兼顾了，性能也未必就满足要求，因此为了照顾某些特殊类型，模板实现了特化。
除了特化之外还有偏特化，这里的偏和偏微分方程一样，都是局部的意思:
偏特化
两个参数中，有一个是固定的类型或者其类型是根据泛化参数来定的。
分配器
分配器一般是给容器来操作内存空间的，虽然提供了外部调用接口，但是一般没有人直接调用Allocator来进行内存操作，分配器的原理就是调用new 和delete操作符，而new和delete又分别调用C的malloc和free，几乎所有的关于底层内存操作的都是malloc和free了，因为malloc和free调用的是系统级的调用，所以，如果我们不用过C或者C++语言，也就不需要关注内存的分配，像java或者js等脚本语言，其编译器或者解释器不但屏蔽了像malloc这样的方法调用，甚至连内存的概念都淡化了，用户不需要再管理内存，其内存的所有操作都有编译器或者解释器来完成，当然编译器和解释器就需要用C这样的系统级语言来写了。
分配器的使用
每一个容器在模板定义的时候都有俩参数，一个是类型，一个是分配器，但我们在使用模板的时候都是传一个参数:
vector<int>，我们没有传分配器，因为模板使用了默认的分配器。分配器承载了内存管理策略，正如malloc一样，如果你malloc的是一个int，那么显然你得到的内存还包括8个字节的cookie等其他描述内存的信息，假如我malloc了一个int，实际内存占了16个字节，那么如果我malloc了1000000个int，内存浪费是16*1000000，VC和Booland貌似就是这么干的，所以运行时非常消耗内存，GNU在2.9的时候用了16条链表来管理优化，很好的解决了这个问题，但是在4.9的时候又回来了，不知道什么原因。
一个分配器的简单用法：
#include<alloca.h>
int main(){
int* p = allocator<int>().allocate(512);
allocator<int>().deallocate(p, 512);
}
其缺点在于，回收的时候我还要告诉分配器回收多大的空间，这中设计显然不是给用户使用的，因为记录空间大小将是一件非常繁琐的事情。上述调用是临时对象调用。
探索std::list源码
2.9版本源码
上图是GNU 2.9版本的源码，虽然老了一点，但还是很清晰的，简单易懂，里面就一根指向node的指针。4.9的继承关系太复杂，需要花费很大的精力去读。
list迭代器部分
迭代器主要有两部分构成，一是各种typedef，二是操作符重载。
list的迭代器
迭代器的设计原则与Iterator Traits(萃取机)的设计与作用
算法通过迭代器操作容器中的数据，所以，算法需要通过迭代器对容器的一些特性做出理解，以便更好操作容器。标准库中定义了5种关联类型：
- iterator_category (迭代器的类型，能提供哪些操作)
- value_type (操作数据的类型)
- diffence_type (要操作的迭代器范围)
其他两种从来没有用到过。
迭代器与算法关系
那么问题来了，如果迭代器不是class，而是指针，那么这种迭代器就无法对这5种关联类型做出说明，为了解决这类问题，C++标准库引入了iterator_traits(迭代器萃取机)，由萃取机来做出说明，把萃取机实现为模板，通过偏特化来实现不同类型的Iterator。
通过偏特化实现的萃取机模板
探索std::vector源码
vector的源码实现比较简单了，里面有三根指针，元素开始和结束位置，存储空间结束位置。每次插入元素的时候都会检查finish指针是否到达最大存储空间，到的话就二倍增长，从新开辟一块新内存，把原来的内容拷贝过去，然后再销毁原来的内存。由此可见，实现动态增长是需要付出代价的，因为内存的开辟和拷贝都是耗时操作，而且还会造成内存的浪费。
vector
探索std::array源码
语言核心已经提供了静态数组，STL又把它封装了一层，C++11才出来的，感觉用的人不多吧应该，大概是为了把静态数组统一纳入STL中，以便使用迭代器和算法。
网友评论