課程概述
- 所謂 Generic Programming (GP, 泛型編程)析砸，就是使用 template （模板）為主要工具來編寫程序瘦锹。
- 本課程開宗明義闡述了 GP 與 OOP （Object Oriented Programming亭螟，面向?qū)ο缶幊蹋┑母静町愐角澹⒄劶?templates 的意義和運(yùn)用法褥。
- 本課程以 STL 為標(biāo)，深層次地探討泛型編程朝刊。（STL 正是泛型編程最成功的作品）
1. C++標(biāo)準(zhǔn)庫和標(biāo)準(zhǔn)模板庫（C++ Standard Library vs. Standard Template Library）[1]
C++強(qiáng)大的功能來源于其豐富的類庫及庫函數(shù)資源耀里。C++標(biāo)準(zhǔn)庫的內(nèi)容總共在50個標(biāo)準(zhǔn)頭文件中定義。
在C++開發(fā)中拾氓，要盡可能地利用標(biāo)準(zhǔn)庫完成冯挎。這樣做的直接好處包括：
- 成本：已經(jīng)作為標(biāo)準(zhǔn)提供，不用再花費(fèi)時間咙鞍、人力重新開發(fā)房官；
- 質(zhì)量：標(biāo)準(zhǔn)庫都是經(jīng)過嚴(yán)格測試的趾徽，魯棒性有保證；
- 效率：標(biāo)準(zhǔn)庫代碼的編寫團(tuán)隊(duì)都是業(yè)界大牛翰守，代碼的執(zhí)行效率有保障孵奶；
- 良好的編程風(fēng)格：采用行業(yè)中普遍的做法進(jìn)行開發(fā)。
1.1 C++標(biāo)準(zhǔn)庫（C++ Standard Library）
C++標(biāo)準(zhǔn)庫的內(nèi)容分為10類：
| C1-C5 | C6-C10 |
|---|---|
| C1. 語言支持 | C6. 容器 |
| C2. 輸入/輸出 | C7. 迭代器支持 |
| C3. 診斷 | C8. 算法 |
| C4. 一般工具 | C9. 數(shù)值操作 |
| C5. 字符串 | C10. 本地化 |
C1. 標(biāo)準(zhǔn)庫中與語言支持功能相關(guān)的頭文件（11個）
| 頭文件 | 描 述 |
|---|---|
| <cstddef> | 定義宏NULL和offsetof蜡峰，以及其他標(biāo)準(zhǔn)類型size_t和ptrdiff_t了袁。與對應(yīng)的標(biāo)準(zhǔn)C頭文件的區(qū)別是，NULL是C++空指針常量的補(bǔ)充定義湿颅，宏offsetof接受結(jié)構(gòu)或者聯(lián)合類型參數(shù)早像，只要他們沒有成員指針類型的非靜態(tài)成員即可。 |
| <limits> | 提供與基本數(shù)據(jù)類型相關(guān)的定義肖爵。例如卢鹦，對于每個數(shù)值數(shù)據(jù)類型，它定義了可以表示出來的最大值和最小值以及二進(jìn)制數(shù)字的位數(shù)劝堪。 |
| <climits> | 提供與基本整數(shù)數(shù)據(jù)類型相關(guān)的C樣式定義冀自。這些信息的C++樣式定義在<limits>中 |
| <cfloat> | 提供與基本浮點(diǎn)型數(shù)據(jù)類型相關(guān)的C樣式定義。這些信息的C++樣式定義在<limits>中 |
| <cstdlib> | 提供支持程序啟動和終止的宏和函數(shù)秒啦。這個頭文件還聲明了許多其他雜項(xiàng)函數(shù)熬粗，例如搜索和排序函數(shù)，從字符串轉(zhuǎn)換為數(shù)值等函數(shù)余境。它與對應(yīng)的標(biāo)準(zhǔn)C頭文件stdlib.h不同驻呐，定義了abort(void)。abort()函數(shù)還有額外的功能芳来，它不為靜態(tài)或自動對象調(diào)用析構(gòu)函數(shù)含末，也不調(diào)用傳給atexit()函數(shù)的函數(shù)。它還定義了exit()函數(shù)的額外功能即舌，可以釋放靜態(tài)對象佣盒，以注冊的逆序調(diào)用用atexit()注冊的函數(shù)。清除并關(guān)閉所有打開的C流顽聂，把控制權(quán)返回給主機(jī)環(huán)境肥惭。 |
| <new> | 支持動態(tài)內(nèi)存分配 |
| <typeinfo> | 支持變量在運(yùn)行期間的類型標(biāo)識 |
| <exception> | 支持異常處理，這是處理程序中可能發(fā)生的錯誤的一種方式 |
| <cstdarg> | 支持接受數(shù)量可變的參數(shù)的函數(shù)紊搪。即在調(diào)用函數(shù)時蜜葱，可以給函數(shù)傳送數(shù)量不等的數(shù)據(jù)項(xiàng)。它定義了宏va_arg耀石、va_end牵囤、va_start以及va_list類型 |
| <csetjmp> | 為C樣式的非本地跳躍提供函數(shù)。這些函數(shù)在C++中不常用 |
| <csignal> | 為中斷處理提供C樣式支持 |
C2. 支持流輸入/輸出的頭文件（11個）
| 頭文件 | 描 述 |
|---|---|
| <iostream> | 支持標(biāo)準(zhǔn)流cin、cout奔浅、cerr和clog的輸入和輸出馆纳，它還支持多字節(jié)字符標(biāo)準(zhǔn)流wcin、wcout汹桦、wcerr和wclog鲁驶。 |
| <iomanip> | 提供操縱程序，允許改變流的狀態(tài)舞骆，從而改變輸出的格式钥弯。 |
| <ios> | 定義iostream的基類 |
| <istream> | 為管理輸出流緩存區(qū)的輸入定義模板類 |
| <ostream> | 為管理輸出流緩存區(qū)的輸出定義模板類 |
| <sstream> | 支持字符串的流輸入輸出 |
| <fstream> | 支持文件的流輸入輸出 |
| <iosfwd> | 為輸入輸出對象提供向前的聲明 |
| <streambuf> | 支持流輸入和輸出的緩存 |
| <cstdio> | 為標(biāo)準(zhǔn)流提供C樣式的輸入和輸出 |
| <cwchar> | 支持多字節(jié)字符的C樣式輸入輸出 |
C3. 與診斷功能相關(guān)的頭文件（3個）
| 頭文件 | 描 述 |
|---|---|
| <stdexcept> | 定義標(biāo)準(zhǔn)異常。異常是處理錯誤的方式 |
| <cassert> | 定義斷言宏督禽，用于檢查運(yùn)行期間的情形 |
| <cerrno> | 支持C樣式的錯誤信息 |
C4. 定義工具函數(shù)的頭文件（4個）
| 頭文件 | 描 述 |
|---|---|
| <utility> | 定義重載的關(guān)系運(yùn)算符脆霎，簡化關(guān)系運(yùn)算符的寫入，它還定義了pair類型狈惫，該類型是一種模板類型睛蛛，可以存儲一對值。這些功能在庫的其他地方使用 |
| <functional> | 定義了許多函數(shù)對象類型和支持函數(shù)對象的功能胧谈，函數(shù)對象是支持operator()()函數(shù)調(diào)用運(yùn)算符的任意對象 |
| <memory> | 給容器忆肾、管理內(nèi)存的函數(shù)和auto_ptr模板類定義標(biāo)準(zhǔn)內(nèi)存分配器 |
| <ctime> | 支持系統(tǒng)時鐘函數(shù) |
C5. 支持字符串處理的頭文件（6個）
| 頭文件 | 描 述 |
|---|---|
| <string> | 為字符串類型提供支持和定義，包括單字節(jié)字符串(由char組成)的string和多字節(jié)字符串(由wchar_t組成) |
| <cctype> | 單字節(jié)字符類別 |
| <cwctype> | 多字節(jié)字符類別 |
| <cstring> | 為處理非空字節(jié)序列和內(nèi)存塊提供函數(shù)菱肖。這不同于對應(yīng)的標(biāo)準(zhǔn)C庫頭文件客冈，幾個C樣式字符串的一般C庫函數(shù)被返回值為const和非const的函數(shù)對替代了 |
| <cwchar> | 為處理、執(zhí)行I/O和轉(zhuǎn)換多字節(jié)字符序列提供函數(shù)稳强，這不同于對應(yīng)的標(biāo)準(zhǔn)C庫頭文件场仲，幾個多字節(jié)C樣式字符串操作的一般C庫函數(shù)被返回值為const和非const的函數(shù)對替代了。 |
| <cstdlib> | 為把單字節(jié)字符串轉(zhuǎn)換為數(shù)值退疫、在多字節(jié)字符和多字節(jié)字符串之間轉(zhuǎn)換提供函數(shù) |
C6. 定義容器類的模板的頭文件（8個）
| 頭文件 | 描 述 |
|---|---|
| <vector> | 定義vector序列模板渠缕，這是一個大小可以重新設(shè)置的數(shù)組類型，比普通數(shù)組更安全蹄咖、更靈活 |
| <list> | 定義list序列模板褐健，這是一個序列的鏈表，常常在任意位置插入和刪除元素 |
| <deque> | 定義deque序列模板澜汤，支持在開始和結(jié)尾的高效插入和刪除操作 |
| <queue> | 為隊(duì)列(先進(jìn)先出)數(shù)據(jù)結(jié)構(gòu)定義序列適配器queue和priority_queue |
| <stack> | 為堆棧(后進(jìn)先出)數(shù)據(jù)結(jié)構(gòu)定義序列適配器stack |
| <map> | map是一個關(guān)聯(lián)容器類型，允許根據(jù)鍵值是唯一的舵匾，且按照升序存儲俊抵。multimap類似于map，但鍵不是唯一的坐梯。 |
| <set> | set是一個關(guān)聯(lián)容器類型徽诲，用于以升序方式存儲唯一值。multiset類似于set，但是值不必是唯一的谎替。 |
| <bitset> | 為固定長度的位序列定義bitset模板偷溺，它可以看作固定長度的緊湊型bool數(shù)組 |
C7. 支持迭代器的頭文件（1個）
| 頭文件 | 描 述 |
|---|---|
| <iterator> | 給迭代器提供定義和支持 |
C8. 有關(guān)算法的頭文件（3個）
| 頭文件 | 描 述 |
|---|---|
| <algorithm> | 提供一組基于算法的函數(shù)，包括置換钱贯、排序挫掏、合并和搜索 |
| <cstdlib> | 聲明C標(biāo)準(zhǔn)庫函數(shù)bsearch()和qsort()，進(jìn)行搜索和排序 |
| <ciso646> | 允許在代碼中使用and代替&& |
C9. 有關(guān)數(shù)值操作的頭文件（5個）
| 頭文件 | 描 述 |
|---|---|
| <complex> | 支持復(fù)雜數(shù)值的定義和操作 |
| <valarray> | 支持?jǐn)?shù)值矢量的操作 |
| <numeric> | 在數(shù)值序列上定義一組一般數(shù)學(xué)操作秩命，例如accumulate和inner_product |
| <cmath> | 這是C數(shù)學(xué)庫尉共，其中還附加了重載函數(shù)，以支持C++約定 |
| <cstdlib> | 提供的函數(shù)可以提取整數(shù)的絕對值弃锐，對整數(shù)進(jìn)行取余數(shù)操作 |
C10. 有關(guān)本地化的頭文件（2個）
| 頭文件 | 描 述 |
|---|---|
| <locale> | 提供的本地化包括字符類別袄友、排序序列以及貨幣和日期表示。 |
| <clocale> | 對本地化提供C樣式支持 |
在這10類頭文件中霹菊，<cstdlib>頭文件分別在C5/C8/C9中出現(xiàn)了剧蚣。
1.2 STL，標(biāo)準(zhǔn)模板庫（Standard Template Library）
STL是惠普實(shí)驗(yàn)室開發(fā)的一系列軟件的統(tǒng)稱⌒ⅲ現(xiàn)主要出現(xiàn)在C++中鸠按，但在被引入C++之前該技術(shù)就已經(jīng)存在了很長一段時間。
STL的代碼從廣義上講可分為六大部件柳洋，幾乎所有的代碼都采用了模板類和模版函數(shù)的方式待诅，這相比于傳統(tǒng)的由函數(shù)和類組成的庫來說提供了更好的代碼重用機(jī)會。
在C++標(biāo)準(zhǔn)中熊镣，STL被組織為下面的13個頭文件：
<algorithm>卑雁、<deque>、<functional>绪囱、<iterator>测蹲、<vector>、<list>鬼吵、<map>扣甲、<memory>、<numeric>齿椅、<queue>琉挖、<set>、<stack>和<utility>涣脚。
1.2.1 算法
函數(shù)庫對數(shù)據(jù)類型的選擇和對其可重用性起著至關(guān)重要的作用示辈。舉例來說，一個求方根的函數(shù)遣蚀，在使用浮點(diǎn)數(shù)作為其參數(shù)類型的情況下的可重用性肯定比使用整型作為它的參數(shù)類型要高矾麻。
而C++通過模板的機(jī)制允許推遲對某些類型的選擇纱耻，直到真正想使用模板或者說對模板進(jìn)行特化的時候，STL就利用了這一點(diǎn)提供了相當(dāng)多的有用算法险耀。
它是在一個有效的框架中完成這些算法的弄喘，可以將所有的類型劃分為少數(shù)的幾類，然后就可以在模版的參數(shù)中使用一種類型替換掉同一種類中的其他類型甩牺。
STL提供了大約100個實(shí)現(xiàn)算法的模版函數(shù)蘑志，比如算法for_each將為指定序列中的每一個元素調(diào)用指定的函數(shù)，stable_sort以你所指定的規(guī)則對序列進(jìn)行穩(wěn)定性排序等等柴灯。
這樣一來卖漫，只要熟悉了STL之后，許多代碼可以被大大的簡化赠群，只需要通過調(diào)用一兩個算法模板羊始，就可以完成所需要的功能并大大地提升效率。
算法部分主要由頭文件<algorithm>查描，<numeric>和<functional>組成：
- <algorithm>是所有STL頭文件中最大的一個（盡管它很好理解）突委，它是由一大堆模版函數(shù)組成的，可以認(rèn)為每個函數(shù)在很大程度上都是獨(dú)立的冬三，其中常用到的功能范圍涉及到比較匀油、交換、查找勾笆、遍歷操作敌蚜、復(fù)制、修改窝爪、移除弛车、反轉(zhuǎn)、排序蒲每、合并等等纷跛。
- <numeric>體積很小，只包括幾個在序列上面進(jìn)行簡單數(shù)學(xué)運(yùn)算的模板函數(shù)邀杏，包括加法和乘法在序列上的一些操作贫奠。
- <functional>中則定義了一些模板類，用以聲明函數(shù)對象望蜡。
1.2.2 容器
在實(shí)際的開發(fā)過程中唤崭，數(shù)據(jù)結(jié)構(gòu)本身的重要性不會遜于操作數(shù)據(jù)結(jié)構(gòu)的算法的重要性，當(dāng)程序中存在著對時間要求很高的部分時脖律，數(shù)據(jù)結(jié)構(gòu)的選擇就顯得更加重要浩姥。
經(jīng)典的數(shù)據(jù)結(jié)構(gòu)數(shù)量有限，但是我們常常重復(fù)著一些為了實(shí)現(xiàn)向量状您、鏈表等結(jié)構(gòu)而編寫的代碼勒叠，這些代碼都十分相似，只是為了適應(yīng)不同數(shù)據(jù)的變化而在細(xì)節(jié)上有所出入膏孟。
STL容器就為我們提供了這樣的方便眯分，它允許我們重復(fù)利用已有的實(shí)現(xiàn)構(gòu)造自己的特定類型下的數(shù)據(jù)結(jié)構(gòu)。
STL容器對最常用的數(shù)據(jù)結(jié)構(gòu)提供了支持柒桑，這些模板的參數(shù)允許我們指定容器中元素的數(shù)據(jù)類型弊决，可以將我們許多重復(fù)而乏味的工作簡化。
容器部分主要由頭文件<vector>,<list>,<deque>,<set>魁淳，<map>,<stack>和<queue>組成飘诗。對于常用的一些容器和容器適配器（可以看作由其它容器實(shí)現(xiàn)的容器），可以通過下表總結(jié)一下它們和相應(yīng)頭文件的對應(yīng)關(guān)系：
| 數(shù)據(jù)結(jié)構(gòu) | 描述 | 實(shí)現(xiàn)頭文件 |
|---|---|---|
| 向量(vector) | 連續(xù)存儲的元素 | <vector> |
| 列表(list) | 由節(jié)點(diǎn)組成的雙向鏈表界逛，每個結(jié)點(diǎn)包含著一個元素 | <list> |
| 雙隊(duì)列(deque) | 連續(xù)存儲的指向不同元素的指針?biāo)M成的數(shù)組 | <deque> |
| 集合(set) | 由節(jié)點(diǎn)組成的紅黑樹昆稿，每個節(jié)點(diǎn)都包含著一個元素，節(jié)點(diǎn)之間以某種作用于元素對的謂詞排列息拜，沒有兩個不同的元素能夠擁有相同的次序 | <set> |
| 多重集合(multiset) | 允許存在兩個次序相等的元素的集合 | <set> |
| 棧(stack) | 后進(jìn)先出的值的排列 | <stack> |
| 隊(duì)列(queue) | 先進(jìn)先出的執(zhí)的排列 | <queue> |
| 優(yōu)先隊(duì)列(priority_queue) | 元素的次序是由作用于所存儲的值對上的某種謂詞決定的的一種隊(duì)列 | <queue> |
| 映射(map) | 由{鍵溉潭，值}對組成的集合，以某種作用于鍵對上的謂詞排列 | <map> |
| 多重映射(multimap) | 允許鍵對有相等的次序的映射 | <map> |
1.2.3 迭代器
迭代器從作用上來說是最基本的部分少欺，可是理解起來比前兩者都要費(fèi)力一些喳瓣。軟件設(shè)計(jì)有一個基本原則，所有的問題都可以通過引進(jìn)一個間接層來簡化赞别，這種簡化在STL中就是用迭代器來完成的畏陕。
概括來說，迭代器在STL中用來將算法和容器聯(lián)系起來仿滔，起著一種黏和劑的作用惠毁。
幾乎STL提供的所有算法都是通過迭代器存取元素序列進(jìn)行工作的，每一個容器都定義了其本身所專有的迭代器堤撵，用以存取容器中的元素仁讨。
迭代器部分主要由頭文件<utility>,<iterator>和<memory>組成：
- <utility>是一個很小的頭文件，它包括了貫穿使用在STL中的幾個模板的聲明实昨。
- <iterator>中提供了迭代器使用的許多方法洞豁，而對于<memory>的描述則十分的困難，它以不同尋常的方式為容器中的元素分配存儲空間荒给，同時也為某些算法執(zhí)行期間產(chǎn)生的臨時對象提供機(jī)制丈挟。
- <memory>中的主要部分是模板類allocator，它負(fù)責(zé)產(chǎn)生所有容器中的默認(rèn)分配器志电。
1.3 C++標(biāo)準(zhǔn)庫與STL的關(guān)系
STL是最新的C++標(biāo)準(zhǔn)函數(shù)庫中的一個子集曙咽，這個龐大的子集占據(jù)了整個庫的大約80%的分量。而作為在實(shí)現(xiàn)STL過程中扮演關(guān)鍵角色的模板則充斥了幾乎整個C++標(biāo)準(zhǔn)庫挑辆。
C++標(biāo)準(zhǔn)庫為C++程序員們提供了一個可擴(kuò)展的基礎(chǔ)性框架例朱。我們從中可以獲得極大的便利孝情，同時也可以通過繼承現(xiàn)有類，自己編制符合接口規(guī)范的容器洒嗤、算法箫荡、迭代子等方式對之進(jìn)行擴(kuò)展。
C++標(biāo)準(zhǔn)庫是std名字空間中的所有內(nèi)容渔隶，就是那些不帶.h的頭文件羔挡，如<cstdio>、<iostream>等间唉。如std::string绞灼，及IO流都不屬于STL，但它們是STL兼容的呈野，可以應(yīng)用迭代器低矮，算法等。雖然std::string和IO流也是模板類际跪，但并不屬于STL商佛。
2. 容器之分類與各種測試
c.end()指向最后一個元素的下一位置，對其解引用姆打，是尚未分配的地址良姆，結(jié)果不確定。
- 紅框：C++11新增的部分
- 標(biāo)準(zhǔn)庫里并沒有規(guī)定 set 或 map 應(yīng)該用什么方法來實(shí)現(xiàn)幔戏，但因?yàn)榧t黑樹非常好玛追，各家編譯器都用其來實(shí)現(xiàn) set 和 map。
2.1 array
編程細(xì)節(jié)： 當(dāng)用到某個變量時闲延，再聲明及定義痊剖。而且這些變量不縮排，方便查看垒玲。
71: c.data() - 數(shù)組在內(nèi)存起點(diǎn)的地址
75: clock() - 程序執(zhí)行到此處花銷 xx ms
76: qsort - 快速排序
77: bsearch - 二分查找
2.2 vector
- vector的空間是兩倍兩倍增長的陆馁。如果空間不夠，按1->2->4->8 的規(guī)則來申請新的空間合愈。也就是說叮贩，其大小只能是 2^n ( n = 0, 1, 2, ... ) ，如圖中需要1000000個空間佛析，實(shí)際上申請了 2^20 = 1048576個空間益老。
- try + catch : 防止出現(xiàn)分配不到內(nèi)存的情況。
- 127: 全局 find(...) 函數(shù)返回的是 iterator寸莫，類型太長不想寫捺萌，因此用 auto 自動推斷擅耽。
- 131: *pItem 得到的是 iterator 指向的 vector 中的數(shù)據(jù)碳蛋，不是我們手打的23456包颁。（意義不一樣）
- 順序查找 find 用時 0ms慷垮，快排+二分查找用時 2765ms ： 有時高級方法比傳統(tǒng)方法更耗時（時間花銷都在快排上）
2.3 list（forward_list and slist）
- 182：系統(tǒng)支持的最大尺寸训裆，對于不同類型容器田轧， max_size 也不一樣推沸。
- 197：不是使用全局的 sort()涩蜘，某些容器內(nèi)部也有自己定義的 sort()。（盡量使用容器特別定制的函數(shù)驮配，更有效率）
- 對于 forward_list，添加元素使用 push_front着茸，而不是 list 使用的 push_back壮锻。
Dev C++ 是開發(fā)環(huán)境，外掛的編譯器 GNU涮阔， slist 是 GNU 中的一種容器猜绣，跟 C++11 新增的 forward_list 類似。
508：注意其頭文件的特殊性敬特。
2.4 deque （stack and queue）
跟 vector 不同掰邢，當(dāng)空間不足，deque 會新增一個 buffer （往前或往后取決于 push_front 還是 push_back）
- stack 和 queue 都是借用 deque 的代碼實(shí)現(xiàn)其功能伟阔。從技術(shù)上來講辣之，把 stack 和 queue 都叫作 adapters。
- 它們只能單方進(jìn)皱炉，單方出怀估，為了保持其特性，它們都不提供 iterator合搅。
2.5 （unordered_）multiset and multimap
324：使用 insert 而不是 push多搀。具體放入的位置有其規(guī)則，放入時已經(jīng)排好序灾部。（紅黑樹）
- 379：插入時要自己 pair （key 和 value）
- 378：multimap 不可使用 [ ] 做 insertion康铭。
- 用 HashTable 支撐。
- 籃子（bucket）一定比數(shù)據(jù)多赌髓。（籃子數(shù)量也會兩倍擴(kuò)增）
443从藤、453：C.find(...)比 ：：find(...) 快很多，盡量用內(nèi)置算法春弥。
2.6 （unorder_）set and map
1000000個元素呛哟，每個都是 0~32767 的隨機(jī)數(shù)。 因?yàn)椴豢芍貜?fù)匿沛，set.size 僅為32768扫责。（Multiset 為 1000000）
- 710：
c[i] = string(buf); // i -> key and string(buf) -> value.- 718：雖然 value 有重復(fù)，都是 key 各不相同逃呼，因此 size 為 1000000鳖孤。
3. allocator（分配器）
紫色方框內(nèi)的是 GNU C 適用的者娱。
- 沒有必要單獨(dú)使用 allocator，它只含有 allocate 和 deallocate 函數(shù)苏揣，都是為了操作容器的內(nèi)存黄鳍。
- 盡量使用容器存儲數(shù)據(jù)，少量的數(shù)據(jù)就用 new + delete 分配內(nèi)存平匈，不要使用 allocator框沟。
-
第一章內(nèi)容在http://blog.csdn.net/rl529014/article/details/51154798基礎(chǔ)上改編并進(jìn)行了相應(yīng)的重排版。 ?
