C++STL標(biāo)準(zhǔn)庫(kù)與泛型編程

使用一個(gè)東西，卻不明白它的道理，不高明
——林語(yǔ)堂

• level 0：淺嘗C++標(biāo)準(zhǔn)庫(kù)
• level 1：深入認(rèn)識(shí)C++標(biāo)準(zhǔn)庫(kù)
• level 2：良好使用C++標(biāo)準(zhǔn)庫(kù)
• level 3：擴(kuò)充C++標(biāo)準(zhǔn)庫(kù)

C++ Standard Library vs. Standard Template Library

Standard Library 包含 Standard Template Library。

標(biāo)準(zhǔn)庫(kù)以header files 形式呈現(xiàn)

• C++標(biāo)準(zhǔn)庫(kù)的 header files 不帶副檔名 .h
• 新式 C header files 不帶副檔名 .h
• 舊式 C header files （帶有副檔名 .h）仍然可用
• 新式 headers 內(nèi)的組件封裝于 namespace "std"
• 舊式 headers 內(nèi)的組件不封裝于 namespace "std"

不同編譯器所帶的標(biāo)準(zhǔn)庫(kù)，使用起來(lái)毫無(wú)區(qū)別。

STL體系結(jié)構(gòu)基礎(chǔ)

STL六大部件（Components）：

• 容器（Containers）：放置數(shù)據(jù)
• 分配器（Allocators）：為數(shù)據(jù)對(duì)應(yīng)分配內(nèi)存
• 算法（Algorithms）：操作數(shù)據(jù)
• 迭代器（Iterators）：算法和容器的橋梁，一種泛化的指針
• 適配器（Adapters）：做轉(zhuǎn)換
• 仿函式（Functors）：作用像一種函數(shù)

一般容器有allocator默認(rèn)值，容器填充類型和分配器分配類型要一致。
迭代器可以參考指針的方式應(yīng)用。此函數(shù)適配器將less（a, b）比較a與b，bind2nd將第二個(gè)參數(shù)綁定為40，not1取非轉(zhuǎn)換為>=。

復(fù)雜度

描述程序執(zhí)行快慢，和應(yīng)用情景相關(guān)，在工業(yè)級(jí)數(shù)據(jù)量下，才體現(xiàn)出威力。

常見(jiàn)的 Big-oh 情形：

1. O(1)或O(c)：常數(shù)時(shí)間 constant time
2. O(n)：線性時(shí)間 linear time
3. O(log2 n)：次線性時(shí)間 sub-linear time
4. O(n^2)：平方時(shí)間 quadratic time
5. O(n^3)：立方時(shí)間 cubic time
6. O(2^n) : 指數(shù)時(shí)間 exponential
7. O(n*(log2 n))：介于線性及二次方成長(zhǎng)的中間模式

前閉后開(kāi)區(qū)間

容器的 begin() 指向容器中的第一個(gè)，end()指向容器中最后一個(gè)之后的下一個(gè)。
容器不一定在一段連續(xù)空間內(nèi)，不管是什么容器，內(nèi)存如何安排，都會(huì)提供 begin() 和 end() 。
所有容器都具有自己的迭代器實(shí)現(xiàn)。

range-based for statement （since C++11）

for(decl : coll) {  //declaration : collection
    statement
}

遍歷容器內(nèi)元素逐一操作。

auto keyword (since C++11)

編譯器自動(dòng)推導(dǎo)變量類型，
主要通過(guò)賦值操作進(jìn)行類型推導(dǎo)。

容器——結(jié)構(gòu)與分類

容器，如何在內(nèi)存中實(shí)現(xiàn)，如何描述元素間關(guān)系，對(duì)我們判斷不同算法對(duì)它的效率很關(guān)鍵。

分類

Sequence Containers

• Array：將C語(yǔ)言中的數(shù)組封裝成類，聲明大小的連續(xù)內(nèi)存空間，前后不可擴(kuò)充。
• Vector：起點(diǎn)不能動(dòng)，尾部可擴(kuò)充。需要增長(zhǎng)時(shí)，調(diào)用分配器自動(dòng)擴(kuò)充。
• Deque：雙向隊(duì)列，兩端可進(jìn)可出。
• List：雙向環(huán)狀鏈表。環(huán)狀只是為了實(shí)現(xiàn)方便。
• Forward-List：?jiǎn)蜗蜴湵怼?/li>

Associative Containers：可以快速通過(guò) key 找到 value

以紅黑樹(shù)（一種高度平衡的二叉樹(shù)，實(shí)現(xiàn)需要自我調(diào)整）實(shí)現(xiàn)，以避免查找時(shí)出現(xiàn)高度不對(duì)稱的奇異情況。
事實(shí)上，C++標(biāo)準(zhǔn)庫(kù)并未規(guī)定這兩種容器的實(shí)現(xiàn)方式，只是由于紅黑樹(shù)自身的優(yōu)越性，為各家編譯普遍采用

• Set/Multiset：value 既是 key，也是 value。
• Map/Multimap：有 key 和 value，key 用于查找，value 作為數(shù)據(jù)。
  Multi 表示可以重復(fù)。

Unordered Containers（可歸類到 2）：不定序元素，hash table separate chaining實(shí)現(xiàn)

容器測(cè)試

array

vector

兩倍增長(zhǎng)：放入元素，出現(xiàn)空間不足時(shí)，就分配是已有空間的兩倍的一份新空間，將原有元素逐一移動(dòng)過(guò)去，最后所占空間總大小對(duì)應(yīng)capacity()，size()表示存入的元素。
出現(xiàn)分配超荷載，用abort()退出

deque

buffer：分組存儲(chǔ)數(shù)據(jù)段，長(zhǎng)度指定
通過(guò)分段連續(xù)結(jié)構(gòu)，來(lái)將分散的代碼段，模擬成連續(xù)的一樣。（以建立map映射指針表的形式）

Tips

用namespace封裝測(cè)試代碼，
變量聲明和定義在測(cè)試時(shí)盡量不重排以提示應(yīng)用位置。