GitHub參考
STL"源碼"剖析-重點(diǎn)知識(shí)總結(jié)
C++STL自己總結(jié)

序列式容器

所謂序列式容器，其中的元素都可序，但未必有序，C++本身內(nèi)建了一個(gè)序列式容器array，STL另外提供了vector、list、deque、stack、queue、priority-queue等序列式容器。其中stack和queue由于只是deque改頭換面而來(lái)，技術(shù)上被歸為一種配接器 (adapter)。

vector

vector 采用的數(shù)據(jù)結(jié)構(gòu)非常簡(jiǎn)單：線性連續(xù)空間。它以兩個(gè)迭代器 start 和 finish 分別指向配置得來(lái)的連續(xù)空間中目前已被使用的范圍，并以迭代器 end_of_storage 指向整塊連續(xù)空間(含備用空間)的尾端。

list

相對(duì)于vector的連續(xù)線性空間，list就顯得復(fù)雜許多，它的好處就是插入或刪除一個(gè)元素，就配置或刪除一個(gè)元素空間。
對(duì)于任何位置的元素的插入或刪除，list永遠(yuǎn)是常數(shù)時(shí)間。
list本身和節(jié)點(diǎn)是不同的結(jié)構(gòu)，需要分開(kāi)設(shè)計(jì)。以下是STL list的節(jié)點(diǎn)node結(jié)構(gòu)：

template <class T>
class __list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

deque

• deque 和 vector 的最大差異，一在于 deque 允許常數(shù)時(shí)間內(nèi)對(duì)起頭端進(jìn)行插入或移除操作，二在于 deque 沒(méi)有所謂容量 (capacity) 概念，因?yàn)樗且苑侄芜B續(xù)空間組合而成，隨時(shí)可以增加一段新的空間連接起來(lái)。
• deque由一段一段連續(xù)空間組成，一旦有必要在deque的前端或尾端增加新空間，便配置一段連續(xù)空間，串接在整個(gè)deque的前端或尾端。deque的最大任務(wù)，便是在這些分段的連續(xù)空間上，維護(hù)其整體連續(xù)的假象，并提供隨機(jī)存取的接口，避開(kāi)了“重新配置、復(fù)制、釋放”的輪回，代價(jià)是復(fù)雜的迭代器結(jié)構(gòu)。
  
  
  deque迭代器
  　　迭代器首先必須指出分段連續(xù)空間在哪里，其次它必須能夠判斷自己是否已經(jīng)處在緩沖區(qū)的邊緣，如果是，一旦前進(jìn)或后退就必須跳躍下一個(gè)緩沖區(qū)，為了能夠正常跳躍，deque必須隨時(shí)掌握管控中心。

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator { // 未繼承 std::iterator
    // 保持迭代器的連接
    T* cur; // 此迭代器所指之緩沖區(qū)的現(xiàn)行（ current）元素
    T* first; // 此迭代器所指之緩沖區(qū)的的頭
    T* last; // 此迭代器所指之緩沖區(qū)的的尾（含備用空間）
    map_pointer node; // 指向管控中心
    ...
};

stack

• stack是一種先進(jìn)后出(First In Last Out，F(xiàn)ILO)的數(shù)據(jù)結(jié)構(gòu)，它只有一個(gè)出口。
• stack允許增加元素、移除元素、取得最頂端元素。但除了最頂端外，沒(méi)有任何其他方法可以存取，stack的其他元素，換言之，stack不允許有遍歷行為。
• stack默認(rèn)以deque為底層容器。
• 由于 stack 系以底部容器完成其所有工作，而具有這種 "修改某物接口，形成另一種風(fēng)貌" 之性質(zhì)者，稱(chēng)為 adapter(適配器)，因此，STL stack 往往不被歸類(lèi)為 container(容器)，而被歸類(lèi)為 container adapter
  

queue

• queue是一種先進(jìn)先出(First In First Out，F(xiàn)IFO)的數(shù)據(jù)結(jié)構(gòu)，它有兩個(gè)出口，允許增加元素、移除元素、從最底端加入元素、取得最頂端元素。但除了最底端可以加入、最頂端可以取出外，沒(méi)有任何其他方法可以存取queue的其他元素，換言之，queue不允許有遍歷行為。
• queue默認(rèn)以deque為底層容器。

heap

priority_queue

slist

關(guān)聯(lián)式容器

標(biāo)準(zhǔn)的 STL 關(guān)聯(lián)式容器分為 set (集合) 和 map (映射表) 兩大類(lèi)，以及這兩大類(lèi)的衍生體 multiset (多鍵集合) 和 multimap (多鍵映射表) 。這些容器的底層機(jī)制均以 RB-tree (紅黑樹(shù)) 完成。
此外，SGI STL 還提供了一個(gè)不在標(biāo)準(zhǔn)規(guī)格之列的關(guān)聯(lián)式容器：hash table (散列表)，以及以此 hash table 為底層機(jī)制而完成的 hash_set (散列集合)、hash_map (散列映射表)、hash_multiset (散列多鍵集合)、hash_multimap (散列多鍵映射表)

set

• set的所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)排序。
• set的元素不像map那樣可以同時(shí)擁有實(shí)值(value)和鍵值(key)，set元素的鍵值就是實(shí)值，實(shí)值就是鍵值，set不允許有兩個(gè)相同的元素。
• set元素不能改變，在set源碼中，set<T>::iterator被定義為底層TB-tree的const_iterator，杜絕寫(xiě)入操作，也就是說(shuō)，set iterator是一種constant iterators(相對(duì)于mutable iterators)
• 底層機(jī)制 紅黑樹(shù)

map

• map的所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)排序。
• map的所有元素都是pair，同時(shí)擁有實(shí)值(value)和鍵值(key)。pair的第一元素為鍵值，第二元素為實(shí)值。map不允許有兩個(gè)相同的鍵值。
• 如果通過(guò)map的迭代器改變?cè)氐逆I值，這樣是不行的，因?yàn)閙ap元素的鍵值關(guān)系到map元素的排列規(guī)則。任意改變map元素鍵值都會(huì)破壞map組織。如果修改元素的實(shí)值，這是可以的，因?yàn)閙ap元素的實(shí)值不影響map元素的排列規(guī)則。因此，map iterator既不是一種constant iterators，也不是一種mutable iterators。
• 底層機(jī)制 紅黑樹(shù)

multiset

• multiset 的特性以及用法和 set 完全相同，唯一的差別在于它允許鍵值重復(fù)，因此它的插入操作采用的是底層機(jī)制 RB-tree 的 insert_equal() 而非 insert_unique()。

multimap

• multimap 的特性以及用法和 map 完全相同，唯一的差別在于它允許鍵值重復(fù)，因此它的插入操作采用的是底層機(jī)制 RB-tree 的 insert_equal() 而非 insert_unique()。

hash table 散列表

二叉搜索樹(shù)具有對(duì)數(shù)平均時(shí)間表現(xiàn)，但這樣的表現(xiàn)構(gòu)造在一個(gè)假設(shè)上：輸入數(shù)據(jù)有足夠的隨機(jī)性。hashtable這種結(jié)構(gòu)在插入、刪除、查找具有“常數(shù)平均時(shí)間”，而且這種表現(xiàn)是以統(tǒng)計(jì)為基礎(chǔ)，不需依賴元素的隨機(jī)性。

hashtable中的buckets使用的是vector數(shù)據(jù)結(jié)構(gòu)，當(dāng)插入一個(gè)元素時(shí)，找到該插入哪個(gè)buckets的插槽，然后遍歷該插槽指向的鏈表，如果有相同的元素，就返回；否則的話就將該元素插入到該鏈表的頭部。(當(dāng)然，如果是multi版本的話，是可以插入重復(fù)元素的，此時(shí)插入過(guò)程為：當(dāng)插入一個(gè)元素時(shí)，找到該插入哪個(gè)buckets的插槽，然后遍歷該插槽指向的鏈表，如果有相同的元素，就將新節(jié)點(diǎn)插入到該相同元素的后面；如果沒(méi)有相同的元素，產(chǎn)生新節(jié)點(diǎn)，插入到鏈表頭部)

hash_set

• 以 hash table 為底層機(jī)制
• 運(yùn)用set，為的是快速搜尋元素。這一點(diǎn)，不論其底層是RB-tree或是hashtable，都可以完成任務(wù)，但是，RB-tree有自動(dòng)排序功能而hashtable沒(méi)有，即set的元素有自動(dòng)排序功能而hash_set沒(méi)有。

hash_map

• hash_map 以 hashtable 為底層結(jié)構(gòu)，由于 hash_map 所提供的操作接口，hashtable 都提供了，所以幾乎所有的 hash_map 操作行為都是轉(zhuǎn)調(diào)用 hashtable 的操作行為結(jié)果。RB-tree 有自動(dòng)排序功能而 hashtable 沒(méi)有，反映出來(lái)的結(jié)果就是，map的元素有自動(dòng)排序功能而 hash_map 沒(méi)有。

hash_multiset

• hash_multiset 的特性與 multiset 完全相同，唯一的差別在于它的底層機(jī)制是 hashtable，因此，hash_multiset 的元素是不會(huì)自動(dòng)排序的。

hash_multimap

• hash_multimap 的特性與 multimap 完全相同，唯一的差別在于它的底層機(jī)制是hashtable，因此，hash_multimap 的元素是不會(huì)自動(dòng)排序的。