1. vector與deque

vector與動(dòng)態(tài)數(shù)組相同，能夠在插入或刪除元素時(shí)自動(dòng)調(diào)整自身大小，其存儲(chǔ)由容器自動(dòng)處理，vector通常占用多于靜態(tài)數(shù)組的空間，因?yàn)橐峙涓嗟膬?nèi)存以管理將來的增長(zhǎng)，在每次插入元素的時(shí)，僅當(dāng)額外內(nèi)存耗盡時(shí)觸發(fā)重新分配。

如上圖所示，vector元素放置在連續(xù)存儲(chǔ)中，以便可以使用迭代器訪問和遍歷他們。在vector中，末尾插入需要不同的時(shí)間，因?yàn)橛袝r(shí)候需要擴(kuò)展存儲(chǔ)空間。對(duì)于刪除最后一個(gè)元素，因?yàn)椴簧婕按鎯?chǔ)空間大小的調(diào)整，則執(zhí)行時(shí)間是恒定的。對(duì)于開頭或者中間插入和擦除在時(shí)間上是線性的，因?yàn)榭赡芤婕暗皆氐囊苿?dòng)。

deque是具有兩端擴(kuò)縮功能的序列容器。其存儲(chǔ)方式與vector相反，deque的元素不是相接存儲(chǔ)的，是由一段一段等長(zhǎng)的連續(xù)空間構(gòu)成的，各段之間并不一定是連續(xù)的。它的典型實(shí)現(xiàn)如下圖所示，通過單獨(dú)分配固定尺寸的序列（對(duì)應(yīng)圖中的數(shù)據(jù)區(qū)），外加額外的登記（對(duì)應(yīng)圖中map映射區(qū)），map數(shù)組中存儲(chǔ)的是每段連續(xù)空間的地址，通過映射區(qū)來管理這些一段一段等長(zhǎng)的連續(xù)空間，進(jìn)而實(shí)現(xiàn)“整體連續(xù)”的效果。

當(dāng)deque容器需要在頭部或者尾部增加空間的時(shí)候，它會(huì)申請(qǐng)一段新的連續(xù)空間，同時(shí)在map數(shù)組的開頭或者結(jié)尾添加指向該空間的指針，由此將deque元素串接起來。在遇到空間不足的時(shí)候由于deque可以申請(qǐng)新的連續(xù)空間，原數(shù)據(jù)空間可以保持不變，更新map即可，所以deque在涉及到空間擴(kuò)展的時(shí)候，效率遠(yuǎn)高于vector。

2. 性能比較

2.1 隨機(jī)訪問

由于vector是連續(xù)存儲(chǔ)的，deque是分段連續(xù)存儲(chǔ)，其隨機(jī)訪問需對(duì)map數(shù)組進(jìn)行二次指針解引用（可以理解為：deque隨機(jī)訪問需要先去找到待訪問元素在哪段連續(xù)存儲(chǔ)空間，然后再對(duì)該空間進(jìn)行下標(biāo)訪問），而vector只有下標(biāo)訪問一次即可。因此在隨機(jī)訪問性能上，vector略高于deque，但兩者復(fù)雜度均為常數(shù)$O(1)$。

2.2 末尾插入/刪除

前面我們說過，vector的存儲(chǔ)是自動(dòng)管理的，按需擴(kuò)張收縮，vector通常占用多于靜態(tài)數(shù)組的空間，因?yàn)橐峙涓嗟膬?nèi)存以管理將來的增長(zhǎng)，通常情況下vector在尾部插入元素的復(fù)雜度為$O(1)$，但當(dāng)額外內(nèi)存耗盡的時(shí)候，需要重新分配，此時(shí)重新分配，是需要單獨(dú)再申請(qǐng)一份更大空間，把vector原有的元素重新放到新申請(qǐng)的空間上，再完成尾部插入，此時(shí)涉及到了新空間的申請(qǐng)、所有元素的移動(dòng)和舊空間的釋放，這種情況下的插入在性能上是災(zāi)難級(jí)別的，因此，總的來說對(duì)于vector尾部插入的時(shí)間復(fù)雜度為均攤常數(shù)$O(1)$。

對(duì)于deque由于存儲(chǔ)空間是分段連續(xù)的，當(dāng)空間不夠的時(shí)候重新申請(qǐng)新的一段空間即可，不會(huì)涉及到舊元素的移動(dòng)，其復(fù)雜度度為常數(shù)$O(1)$。對(duì)于尾部刪除，因?yàn)椴簧婕暗椒峙淇臻g申請(qǐng)，因此兩者的復(fù)雜度均在$O(1)$。

注：vector在尾部插入元素的時(shí)，新的size()如果大于capacity()，那么所有的迭代器和引用（包括end()迭代器）都會(huì)失效，否則只有end()迭代器會(huì)失效。而deque除了迭代器會(huì)失效，而不會(huì)使指向其余元素的指針或引用失效。

2.3 隨機(jī)插入/刪除

vector在進(jìn)行隨機(jī)插入的時(shí)候，涉及到插入位置到序列尾部這段元素的移動(dòng)（可以理解為這段元素需要整體往后移動(dòng)一位，給新插入元素把位置留出來），隨機(jī)刪除元素同理，因此其隨機(jī)插入/刪除的時(shí)間復(fù)雜度為插入位置與到vector尾部距離成線性$O(n)$。deque的擴(kuò)展方式是雙向的，因此其可以**根據(jù)插入位置距離頭部或者尾部較近的距離成線性$O(n)$，**因此，其性能略勝vector一丟丟。

注：對(duì)于vector隨機(jī)插入，如果新size()大于舊的capacity()就會(huì)導(dǎo)致重分配，所有的迭代器和引用都會(huì)失效，否則，只有在插入點(diǎn)前的迭代器和引用會(huì)保持有效。對(duì)于deque而言，所有迭代器和引用也會(huì)失效，除非插入位置為容器尾部或者頭部，引用不會(huì)失效。

3. 總結(jié)

vector和deque的對(duì)比如下表所示：

vector重分配在性能上是有開銷的，如果在使用之前元素的數(shù)量已知，那么可以使用rederve()函數(shù)來消除重分配。

deque的存儲(chǔ)按需自動(dòng)擴(kuò)展及收縮，擴(kuò)展deque比擴(kuò)張vector更優(yōu)，因?yàn)樗簧婕暗綇?fù)制既存元素到新內(nèi)存位置。但另外一方面，deque典型地?fù)碛休^大的最小內(nèi)存開銷，所以當(dāng)即使保有一個(gè)元素的時(shí)候，deque也需要為它分配它的整個(gè)內(nèi)部數(shù)組。

文章首發(fā)公眾號(hào)：iDoitnow如果喜歡話，可以關(guān)注一下文章來源地址http://www.zghlxwxcb.cn/news/detail-676028.html

到了這里，關(guān)于vector VS deque的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！