《STL源码剖析》学习--六大组件
stl 提供了六大組件，分別為：容器、算法、迭代器、仿函數、適配器和配置器。
容器通過配置器取得數據存儲空間，算法通過迭代器存取容器的內容，仿函數可以協助算法完成不同的策略，配接器可以修飾或者嵌套仿函數。
下面分別簡單介紹：
1.容器（container) --? 各種數據結構
根據數據排列方式分為序列式和關聯式：
1.1序列式容器
（1）vector：與C++提供的靜態空間Array相比，vector是動態空間。連續空間，支持隨機存取，迭代器是普通指針。動態增加大小，不是在原空間后面續接新空間，而是以原來兩倍的大小另外開辟空間，然后將原來內容拷貝過來，再在之后添加新元素，釋放空間，一個“配置新空間，數據移動，釋放舊空間”的過程，因此插入元素不一定是常數時間。當配置新空間后，原來迭代器失效。vector不適用于插入刪除頻繁或者數據量很大的運算，會不停的開辟新空間，釋放空間。
單項開口，只能一端插入刪除元素。
（2）list：雙向鏈表，不支持隨機存取，非連續空間，對于任何位置插入或者移除元素都是常數時間。當插入或者刪除元素時，除此元素外迭代器不失效。
雙向開口，前后端都可以插入刪除元素。
提供transfer遷移操作，可以將連續范圍的元素遷移到某個特定位置之前，這是節點之間的移動；
提供splice接合操作，將某連續范圍的元素從一個list移動到另一個list的某個定點；
還有merge、reverse和sort操作。
（3）deque ：連續線性空間，隨機存取，雙向開口，雙端插入刪除，允許常數時間內對頭端進行元素的插入刪除。動態地以分段連續空間組合而成，因而沒有預留空間，隨時可以增加一段新空間并連接起來。deque的隨機存取的代價很大：具有map作為主控，map是一小塊連續空間，其中每個元素指向另一端較大的連續空間（緩沖區）；具有復雜的迭代器架構，維護兩個迭代器，start和finish，分別指向緩沖區的第一個元素和最后緩沖區的最后一個元素。當插入刪除元素時還包括map的分配更新，緩沖區的分配，迭代器的更新。
（4）stack ：一種配接器，底層是deque，通過改變接口，來實現“后進先出”，不允許遍歷，沒有迭代器。
（5）queue ：跟stack一樣是一種配接器，底層是deque，先進先出，不允許遍歷，沒有迭代器。
（6）heap：不屬于stl，有大堆和小堆之分，根據完全二叉樹堆排序算法來保持一個大堆或者小堆，從而可以每次取得優先權最高的的元素。heap所有元素都必須遵循特別的排序規則，不提供遍歷功能，沒有迭代器。
（7）priority_queue ：也是一種配接器，底層是vector，再加上heap排序規則，修改接口，實現自動排序，權值高的在前，只能取走頂端元素，沒有迭代器。
（8）slist：和list類似，只是是單向鏈表，只有forward iterator，處于效率的考慮，針對此提供了insert_after()和erase_after()。只提供pop_front()，元素次序和插入次序相反。
1.2 關聯式容器：
（1）RB-tree：即紅黑樹，stl不公開，紅黑樹是一種平衡二叉樹，置于紅黑樹的計算過程不做介紹，可參考《算法導論》13章紅黑樹。這種結構對于數據搜索效率很高，時間復雜度O(lgN)。
（2）set ：根據元素鍵值（也是實值）自動排序，不允許鍵值重復，底層是紅黑樹。
（3）map ：根據元素鍵值（第一元素）自動排序，不允許鍵值重復，底層是紅黑樹。
（4）multiset： 與set相同，只是允許鍵值重復。
（5）hashtable： 使用映射的方式將元素映射為大小可接受的索引。解決碰撞簡單的有線性探測，但是容易造成主集團；引出二次探測，可能引發次集團；還有一種方法開鏈，在每個表格元素中維護一個list，sgi stl中采用這種方法。
（6）hash_set：類似于set ，底層機制為hashtable，因為hashtable沒有排序，hash_set 沒有自動排序。
（7）hash_map：類似于map，只是底層機制為hashtable，同樣沒有自動排序。
（8）hash_multiset：類似于multiset，允許鍵值重復，沒有排序。
（9）hash_multimap：類似于multimap，底層機制為hashtable，允許鍵值重復，沒有排序。
2.算法（alogrithm)-- 各種算法
這里不做具體介紹，都是高效的算法，需要自己研究。
3.迭代器（iterator)-- 容器和算法之間的膠合劑，所有容器都有自己專屬的迭代器。
（1）注意迭代器實現中traits編程手法的實現。詳細可見traits
（2）迭代器有五種型別：Input、Output、Forward、Bidirectional和Random Iterator。
4.仿函數（functor)-- 類似函數的東西，作為算法的一種策略。
具體見可能令你困惑的C++語法中最后的仿函數。
5.配接器 （adapter) -- 用來修飾容器、仿函數或者迭代器接口的東西，使原本不能在一起工作的能工作在一起。
在《設計模式》一書中有此設計模式，定義為：將一個class的接口轉換為另一個class的接口，使原本因接口不兼容而不能合作的classes，可以一起運行。
stl中的配接器有：container、iterator和functor。containeradapters 有stack和queue，底層都是deque；iterator adapters有insert 、reverse 和stream；function adapters有對返回值進行否定的not1和not2、對參數進行綁定的bind1st和bind2nd、用于函數合成的compose1和compose2、用于函數指針ptr_fun、用于成員函數指針mem_fun和mem_fun_ref。
6.配置器 (allocator) -- 負責空間的配置和管理
（1）容器缺省的配置器為alloc，而非allocator。
（2）stl 將內存空間的配置/釋放和對象內容的構造/析構分開，由不同操作負責。內存配置操作由alloc:;alllocate()負責，內存釋放由alloc::deallocate()負責；對象構造由::construct()負責，對象析構由::destroy()負責。
destroy()有兩個版本，第一個版本直接調用對象的析構函數；第二個版本，如果對象的析構是無關痛癢的（其__type_traits<T>是true），則什么也不做，否則，調用第一個版本。
（3）內存空間采用雙層級配置器。第一級使用malloc()和free()，第二級則視不同的情況采取不同的策略，當配置區域塊超過128bytes時，調用第一級配置器；當配置區域小于128byte時，采用memory pool整理方式。因為在小額區太多時，配置時負擔也重，所以在小區域時用的策略也多。
（4）二級配置器，主動將小額區塊的內存需求上調至8的倍數，并維護16個freelists，各自管理大小分別為8、16、24、32…128bytes的小額區塊。
?
總結
以上是生活随笔為你收集整理的《STL源码剖析》学习--六大组件的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《STL源码剖析》学习--traits
- 下一篇： 《STL源码剖析》--知识点