C++標準庫（STL）學習筆記（一）容器
經典廢話
開始整標準庫，了解一門語言最好的方式就是看標準庫原始碼，確實能學到很多東西，前幾天面試阿里的實習，問了個C++智能指標，還好最近看視頻有看到，不然裂開了，所以學校里學的那點語言基礎是完全不夠用的，想找作業的話還是要自己多努力啊，
還有，最近查各種容器包括演算法的介面發現個網站http://www.cplusplus.com/挺方便的，省的百度了不靠譜，
正文
1、標準庫的內容
C++標準庫主要有六大組件，容器（Container），演算法（Algorithm），迭代器（Iterator），仿函式（Functor），配接器（Adapter），分配器（Allocator），標準庫中還包含一些其他部分，如cin和cout的實作，
這篇主要記錄與容器相關的學習所得，
2、泛型編程之特化與偏特化
泛型編程就是在實作類或函式時不指定某些要用的型別，由使用者決定，我是有接觸過一些泛型編程，沒深入了解過，如果讀者完全沒接觸過，建議先去了解一下，在C++標準庫中大量應用泛型編程的手法，因為對于幾乎所有的容器、演算法等內容，都要給予使用者自己指定型別的權力，這里主要寫新接觸到的特化與偏特化，
使用泛型時，我們會把決定型別的權力完全留給使用者，但是對于某些型別，或者某一型別別（有點奇怪），我們希望有特定的實作，這時就可以使用特化和偏特化，
（1）特化
一個小例子，也許并沒什么道理，我們想實作一個函式，傳入一個數，回傳它的平方，我們希望這個函式可以接受各種型別的引數，如int，float等，所以我們使用泛型，做了如下實作，
`
template <typename T>
T Sqr(T x){
return x * x;
}
`
寫完之后我們覺得，對于布林值的變數，對它計算平方值其實并沒有什么意義，因為0和1的平方都是自己，所以當傳入的變數是布林值的時候，直接回傳它本身就可以了，于是我們寫了一個特化的版本，
template <typename T>
T Sqr(T x){
return x * x;
}
template <>
bool Sqr(bool x){
return x;
}
這樣在傳入值為布爾型別的時候，編譯器會找到并呼叫特化的版本，
特化主要用于在泛型編程中對某些指定模板型別做特殊的處理，在有特化實作的時候，會優先呼叫特化的版本，在泛型類的實作中也可以使用特化，這里為了例子簡單使用的泛型函式，
（2）偏特化
繼續借用剛才的例子，在實作完特化之后，我們忽然覺得如果傳入的型別是指標型別的話，對它做平方運算并不合適，我們希望在使用者向我們的函式傳入指標型別時，能夠警告使用者這樣做不合理，
template <typename T>
T Sqr(T x){
return x * x;
}
template <>
bool Sqr(bool x){
return x;
}
template <typename T>
T* Sqr(T* x){
std::cout << "請勿對指標做平方運算，" << endl;
return nullptr;
}
這樣在使用者傳入的引數為指標時（不管是指向什么型別的指標），編譯器都會呼叫針對指標的偏特化版本，偏特化同樣適用于對常量（const T），參考（T&）等型別，同時，如果函式或類具有多個模板型別，指定其中的一部分，即部分特化，也叫做偏特化，
特化和偏特化在C++標準庫中大量使用并完成了很多看起來很神奇的功能實作，后面再說，
3、分配器（Allocator）
分配器在標準庫的六大組件里大約是最沒牌面的一個，很多課程都懶得去講它，在我這里它也沒牌面，被丟進寫容器的文章里順帶寫了，
分配器為容器服務，負責為容器分配合適的儲存空間，也就是一個包裝了幾層的malloc，有的編譯器和版本中的分配器有一些為了速度更快的設計，而大部分只是計算一下大小，用一下new而已，對使用者來講，在絕大多數的情況下根本不需要關心分配器的事情，在宣告一個容器時，編譯器會自動給它指定一個默認的分配器，
當然，其實程式員可以自己寫一個分配器，然后宣告容器時指定使用自己的分配器，然而我比較懶，不知道你們怎么想，
4、各大容器及他們的關系
標準庫中實作了很多的容器，下面列一個名單，其中非公開的意思是標準庫不想給你用，你非要用的話大約也是可以的，
非公開：紅黑樹（rb_tree），哈希表（hashtable），
序列容器：陣列（array），向量（vector），雙向佇列（deque），單向鏈表（forward_list），鏈表（list）， 堆疊（stack），佇列（queue），優先佇列（priority_queue），
關聯容器：集合（set），多重集合（multiset），映射（map），多重映射（multimap），（大約是這么翻譯吧，我也不知道）
無序關聯容器：無序集合（unorderd_set），無序多重集合（unordered_multiset），無序映射（unordered_map），無序多重映射（unordered_multimap），
這些名字和分類看著奇奇怪怪的沒關系，慢慢學嘛，用的多了就都了解了，后面寫的時候可能會用英文名字多一些，因為我感覺英文名字好理解，如果你不習慣就多熟悉吧，畢竟寫代碼的時候他不能用中文啊，
很多地方（包括）把堆疊、佇列、優先佇列分類為容器配接器（container adaptor），我因為懶，就丟一起了，其實官方分進容器里面的也有的其實是容器配接器，沒必要研究這些字眼，總之都可以當容器用，
在標準庫的容器中，并不是每一種都做了獨立實作，很多容器的實作是對其他容器的包裝，標準庫中包裝的方式是復合，即類中擁有一個其他類的成員，容器關系如下：
stack，queue衍生自deque，
priority_queue衍生自queue，
set，map，multiset，multimap衍生自紅黑樹，
unordered家族都衍生自哈希表，
紅黑樹和哈希表之所以不作為公開容器，就是因為這些容器對它們做了足夠完備的包裝，使用這些衍生容器就可以完成幾乎所有的要求，然而他確實在那，
5、List
C++中的List是雙向鏈表，單向的叫forward_list，是把list包了包做出來的，List的實作是一個環狀雙向鏈表，尾端添加了一個空白節點，以復合標準庫前閉后開的規范，很簡單，沒什么好說，
6、Array
Array容器是對陣列的包裝，內部就是一個陣列，如果給Array傳入0大小，會自動創建一個1大小的陣列，Array容器的迭代器是純正的一根指標，沒有構造和解構式，
7、Deque
Deque是stack和queue的基礎，如果寫演算法題的話，估計可以說一直在用deque，Deque用法上像一個雙向的vector，頭尾都可以添加和洗掉，
Deque的實作是分段連續，每一個buffer中是連續的，不同buffer天各一方，由deque中一個指標類的vector（控制中心）記錄每一個buffer的位置，大概就和盛飯一樣，一碗一碗盛，裝不下了就下一碗，Deque通過多載訪問運算子和特殊設計的迭代器來造成連續的假象，其實也就是在迭代器加減移動的時候多判斷一下會不會超出buffer邊界，如果會的話，就跑回控制中心然后跳到對應的buffer里去，
Deque支持insert，然而因為他是連續的，就要移動很多個元素，比vector好的是他有兩頭，可以找近的一邊，然后把那一邊的元素都挪一下騰個地方插入，
Deque的迭代器由四個指標構成，一個指向當前位置，這是每個迭代器都有的，第二個指向deque的控制中心里目前buffer對應的位置，剩下兩個指向目前buffer的頭尾，用來對是否越界做判斷，
stack和queue就是deque刪了一些功能，講道理的話完全屬于多此一舉，跟用deque沒區別，然而我也天天用，懶，那能咋辦，多說一句，其實stack和queue可以指定list為底層容器，然而可以想見的會慢一些，
8、rb_tree
紅黑樹是set和map的基礎，而且也是在學資料結構時常常會聽到的傳說，這個東西他確實比較復雜，我也不打算寫他具體運行的規則，雖然我研究過，有興趣的話可以去找來看看，反正估計觀看程序不會很愉快，
簡單地理解，紅黑樹就是一種平衡的二叉搜索樹，一個節點有兩個子節點，并且他內部的神奇操作讓整個樹處于平衡的狀態，平衡大概就是每根枝子差不多長，如果畫出來看會比較飽滿，不會一邊戳上天了另一邊沒長，這句話一點都不嚴謹，就是表達個意思，操作方式大概就是在加入元素和洗掉元素時晃悠晃悠，讓他繼續保持平衡，嗯，我也不知道我在說什么，
紅黑樹也具有二叉搜索樹的特性，是一個有序的容器，在這里說一句，紅黑樹包括set和map的頭（front）是最小的元素，并不是根節點，
紅黑樹的元素為鍵值對，key用來確定元素的位置，value是元素的內容，
9、Set和Map
為什么這兩個被沒有牌面地擠在了一起呢，因為他倆孿生兄弟，可以理解吧，這兩個都是紅黑樹親生孩子，只不過使用紅黑樹的方式有些許不同，他們都要求插入的元素的key在容器中獨一無二，
Set插入的是單一元素，也就是元素的key就是value，Set的元素不允許插入后修改，因為會影響它在樹中的位置，Set的迭代器也是const 迭代器，，
Map插入的是鍵值對，Map的元素可以修改，但修改的不是key，只能是value部分，Map的[]運算子會回傳key對應的value，如果該key不存在，會創建一個使用該key的元素，并且為它的value賦默認值，然后回傳，
multiset和multimap分別是上面兩個的分裂體，都可以插入多個key相同的元素，
10、Hashtable
哈希表也是資料結構中的老生常談了，具體原理我也不講了，大概就是根據hashfunction，每個元素會獲得一個號碼牌，根據號碼牌就能找到該存的地方，
Hashtable跟之前的容器都不一樣的地方在于，他不接受任意類的元素，如果你自己寫了一個類想用哈希表存盤，你還需要給出一個hashfunction，因為標準庫并不知道怎么給自定義的類發號碼牌，標準庫只給出了對于基本類的hashfunction，
寫哈希函式就很技術了，好的壞的效果差距很大，如果只是想能用的話，可以把自定義類中的一個或多個基本類的成員拿出來，分別使用他們的哈希函式算出來幾個號碼牌，然后把它們用某種方式結合一下，
unordered家族全都是從這里來的，里面具體的區別跟上面一欄講的是一樣的，可以自己聯想一下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/270558.html
標籤：C++
上一篇：CQGUI框架之陰影圓角視窗實作