STL中各個容器的實作基本原理以及互相依賴

STL中一共擁有六大元件：

1.算法 2.疊代器 3.容器. 4.仿函數 5.擴充卡(配接器)6.空間配置器

通過閱讀侯捷版本的《STL源碼剖析》可以知道，STL的實作也是由基本的資料結構來完成的

容器大概可以分為關聯型容器和序列型容器，

序列型容器有vector,list,deque,queue,stack,slist,heap,priority_queue

vector由數組實作，當現有數組容量不足時，申請新的記憶體，每次新增一倍目前容量的記憶體。

deque翻譯為雙端隊列，但它由一個中央控制器(map——此map非彼map)負責實作，deque的資料儲存在零零散散的多個固定長度的數組中，而map中儲存着一個指針，指針分别指向這些數組，deque先從map的中間位置(因為是雙端隊列，故各個指針是由中間向兩端依次排開)擷取指針，然後移動到具體的數組中存放資料。當數組不夠用時，申請新的數組并在map中記載指針，當map也不夠時，申請新的map，并且将原有的Map拷貝至新申請的map中來。是以map的複雜度大于vector。

stack、queue基于deque;

heap:完全二叉樹，使用大頂堆實作，然後進行排序，以vector的形式存放。

priority_queue：基于heap

list：雙向環形連結清單

slist::單連結清單

關聯式容器：

set,map,multiset,multimap-基于紅黑樹(RB-tree)，一種加上了額外平衡條件的二叉搜尋樹。

hash table-散清單。将待存資料的key經過映射函數變成一個數組(一般是vector)的索引，例如：資料的key%數組的大小＝數組的索引(一般文本通過算法也可以轉換為數字)，然後将資料當作此索引的數組元素。有些資料的key經過算法的轉換可能是同一個數組的索引值(碰撞問題，可以用線性探測，二次探測來解決)，STL是用開鍊的方法來解決的，每一個數組的元素維護一個list，他把相同索引值的資料存入一個list，這樣當list比較短時執行删除，插入，搜尋等算法比較快。

hash_map,hash_set,hash_multiset,hash_multimap-基于hash table。