順序容器vector、list、deque的差別

說明：這篇文章主要通過查閱網上資料整理而成，并非原創。

順序容器

三種容器均支援resieze()操作，重新劃定容器大小，且此函數有重載。

vector

vector和built-in數組類似，是一個在堆上建立的一維數組，它擁有一段連續的記憶體空間，并且起始位址不變，是以 它能非常好的支援随即存取，即[]操作符。vector因為存儲在堆上，是以支援erase( ), resieze()（重新劃分容器容量）等操作； vector不用擔心越界當空間不夠用的時候，系統會自動按照一定的比例（對capacity( )大小）進行擴充。在vector序列末尾添加(push_back( ))或者删除(pop_back( ))對象效率高，在中間進行插入或删除效率很低，主要是要進行元素的移動和記憶體的拷貝，原因就在于當記憶體不夠用的時候要執行重新配置設定記憶體，拷貝對象到新存儲區，銷毀old對象，釋放記憶體等操 作，如果對象很多的話，這種操作代價是相當高的。為了減少這種代價，使用vector最理想的情況就是事先知道所要裝入的對象數目，用成員函式 reserve( )預定下來；vector最大的優點莫過于是檢索（用operator[ ]）速度在這三個容器中是最快的，

list

list的本質是一個雙向連結清單(根據sgi stl源代碼)，記憶體空間不連續，通過指針進行操作。說道連結清單，它的高效率首先表現是插入，删除元素，進行排序等等需要移動大量元素的操作。顯然連結清單沒有檢索操作operator[ ], 也就是說不能對連結清單進行随機通路，而隻能從頭至尾地周遊，這是它的一個缺陷。list有不同于前兩者的某些成員方法，如合并list的方法splice( ), 排序sort( ),交換list 的方法swap( )等等。

deque

deque是一個double-ended queue是由多個連續記憶體塊構成，deque是list和vector的相容，分為多個塊，每一個塊大小是512位元組，塊通過map塊管理，map塊裡儲存每個塊得首位址。是以該容器也有索引操作operator[ ]，效率沒vector高。另外，deque比vector多了push_front( ) & pop_front( )操作。在兩端進行此操作時與list的效率 差不多

下面是選擇順序容器類型的一些準則

1.如果我們需要随機通路一個容器則vector要比list好得多 。

2.如果我們已知要存儲元素的個數則vector 又是一個比list好的選擇。

3.如果我們需要的不隻是在容器兩端插入和删除元素則list顯然要比vector好

4.除非我們需要在容器首部插入和删除元素否則vector要比deque好。

5.如果隻在容易的首部和尾部插入資料元素，則選擇deque.

6.如果隻需要在讀取輸入時在容器的中間位置插入元素，然後需要随機通路元素，則可考慮輸入時将元素讀入到一個List容器，接着對此容器重新排序，使其适合順序通路，然後将排序後的list容器複制到一個vector容器中