0. 背景
STL是什么？
STL(Standard Template Library)标准模板库的英文缩写，包含有计算机科学领域常用的基本数据结构和基本算法。
STL与C++标准库的关系
版本
| No. | 版本 | 作者 | 是否开源 | 特点 |
|---|---|---|---|---|
| 1 | HP STL | [美]Alexandar Stepanov/[美]Meng Lee | 是 | 第一个实现版本 |
| 2 | SGI STL | [美]Alexandar Stepanov | 是 | GCC使用版本，源码可读性高 |
| 3 | STLport | [俄]Boris Fomitchev | 是 | 适用于VC++和C++ Builder等多种编译器，跨平台可移植 |
| 4 | P.J.Plauger STL | [美]P.J.Plauger | 否 | Visual C++使用版本，性能教高 |
| 5 | Rouge Wave STL | Rouge Wave公司 | 否 | Borland C++ 5.0-使用版本 |
参考:《STL源码剖析》侯捷
1. STL 的组成
STL Components
| No. | Component | 部件 | 作用 | |
|---|---|---|---|---|
| 1 | Container | 容器 | 存储数据 | |
| 2 | Iterator | 迭代器 | 遍历容器数据 | |
| 3 | Adaper | 适配器(配接器) | 容器转换 | |
| 4 | Algorithm | 算法 | 通用算法 | |
| 5 | Function Object/Functor | 函数对象/仿函数(函数子) | ||
| 6 | Allocator | 分配器(配置器) | 分配释放内存 |
程序 = 数据结构(容器) + 算法
迭代器是容器与算法的桥梁
2. 容器分类
分类原则：结构
| No. | Container | 容器 | e.g. |
|---|---|---|---|
| 1 | Sequence Container | 顺序容器（序列容器） |
vector,list,deque
|
| 2 | Associative Container | 关联容器 |
map,``multimap,set,multiset` |
| 3 | Container Adapter | 容器适配器 |
stack,queue,priority_queue
|
3. 迭代器分类
- 分类原则：访问方式
| No. | Iterator | 迭代器 | 能力 | e.g. |
|---|---|---|---|---|
| 1 | Input Iterator | 输入迭代器 | 向前读取能力 | istream_iterator |
| 2 | Output Iterator | 输出迭代器 | 向前写入能力 | ostream_iterator |
| 3 | Forward Iterator | 向前迭代器 | 向前读取写入能力 | - |
| 4 | Biredirectional Iterator | 双向迭代器 | 双向读取写入能力 |
list,map,set的iterator
|
| 5 | Random-Access Iterator | 随机访问迭代器 | 随机读取写入能力 |
string,vector,deque的iterator
|
- 分类原则：操作类型
| No. | Iterator | 迭代器 | e.g. |
|---|---|---|---|
| 1 | iostream Iteractor |
iostream迭代器 |
istream_iteractor,ostream_iteractor
|
| 2 | Insert Iteractor | 插入迭代器 |
back_inserter,front_inserter,inserter
|
| 3 | Reverse Iteractor | 反向迭代器 | reverse_iteractor |
3. 适配器分类
分类原则：适配部件
| No. | Adapter | 适配器 | e.g. |
|---|---|---|---|
| 1 | Container Adapter | 容器适配器 |
stack,queue,priority_queue
|
| 2 | Iterator Adapter | 迭代适配器 |
back_inserter,front_inserter,inserter
|
| 3 | Function-Object Adapter | 函数对象适配器 |
bind1st,bind2nd,not1,not2
|
4. 算法分类
分类原则：按操作类型
| No. | Algorithm | 算法 | e.g. |
|---|---|---|---|
| 1 | Read Only | 只读算法 |
find,count,search,for_each,mismatch,equal,binary_search
|
| 2 | Write Only | 写容器算法 |
fill,generate,copy,transform,merge,swap,replace
|
| 3 | Sort | 排序算法 |
sort,stable_sort,reverse
|
5. 函数对象分类
分类原则：运算类型
| No. | Function Object | 函数对象 | e.g. |
|---|---|---|---|
| 1 | Arithmetic Function-Object | 算术函数对象 |
plus<T>,minus<T>,multiplies<T>,divides<T>,modulus<T>,negate<T>
|
| 2 | Relational Function-Object | 关系函数对象 |
equal_to<T>,not_equal_to<T>,less<T>,less_equal<T>,greater<T>,greater_equal<T>
|
| 3 | Logical Function-Object | 逻辑函数对象 |
logical_and<T>,logical_or<T>,logical_not<T>
|
6. 分配器
功能：获取释放内存
