0. 背景
STL是什么？
STL(Standard Template Library)標(biāo)準(zhǔn)模板庫的英文縮寫，包含有計算機科學(xué)領(lǐng)域常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。
STL與C++標(biāo)準(zhǔn)庫的關(guān)系
版本
| No. | 版本 | 作者 | 是否開源 | 特點 |
|---|---|---|---|---|
| 1 | HP STL | [美]Alexandar Stepanov/[美]Meng Lee | 是 | 第一個實現(xiàn)版本 |
| 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 | 容器 | 存儲數(shù)據(jù) | |
| 2 | Iterator | 迭代器 | 遍歷容器數(shù)據(jù) | |
| 3 | Adaper | 適配器(配接器) | 容器轉(zhuǎn)換 | |
| 4 | Algorithm | 算法 | 通用算法 | |
| 5 | Function Object/Functor | 函數(shù)對象/仿函數(shù)(函數(shù)子) | ||
| 6 | Allocator | 分配器(配置器) | 分配釋放內(nèi)存 |
程序 = 數(shù)據(jù)結(jié)構(gòu)(容器) + 算法
迭代器是容器與算法的橋梁
2. 容器分類
分類原則：結(jié)構(gòu)
| No. | Container | 容器 | e.g. |
|---|---|---|---|
| 1 | Sequence Container | 順序容器（序列容器） |
vector,list,deque
|
| 2 | Associative Container | 關(guān)聯(lián)容器 |
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 | 函數(shù)對象適配器 |
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. 函數(shù)對象分類
分類原則：運算類型
| No. | Function Object | 函數(shù)對象 | e.g. |
|---|---|---|---|
| 1 | Arithmetic Function-Object | 算術(shù)函數(shù)對象 |
plus<T>,minus<T>,multiplies<T>,divides<T>,modulus<T>,negate<T>
|
| 2 | Relational Function-Object | 關(guān)系函數(shù)對象 |
equal_to<T>,not_equal_to<T>,less<T>,less_equal<T>,greater<T>,greater_equal<T>
|
| 3 | Logical Function-Object | 邏輯函數(shù)對象 |
logical_and<T>,logical_or<T>,logical_not<T>
|
6. 分配器
功能：獲取釋放內(nèi)存
