07.27 C++中vector list dequeue set map

在c++中，如果要存儲的數據大小在編譯期間就能確定，則使用數組即可，否則就要使用c++的容器類。容器類分為順序存儲結構（vector list deque）和關聯存儲結構（set map）

<vector>

連續的存儲結構，連續的特性導致隨機訪問效率高（例如用[]下表訪問元素），但插入和刪除效率低（因為插入一個元素就要以塊的形式挪動內存），當vector容量滿了再插入元素時，系統會重新尋找一塊比現在大的內存（不同編譯器大小不一樣，VS2005是1.5倍）將當前數組放入，這樣做很耗時，所以最好提前定義好vector的容量不要超。

可允許重複對象

可插入null元素

有序容器

<list>

非連續雙鏈表存儲結構，這種特性導致隨機訪問效率低（不支持[]），但插入刪除操作效率高。佔用內存大。

可允許重複對象

可插入null元素

有序容器，插入順序就是輸出順序

<deque>

deque是vector和list的折中，即支持隨機存取，插入刪除操作的效率也介於兩者之間，但是佔用內存比前二者都多

可允許重複對象

可插入null元素

有序容器，插入順序就是輸出順序

vector or deque or list?

經常隨機訪問選vector，經過插入刪除選list，都需要選deque，deque性能處於折中

capacity reverse size resize?

capacity是當前vector最大能容納的元素數，size是當前vector存入的元素數，reverse(n)改變的是capacity值，resize改變的是size值，如果resize沒有指定賦什麼值給vector則按vector元素類型默認的構造函數塞數據進去，resize後vector的size就改變了

不允許重複對象

無序容器

只能插入一個null元素

不可重複鍵值對

set和map底層都是通過紅黑樹實現（具有較高的查找性能）