C++>STL分類，list，deque與vector的比較

stl提供了三個最基本的容器：vector,list,deque。

vector和built-in數組類似，它擁有一段連續的記憶體空間，并且起始位址不變，是以它能非常好的支援随即存取，即[]操作符，但由于它的記憶體空間是連續的，是以在中間進行插入和删除會造成記憶體塊的拷貝，另外，當該數組後的記憶體空間不夠時，需要重新申請一塊足夠大的記憶體并進行記憶體的拷貝。這些都大大影響了vector的效率。

list就是資料結構中的雙向連結清單(根據sgi stl源代碼)，是以它的記憶體空間可以是不連續的，通過指針來進行資料的通路，這個特點使得它的随即存取變的非常沒有效率，是以它沒有提供[]操作符的重載。但由于連結清單的特點，它可以以很好的效率支援任意地方的删除和插入。

deque是一個double-ended queue，它的具體實作可以了解為list，但是它的結點裡存放的的是vector，但知道它具有以下兩個特點：

它支援[]操作符，也就是支援随即存取，并且和vector的效率相差無幾，它支援在兩端的操作：push_back,push_front,pop_back,pop_front等，并且在兩端操作上與list的效率也差不多。

是以在實際使用時，如何選擇這三個容器中哪一個，應根據你的需要而定，一般應遵循下面的原則：

1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector

2、如果你需要大量的插入和删除，而不關心随即存取，則應使用list

3、如果你需要随即存取，而且關心兩端資料的插入和删除，則應使用deque。

vector為存儲的對象配置設定一塊連續的位址空間，是以對vector中的元素随機通路效率很高。在vecotor中插入或者删除某個元素，需要将現有元素進行複制，移動。如果vector中存儲的對象很大，或者構造函數複雜，則在對現有元素進行拷貝時開銷較大，因為拷貝對象要調用拷貝構造函數。對于簡單的小對象，vector的效率優于list。vector在每次擴張容量的時候，将容量擴充2倍，這樣對于小對象來說，效率是很高的。

list中的對象是離散存儲的，随機通路某個元素需要周遊list。在list中插入元素，尤其是在首尾插入元素，效率很高，隻需要改變元素的指針。

綜上所述：

vector适用：對象數量變化少，簡單對象，随機通路元素頻繁

list适用：對象數量變化大，對象複雜，插入和删除

STL通用類型算法

這類算法與資料結構無關。

https://blog.csdn.net/u014183456/article/details/82835281