C++ STL底層實作

順序容器

vector(順序容器)

deque(雙端隊列)

list(連結清單)
           

關聯容器

set(集合)

multiset

map(key, value)

multimap
           

容器	特點	記憶體結構	對應頭檔案
向量vector	1. 查詢時間複雜度(O1) 2. 尾部插入和删除時間複雜度(O1) 3. 頭部插入和删除的代價很高	數組
雙端隊列 deque	1. 在頭部和尾部插入和删除操作的時間複雜度O(1)	雙向連結清單
	對任意位置對插入和删除操作的時間複雜度O(1)	雙端連結清單
集合set	由節點組成的紅黑樹，每個節點都包含着一個元素，節點之間以某種作用于元素對的位于排列， 沒有兩個不同的元素能夠擁有相同的次序，具有快速查找對能力。但它以犧牲插入和删除操作的效率為代價	二叉樹
多重集合 multiset	支援重複元素，具有快速查找的能力.插入/删除操作的時間複雜度為O(log2N)
映射map	由健值對組成的集合，以某種作用于鍵對上的位次排列，具有快速查找的能力.根據key值快速查找，查找的時間複雜度為O(log2N)
多重映射multimap	一個鍵可以應對多個值，具有快速查找多能力		map