vector ,deque 和 list
順序性容器：
向量 vector ：
是一個線性順序結構。相當於數組，但其大小可以不預先指定，並且自動擴展。它可以像數組一樣被操作，由於它的特性我們完全可以將vector 看作動態數組。
在創建一個vector 後，它會自動在內存中分配一塊連續的內存空間進行數據存儲，初始的空間大小可以預先指定也可以由vector 默認指定，這個大小即capacity （）函數的返回值。當存儲的數據超過分配的空間時vector 會重新分配一塊內存塊，但這樣的分配是很耗時的，在重新分配空間時它會做這樣的動作：
首先，vector 會申請一塊更大的內存塊；
然後，將原來的數據拷貝到新的內存塊中；
其次，銷毀掉原內存塊中的對象（調用對象的析構函數）；
最後，將原來的內存空間釋放掉。
如果vector 保存的數據量很大時，這樣的操作一定會導致糟糕的性能（這也是vector 被設計成比較容易拷貝的值類型的原因）。所以說vector 不是在什麼情況下性能都好，只有在預先知道它大小的情況下vector 的性能才是最優的。
vector 的特點：
(1) 指定一塊如同數組一樣的連續存儲，但空間可以動態擴展。即它可以像數組一樣操作，並且可以進行動態操作。通常體現在push_back() pop_back() 。
(2) 隨機訪問方便，它像數組一樣被訪問，即支持[ ] 操作符和vector.at()
(3) 節省空間，因為它是連續存儲，在存儲數據的區域都是沒有被浪費的，但是要明確一點vector 大多情況下並不是滿存的，在未存儲的區域實際是浪費的。
(4) 在內部進行插入、刪除操作效率非常低，這樣的操作基本上是被禁止的。Vector 被設計成只能在後端進行追加和刪除操作，其原因是vector 內部的實現是按照順序表的原理。
(5) 只能在vector 的最後進行push 和pop ，不能在vector 的頭進行push 和pop 。
(6) 當動態添加的數據超過vector 默認分配的大小時要進行內存的重新分配、拷貝與釋放，這個操作非常消耗性能。 所以要vector 達到最優的性能，最好在創建vector 時就指定其空間大小。
vector創建二維數組與訪問:
vector<vector<double>> vec2D(M,vector<double>(6));
訪問：vec2D[i][j]即可！
http://roucheng.cnblogs.com/
雙向鏈表list
是一個線性鏈表結構，它的數據由若干個節點構成，每一個節點都包括一個信息塊（即實際存儲的數據）、一個前驅指針和一個後驅指針。它無需分配指定的內存大小且可以任意伸縮，這是因為它存儲在非連續的內存空間中，並且由指針將有序的元素鏈接起來。
由於其結構的原因，list 隨機檢索的性能非常的不好，因為它不像vector 那樣直接找到元素的地址，而是要從頭一個一個的順序查找，這樣目標元素越靠後，它的檢索時間就越長。檢索時間與目標元素的位置成正比。
雖然隨機檢索的速度不夠快，但是它可以迅速地在任何節點進行插入和刪除操作。因為list 的每個節點保存著它在鏈表中的位置，插入或刪除一個元素僅對最多三個元素有所影響，不像vector 會對操作點之後的所有元素的存儲地址都有所影響，這一點是vector 不可比擬的。
list 的特點：
(1) 不使用連續的內存空間這樣可以隨意地進行動態操作；
(2) 可以在內部任何位置快速地插入或刪除，當然也可以在兩端進行push 和pop 。
(3) 不能進行內部的隨機訪問，即不支持[ ] 操作符和vector.at() ；
(4) 相對於verctor 占用更多的內存。
雙端隊列deque
是一種優化了的、對序列兩端元素進行添加和刪除操作的基本序列容器。它允許較為快速地隨機訪問，但它不像vector 把所有的對象保存在一塊連續的內存塊，而是采用多個連續的存儲塊，並且在一個映射結構中保存對這些塊及其順序的跟蹤。向deque 兩端添加或刪除元素的開銷很小。它不需要重新分配空間，所以向末端增加元素比vector 更有效。
實際上，deque 是對vector 和list 優缺點的結合，它是處於兩者之間的一種容器。
deque 的特點：
(1) 隨機訪問方便，即支持[ ] 操作符和vector.at() ，但性能沒有vector 好；
(2) 可以在內部進行插入和刪除操作，但性能不及list ；
(3) 可以在兩端進行push 、pop ；
三者的比較
下圖描述了vector 、list 、deque 在內存結構上的特點：
vector 是一段連續的內存塊，而deque 是多個連續的內存塊， list 是所有數據元素分開保存，可以是任何兩個元素沒有連續。
vector 的查詢性能最好，並且在末端增加數據也很好，除非它重新申請內存段；適合高效地隨機存儲。
list 是一個鏈表，任何一個元素都可以是不連續的，但它都有兩個指向上一元素和下一元素的指針。所以它對插入、刪除元素性能是最好的，而查詢性能非常差；適合 大量地插入和刪除操作而不關心隨機存取的需求。
deque 是介於兩者之間，它兼顧了數組和鏈表的優點，它是分塊的鏈表和多個數組的聯合。所以它有被list 好的查詢性能，有被vector 好的插入、刪除性能。 如果你需要隨即存取又關心兩端數據的插入和刪除，那麼deque 是最佳之選。
推薦：http://www.cnblogs.com/roucheng/p/jfcz.html
