C++中l(wèi)ist、deque以及vector對(duì)比

C++的容器類包括兩大類：

1.順序存儲(chǔ)結(jié)構(gòu)，包括vector、list、deque等等；
2.關(guān)聯(lián)存儲(chǔ)結(jié)構(gòu)，包括set、map、multiset等等；

對(duì)比vector、list以及deque這三種順序存儲(chǔ)結(jié)構(gòu)

注：
順序存儲(chǔ)結(jié)構(gòu)表明，其中的每個(gè)元素之間是有先后順序的，這個(gè)順序只和插入/刪除等操作有關(guān)，而與元素的值無關(guān)。

一、vector

vector本身是向量的意思，也稱vector是向量數(shù)組。

vector本身是為了解決數(shù)組不能動(dòng)態(tài)增長，而自己實(shí)現(xiàn)的類還需要自己小心翼翼地處理指針和malloc等問題，所以衍生出vector。

vector中的每個(gè)元素在內(nèi)存上是連續(xù)的，就像數(shù)組一樣；

vector支持高效的隨機(jī)訪問（使用[ ]運(yùn)算符或者at方法）；

什么是隨機(jī)訪問？

所謂隨機(jī)訪問，是可以直接計(jì)算出對(duì)應(yīng)元素的地址，假設(shè)起始地址是base，每個(gè)元素占空間大小是element_size，那么當(dāng)我存取第n個(gè)元素時(shí)，我可以直接計(jì)算出其對(duì)應(yīng)的地址：第六個(gè)元素的地址=base+element_size*(n-1),不必要類似鏈表一樣遍歷，效率明顯很高。

vector支持高效的在末尾插入和刪除。

注意：
此處特別強(qiáng)調(diào)是在末尾，想一想，一個(gè)數(shù)組，在哪里插入和刪除最為容易？
顯然是末尾。
如果在數(shù)組中間插入或刪除，需要將之后的所有元素都向前/向后移動(dòng)，無疑增加了開銷。

可以將vector看成是一個(gè)數(shù)組，區(qū)別于普通的數(shù)組，vector擁有自動(dòng)擴(kuò)展內(nèi)存空間的能力（不必程序員自己管理內(nèi)存空間）。

vector有一個(gè)capacity方法，其返回值是當(dāng)前vector已經(jīng)分配了多少個(gè)空間用來存儲(chǔ)element。

這些空間不一定全被“裝滿”了，可能只裝了一部分。

在裝滿（vector.size()==vector.capacity()）的情況下繼續(xù)裝（vector.push_back(xxx)）時(shí)，vector自動(dòng)擴(kuò)大內(nèi)存：
步驟如下：
首先申請(qǐng)一塊更大的內(nèi)存空間；
其次將vector現(xiàn)有的元素都搬過去；
最后將需要插入的元素插入到末尾。

注意：
在上述的步驟中還要將原來使用的內(nèi)存空間釋放。
程序員無需關(guān)心什么時(shí)候釋放等等細(xì)節(jié)，vector會(huì)自己做的。
程序員只要一個(gè)push_back即可。

關(guān)于vector的成員函數(shù)說兩句：

1.szie以及capacity返回的都是元素的個(gè)數(shù)，是以元素來計(jì)數(shù)的，而不是字節(jié)。

2.vector支持在末尾進(jìn)行pop和push，但不支持在首進(jìn)行pop和push。

當(dāng)然，如果一定要在前面插入，vector也是有對(duì)應(yīng)的insert和erase的，只是由于必然引起數(shù)據(jù)塊的移動(dòng)，所以性能很低。

二、list

list是一個(gè)非連續(xù)的順序結(jié)構(gòu)，每個(gè)元素在內(nèi)存上都不是挨著的。

list是一個(gè)雙向鏈表，即每個(gè)節(jié)點(diǎn)都有兩個(gè)指針域：一個(gè)指向前驅(qū)節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn)。

list同普通的鏈表一樣，對(duì)待插入刪除這樣的操作可以有很高的效率；

同樣，對(duì)于隨機(jī)訪問的能力就不盡如人意，效率很差了。

list在存儲(chǔ)大的，復(fù)雜的數(shù)據(jù)時(shí)有很不錯(cuò)的表現(xiàn)。

list有幾個(gè)優(yōu)點(diǎn)：

首先list不使用連續(xù)的內(nèi)存；
其次在插入和刪除方面有很好的性能；
最后是可以在兩端進(jìn)行pop和push（vector只能在尾端進(jìn)行pop和push）。

list也有其自己的缺點(diǎn)：

因?yàn)槠涿總€(gè)節(jié)點(diǎn)有兩個(gè)指針域，導(dǎo)致占用空間較大；
list不支持[]操作符和at方法。

注：
不是list不能實(shí)現(xiàn)[ ]和at，而是設(shè)計(jì)者認(rèn)為list在這方面表現(xiàn)的很不好，隨機(jī)訪問也不應(yīng)該是list的用武之地，所以不這么實(shí)現(xiàn)，但不代表著不能實(shí)現(xiàn)。

對(duì)于list，清除所有的元素需要依次遍歷，效率很低（如果是vector，因?yàn)槭且徽麎K內(nèi)存，可以很方便地進(jìn)行操作）。

三、deque

deque=double-end-queue，意即雙端隊(duì)列。

可以將deque看成是list和vector的結(jié)合。（效率接近于vector），而且在插入和刪除方面也表現(xiàn)出很不錯(cuò)的性能（尤其是在首位進(jìn)行插入刪除，效率接近于list）。

deque還可以類似list那樣在兩端進(jìn)行pop和push。

猜測(cè)：

deque可能是下面的存儲(chǔ)結(jié)構(gòu)：

每幾個(gè)元素時(shí)連續(xù)的一個(gè)內(nèi)存塊，而每個(gè)內(nèi)存塊之間有指針鏈接起來。

當(dāng)隨機(jī)訪問時(shí)使用一個(gè)分段函數(shù)可以相對(duì)方便地計(jì)算出來地址（當(dāng)然沒有vector那樣方便啦，只是比起list來說好很多了）；

當(dāng)在首位進(jìn)行插入刪除時(shí)有接近于list的性能表現(xiàn)。

綜上三點(diǎn)，得出以下結(jié)論：

1.如果有大量的隨機(jī)訪問，而插入和刪除操作較少，應(yīng)該使用vector；

2.如果有大量的插入和刪除，而隨機(jī)訪問較少，應(yīng)該使用list；

3.如果既有很多的插入和刪除，又有很多的隨機(jī)訪問，那么deque是個(gè)不錯(cuò)的選擇。

另外一點(diǎn)，如果在不知道內(nèi)存具體需求的時(shí)候，一般使用deque要比vector性能好一些。

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】5. C++中 list、deque、vector对比的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。