標(biāo)準(zhǔn)庫與泛型編程
內(nèi)容提示：泛型編程（GP)與面向?qū)ο缶幊?OOP)的根本差異，模板的意義以及運用。
課程目標(biāo)：
1.淺嘗C++標(biāo)準(zhǔn)庫
2.深入認(rèn)識C++標(biāo)準(zhǔn)庫
3.良好使用C++標(biāo)準(zhǔn)庫
4.擴充C++標(biāo)準(zhǔn)庫
STL vs CSL（標(biāo)準(zhǔn)模板庫 vs C++標(biāo)準(zhǔn)庫）：CSL=STL+else（其他內(nèi)容）
header files的寫法標(biāo)準(zhǔn)
注1：編譯器不影響標(biāo)準(zhǔn)庫的使用
注2：學(xué)習(xí)網(wǎng)址推薦
【1】 http://www.cplusplus.com/
【2】 http://en.cppreference.com/w/
【3】 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2118.html
STL六大部件
六大部件
容器（Containers）：用來存放數(shù)據(jù)。
分配器（Allocator）：負(fù)責(zé)空間配置與管理，實現(xiàn)動態(tài)空間的分配、管理、釋放。
算法（Algorithms）：模板編程，問題處理的策略、方法。
迭代器（Iterator）：泛化指針，扮演容器與算法間的“粘合劑）。
仿函數(shù)（Functors）：行為類似函數(shù)，可作為算法的某種策略。
適配器（Adapters）：修飾容器/仿函數(shù)/迭代器接口的東西，所有操作由底層的deque提供。
STL六大部件 應(yīng)用舉例
復(fù)雜度介紹：
big O
container 區(qū)間介紹
container 前閉后開區(qū)間
for loop的新用法
語法規(guī)則
auto keyword
auto 分析
容器結(jié)構(gòu)分析
三類容器
Sequence containers（序列式容器）按照放入次序排列
are ordered collectionsin which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element
Array：內(nèi)存連續(xù)容器，無法擴容
Vector:分配器負(fù)責(zé)處理內(nèi)存。增長方式為2的n次方（可能造成浪費）。
擴充方式，尾部自動擴充。
Deque：雙向隊列，兩端都可以擴充。
Deque 內(nèi)存申請方式
list：雙向鏈表（內(nèi)存不聯(lián)系）
forward-List：單向鏈表。內(nèi)存<雙向鏈表。
Associative containers（關(guān)聯(lián)式容器）
are sorted collectionsin which the position of an element depends on its value (or key, ifit’s a key/value pair) due to a certain sorting criterion.
使用范圍：快速查找（用key查找）底部為紅黑樹（高度平衡），map包含key，value（key！=value），set（key==value）set/map無法放入相同的元素，Multimap/multiset，元素可以相同。
Unordered (associative) containers（無序容器—特殊關(guān)聯(lián)容器）
are the hash function isfast. But because such a fast perfect hash function is not always possible or mightrequire that the array consumes a huge amount of memory, multiple elements might have the same position. For thisreason, the elementsin the array are linked lists so that you can store more than one element at each array position.
底層：hash table制作。bucket個數(shù)>element的個數(shù)。元素位置相同，方成鏈表，鏈表不能太長（影響查找速度），如果太長自動調(diào)整。
Unordered containers
容器舉例：
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
分配器
分配器代碼
分配器建議搭配容器使用。小額內(nèi)存 new()與delete（）以及malloc（）搭配free（）使用。如果直接用分配器申請內(nèi)存，還需要記住申請的個數(shù)（使用不方便）
OOP & GP
OOP（class 繼承， 虛函數(shù)）：數(shù)據(jù)與方法放在同一個類里。
GP：數(shù)據(jù)與方法分離。通過迭代器，實現(xiàn)方法對數(shù)據(jù)的調(diào)用。
Paste_Image.png
GP的優(yōu)勢：容器和算法的開發(fā)各自獨立，不需要考慮對方的問題，效率提高。屆時二者直接通過接口實現(xiàn)數(shù)據(jù)調(diào)用。
舉例：通過模板實現(xiàn)（比大小的方法）
Paste_Image.png
STL基礎(chǔ)：1、Operator Overloading（操作符重載）2、Templates（模板）
操作符重載規(guī)則
操作符重載規(guī)則
**模板：參照上一課程
參考書籍
容器、結(jié)構(gòu)與分類
容器 list
Paste_Image.png
Paste_Image.png
Paste_Image.png
Iterator (1.typedef 2.操作符重載）
Paste_Image.png
Paste_Image.png
traits
Paste_Image.png
Paste_Image.png
Paste_Image.png
容器 vector（動態(tài)增長的數(shù)組）
自動擴充，重新申請一個兩倍大的數(shù)組。非原地擴充
三個指針（start 、finish、end_of_storage)，sizeof（vector）=3×指針大小。默認(rèn)分配器alloc
Paste_Image.png
vector 成長的實現(xiàn)
查看finish與end
Paste_Image.png
vector使用會大量調(diào)用構(gòu)造及析構(gòu)函數(shù)，如果數(shù)據(jù)量大，要考慮時間成本
vector‘s iterator
G2.9版本
【4.9 暫時放棄看，沒必要】
Paste_Image.png
Paste_Image.png
Paste_Image.png
容器 array（固定大小的數(shù)組）
Paste_Image.png
連續(xù)空間，只需用指針做迭代器，不需要特殊設(shè)計。
【4.9 暫時放棄看，沒必要】
Paste_Image.png
容器forward_list（參考list看）
Paste_Image.png
容器 deque（分段連續(xù)空間）G2.9
雙向擴充的實現(xiàn)：迭代器跳到邊界時，node指向下一個緩沖區(qū)。
Paste_Image.png
map控制中心是一個vector
2.9版允許指定緩沖區(qū)的大小，通過BufSiz指定
deque插入元素時，可以自動判斷，距離頭近還是尾部近。然后移動短的一段。節(jié)省時間
Paste_Image.png
Paste_Image.png
deque模擬連續(xù)空間的方式
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
【G4.9】
Paste_Image.png
Paste_Image.png
容器queue&stack
queue
stack
用list做底部支撐，也能實現(xiàn)stack與queue的功能，代碼如下：
用list做底部支撐，也能實現(xiàn)stack與queue的功能
但是執(zhí)行效率沒有deque高？（猜測）
stack可以選擇vector做底部支撐，vector不支持queue的c.pop（）函數(shù)
Paste_Image.png
完全不能用map做底部支撐
完全不能用map做底部支撐
————————————————————————————————————————————————
關(guān)聯(lián)式容器
rb_tree（相當(dāng)于小型數(shù)據(jù)庫）
特點，高度平衡，可以實現(xiàn)快速插入以及查找
RB_TREE
Paste_Image.png
Paste_Image.png
Paste_Image.png
G2.9
G4.9
G4.9
Paste_Image.png
Paste_Image.png
Paste_Image.png
map
Paste_Image.png
Paste_Image.png
Paste_Image.png
Paste_Image.png
