C++ STL内部簡單細節整理

對于使用C++語言進行項目開發的同學，STL必然是必須掌握并且熟練的技術。除了能夠熟練使用，我們當然也有必要知道其内部實作原理。當然，對于新手或者并屬于一線開發者的同學，一下子看懂STL源碼是不現實的，但是我們可以從簡單的地方入手，慢慢去了解掌握它。下面我就總結一些最基本的細節。

STL的構成

大部分人可能知道STL包括容器，疊代器，算法。其實，STL還包括比較重要的函數對象，擴充卡，記憶體配置設定器，概念和模型。這裡分别挑重點說一下。

函數對象（Function Object）

先說函數對象吧，哈哈。在C++中我們知道函數指針，它将具有相同類型和個數的輸入參數和傳回值的一組函數抽象出來。這為代碼靈活性做出來貢獻。但是在STL中，我們使用函數對象而不是函數指針——這其實也是C++進階特性中的一貫做法，将指針封裝成一個對象去使用。疊代器啦，智能指針啦，都是這樣子的。需要注意的一點是，為了使用上直覺，我們需要重載函數對象的運算符()，這樣當函數調用其()成員函數時，就好像還是在使用一個函數一樣。

擴充卡（Adapter）

C++ STL中所謂的擴充卡，作用相當于一個類型轉換。可以轉換函數對象，疊代器，甚至是容器等。其實這是為了利用已有的代碼或者資料結構泛化實作擴充的資料結構而已，因為好多STL的子產品内部實作是差不多的。比如雙參數的函數對象，可以通過賦予其中一個參數某個值，轉換成單參數的函數對象；reverse_iterator疊代器是由iterator疊代器轉換移動方向相反之後實作的；stack棧容器，本身并沒有什麼實質性的代碼，隻是将底層容器轉換為“後進先出”的stack容器。

容器（Container）

容器是STL中專門存放資料的一組資料結構。其它的不多說，這裡主要說明一下每一種容器都是用什麼基本的資料結構實作的，這個在面試中經常遇到。

1 vector

vector可能是最常用的資料結構了，其内部是用數組實作的。也難怪，vector就是一個進階數組，尤其是少有的支援用中括号随機存儲。既然是數組實作的，那麼當所存儲的資料超出初始數組容量大小的時候怎麼辦？好辦，這樣的話，vector會重新申請一塊更大的記憶體，大小為原來的兩倍，然後将原來記憶體的資料拷貝到新記憶體中，再釋放原記憶體。這樣帶來一個問題，當資料量不斷增大，vector就會不斷進行動态記憶體的申請和釋放，這樣嚴重影響效率。于是，如果我們開始的時候知道資料的最大數量，就可以在最開始的時候，為vector配置設定足夠大的記憶體，用的的函數是vector對象的reserve()和resize()函數。vector 的reserve增加了vector的capacity，但是它的size沒有改變！而resize改變了vector的capacity同時也增加了它的size！原因如下：

reserve是容器預留白間，但在空間内不真正建立元素對象，是以在沒有添加新的對象之前，不能引用容器内的元素。加入新的元素時，要調用push_back()/insert()函數。

resize是改變容器的大小，且在建立對象，是以，調用這個函數之後，就可以引用容器内的對象了，是以當加入新的元素時，用operator[]操作符，或者用疊代器來引用元素對象。此時再調用push_back()函數，是加在這個新的空間後面的。

兩個函數的參數形式也有差別的，reserve函數之後一個參數，即需要預留的容器的空間；resize函數可以有兩個參數，第一個參數是容器新的大小，

第二個參數是要加入容器中的新元素，如果這個參數被省略，那麼就調用元素對象的預設構造函數。

2 list

list可以認為就是一個環形雙向清單，隻不過封裝後成為了STL的一個普通容器。

3 deque

deque則采用的是vector和list的結合，所謂結合，并不是兩種資料結構的結合，而是某些性能上的結合。我們知道，vector支援随機通路，而list支援常量時間的删除，deque支援的是随機通路以及首尾元素的删除。deque的内部實作嘛，首先盜圖一張：

deque容器的元素資料采用一種分塊的線性結構存儲。deque分成若幹線性存儲塊，稱為deque塊，塊的大小一般為512個位元組，元素的資料類型所占用的位元組數，決定了每個deque塊可容納的元素個數。所有的deque塊使用一個Map塊進行管理，每個Map塊資料項記錄各個deque塊的首位址。類似于一個二維數組，要支援随機存儲，首先需要從map中找到“二維數組”的第一維，然後再從相應的連續空間中找“二維數組”的第二維。更多詳細說明請點選這位老兄的部落格。

4 stack和queue

這兩個容器合起來叫堆棧，stack是棧，queue是堆。它們是直接利用STL中的現有容器泛化實作的。預設使用雙端隊列deque的資料結構，當然也可以采用其他線性表（如vector或list），隻要提供堆棧的入棧、出棧、棧頂元素通路和判斷是否為空的操作即可。由于堆棧的底層使用是其他容器，是以，堆棧可看作是一種擴充卡，将一種容器轉換為另一種容器。

5 priority_queue優先隊列容器

優先級隊列也是一種從一端入隊，另一端出隊的隊列。不同于一般隊列的是，隊列中最大的元素總是位于隊首位置，是以，元素的出隊并非按照先進先出的要求，而是将目前隊列中最大元素出隊。

C++ STL優先隊列的泛化，底層預設采用vector向量容器，使得優先級隊列的元素可做數組操作，進而應用堆算法找出目前隊列最大元素，并将它調整到隊首位置。

優先級隊列也可以看做容器擴充卡，将底層的序列容器vector轉換為優先隊列。

6 string字元串容器

C語言并沒有提供一個專門的字元串類型，需要通過字元數組，對字元串進行存儲和處理。在标準C++中，字元串類string由C++ STL實作，提供豐富的字元串處理功能。string是一個基于字元的序列容器，具有vector向量一樣的内部線性結構，字元逐一寫入容器，最後以null字元結束。STL的string就是用字元數組實作的。

7 bit_vector位向量容器

bit_vector位向量容器是一個bit位元素的序列容器，具有vector容器一樣的成員函數，常用于硬體端口的控制。差別于vector< bool>的一個重要特性是bit_vector更節省記憶體空間，一個元素隻占用一個bit，而不是一個位元組。bit_vector用vector作字尾名，實際上與vector并沒有任何關聯。其内部是用位數組實作的。需要指出的是，bit位的随機讀寫，利用C++的bit位操作運算，如位與、位或和異或等。相對比vector麻煩。

8 set、multiset、map、multimap

這四位是用紅黑樹實作的，紅黑樹保證了對于元素的插入，查找，删除都是O(logn)的時間複雜度。使用時，前兩者引入頭檔案#include< set>，後兩者引入頭檔案#include< map>。

9 hash_set、hash_map

這兩位是用哈希表實作的，進而實作了更快的檢索。這兩位目前還不是C++ STL的标準容器。

算法（Algorithm）

STL的算法和容器是兩個最關鍵的元件，其他元件都是圍繞它們進行開發或使用的附帶産物。C++ STL的算法都是以模闆函數的方式提供出來的，可對具有泛型資料結構的容器進行資料處理。

如同容器一樣，将常用的排序、交換、查找和搜尋等算法處理，以泛化算法實作到C++ STL庫中，避免不必要的重複設計。C++ STL的算法函數有幾十種之多，分為不修改容器資料的周遊、查找、搜尋、計數、比對等非變易算法，複制、替換、交換、反向排列等變易算法，排序算法和數值計算的算法等。

疊代器（Iterator）

傳統上讀寫資料結構中的資料，一般是通過移動讀寫指針來進行的。在STL中，對容器的資料讀寫，通過疊代器來進行，每個容器都有自己對應的疊代器。疊代器是指針的一個泛化，在容器和算法之間充當橋梁的作用，是STL泛型庫最核心的一個組成部分。

記憶體配置設定器（Allocator）

STL的記憶體配置設定器是一些用于記憶體管理的模闆類，可支援搞層次和高性能的記憶體管理。因為記憶體管理往往是項目中非常重要的一個功能部分，是以STL把這部分提取出來，友善各種容器對元素資料進行記憶體管理，為容器很提供了進階形式的調用。

概念（Concept）和模型（Model）

STL通過模闆來傳遞類型參數，導緻算法函數無法使用C++本身的類型檢查機制，在代碼的開發階段不容易發現錯誤。一個較為有效的方法是，為泛型庫算法函數的所有模闆類型，從算法的實作步驟中歸納出相應的一個概念，用概念來指出用于具體實作的類型必須滿足的運算條件，二滿足某個概念所定義條件的類型，則稱為該概念的一個模型。

STL的版本

• HP STL：C++ STL第一個實作版本
• SGI STL：最好的源代碼閱讀版本
• STLport：支援hash_set，hash_map
• P.J.Plauger STL：被微軟所采用