1. 先說(shuō)清楚deque到底解決了什么問(wèn)題C STL里的容器族譜中vector、list、deque這三兄弟的分工一直很有意思。vector是“單塊連續(xù)內(nèi)存上的動(dòng)態(tài)數(shù)組”list是“徹底離散的鏈表”而deque則長(zhǎng)期被很多人用一個(gè)模糊的描述帶過(guò)——“雙端隊(duì)列頭尾插入刪除都快”。這個(gè)描述沒(méi)錯(cuò)但它只是表象。真正值得追的問(wèn)題是deque憑什么能讓兩端都快的它內(nèi)部到底長(zhǎng)什么樣為什么stack和queue這兩個(gè)適配器的默認(rèn)底層容器偏偏都是deque這篇分析我會(huì)直接從源碼視角拆解deque的實(shí)現(xiàn)結(jié)構(gòu)再順勢(shì)把queue和stack剝開(kāi)來(lái)看。你會(huì)看到stack其實(shí)是一個(gè)幾乎沒(méi)有自己存儲(chǔ)空間的空殼它把全部工作委托給了底層容器而queue則需要底層容器同時(shí)具備push_back、pop_front、front、back這幾個(gè)能力這直接解釋了為什么deque是最合適的默認(rèn)底子。如果你正在準(zhǔn)備相關(guān)內(nèi)容或者只是好奇“STL里到底藏著什么”這篇文章值得往下讀。理解了deque的分段連續(xù)存儲(chǔ)模型再回頭看vector和list你會(huì)對(duì)整個(gè)STL的內(nèi)存布局有更立體的感覺(jué)。1.1 分段連續(xù)存儲(chǔ)deque的折中之道deque的核心設(shè)計(jì)思路可以概括為“分段連續(xù)存儲(chǔ)”。它不是一整塊連續(xù)內(nèi)存而是由若干塊固定大小的獨(dú)立連續(xù)緩沖區(qū)拼接起來(lái)邏輯上對(duì)外表現(xiàn)為一個(gè)連續(xù)的序列。這個(gè)思想在STL源碼里體現(xiàn)得極其清晰deque對(duì)象內(nèi)部有一個(gè)被稱為map的指針數(shù)組map的每個(gè)元素指向一塊緩沖區(qū)而deque的迭代器則在這塊緩沖區(qū)構(gòu)成的“序列”之間跳躍移動(dòng)。用一句大白話解釋vector是一間打通的大倉(cāng)庫(kù)所有貨物碼在同一個(gè)平面list是一串獨(dú)立的小倉(cāng)庫(kù)貨物之間靠鏈條聯(lián)系deque則是一排規(guī)格相同的小倉(cāng)庫(kù)每間倉(cāng)庫(kù)內(nèi)部貨物緊密排列倉(cāng)庫(kù)與倉(cāng)庫(kù)之間通過(guò)一張“倉(cāng)庫(kù)索引表”串起來(lái)。正因?yàn)槊块g倉(cāng)庫(kù)都獨(dú)立想要在前面或后面加一間倉(cāng)庫(kù)就非常簡(jiǎn)單——只要新村一間倉(cāng)庫(kù)并登記到索引表里就行不用像vector那樣把整倉(cāng)庫(kù)貨物全部搬家。這個(gè)設(shè)計(jì)天然解決了一個(gè)核心矛盾vector的頭部插入需要搬動(dòng)所有元素list的隨機(jī)訪問(wèn)必須從頭遍歷而deque在“兩端操作”和“隨機(jī)訪問(wèn)”之間取了平衡。兩端操作是真正的O(1)隨機(jī)訪問(wèn)是帶一點(diǎn)額外開(kāi)銷的O(1)。代價(jià)則是中間插入時(shí)依然需要搬移元素并且因?yàn)橐幚砜缇彌_區(qū)搬遷邏輯復(fù)雜度遠(yuǎn)高于vector。1.2 為什么stack和queue都默認(rèn)用deque很多人第一次看到stack的默認(rèn)底層容器是deque時(shí)會(huì)覺(jué)得意外stack只是尾部進(jìn)、尾部出用vector豈不是更自然queue是尾進(jìn)頭出用list好像也行為什么標(biāo)準(zhǔn)庫(kù)偏偏挑deque因?yàn)閐eque恰好提供了queue和stack需要的那組接口而且性能特征最均衡。stack需要push_back、pop_back、backvector全都支持理論上stack完全可以以vector為底層queue需要push_back、pop_front、front、backvector沒(méi)有pop_frontlist雖然有pop_front但隨機(jī)訪問(wèn)和元素局部性都很差。deque是唯一一個(gè)“兩端都是O(1)、塊內(nèi)局部性不錯(cuò)、且接口齊全”的容器所以標(biāo)準(zhǔn)庫(kù)把它設(shè)為默認(rèn)底層。這不是隨意拍腦袋的決定而是對(duì)操作頻率和實(shí)現(xiàn)代價(jià)綜合權(quán)衡后的最優(yōu)解。后面分析適配器源碼時(shí)你會(huì)有更直觀的感受。對(duì)比維度dequevectorlist內(nèi)存布局分塊連續(xù)塊間經(jīng)map索引一整塊連續(xù)內(nèi)存每個(gè)節(jié)點(diǎn)分離靠指針串聯(lián)頭部插入/刪除O(1)O(n)搬全部元素O(1)尾部插入/刪除O(1)O(1)擴(kuò)容時(shí)O(n)O(1)中間插入/刪除O(n)最多搬一半元素O(n)搬后面全部元素O(n)查找O(1)修改隨機(jī)訪問(wèn)O(1)常數(shù)較大需跨塊判斷O(1)常數(shù)最小O(n)迭代器失效規(guī)則兩端插入引用不失效迭代器可能失效中間插入全失效擴(kuò)容后迭代器和引用全部失效只要不刪除該元素本身迭代器穩(wěn)定2. deque內(nèi)部的三個(gè)關(guān)鍵拼圖要讀懂deque的源碼只需要盯住三個(gè)東西map指針數(shù)組、緩沖區(qū)、迭代器。這三者之間的關(guān)系可以類比成“目錄、書(shū)頁(yè)和書(shū)簽”。map是目錄記錄每一塊緩沖區(qū)的起始地址緩沖區(qū)是實(shí)際存放元素的書(shū)頁(yè)迭代器則是當(dāng)前閱讀位置的書(shū)簽它不僅要指向某個(gè)元素還要記錄自己目前在哪一頁(yè)的哪個(gè)位置。2.1 中央控制器map一張索引表在典型的libstdc實(shí)現(xiàn)中deque_base內(nèi)部有一個(gè)指向“指針數(shù)組”的指針_M_map以及一個(gè)記錄map大小的_M_map_size。map數(shù)組的每個(gè)元素都是_Tp*指向一塊緩沖區(qū)。另外還有兩個(gè)迭代器成員_M_start和_M_finish一個(gè)標(biāo)記首元素位置一個(gè)標(biāo)記尾后位置。map不是一開(kāi)始就很大。它會(huì)設(shè)定一個(gè)初始規(guī)模并且故意在首尾兩側(cè)多留一些空位。為什么要預(yù)留因?yàn)閐eque將來(lái)可能會(huì)從兩端繼續(xù)擴(kuò)充如果map里已經(jīng)沒(méi)有空槽位指向新緩沖區(qū)它就需要重新分配一個(gè)更大的map然后把原來(lái)的指針數(shù)組整體搬到新map的中間位置。預(yù)留空位就是為了延遲這次搬遷讓前端插入和后端插入都能直接登記新緩沖區(qū)地址而不必頻繁觸發(fā)map重新分配。理解map的關(guān)鍵在于map本身不是元素存儲(chǔ)區(qū)它只是“指針的集合”。deque擴(kuò)容時(shí)可能發(fā)生兩種層級(jí)的變化第一是map指針數(shù)組膨脹這時(shí)只需要復(fù)制指針元素?cái)?shù)據(jù)紋絲不動(dòng)第二是緩沖區(qū)不夠用deque會(huì)為新的端分配一塊新緩沖區(qū)。這兩種開(kāi)銷都比vector擴(kuò)容時(shí)“搬南所有元素”小得多這也是deque兩端操作高效的根本原因。2.2 緩沖區(qū)大小是怎么定出來(lái)的deque的一個(gè)重要模板參數(shù)是緩沖區(qū)大小_S_buffer_size它決定了一塊緩沖區(qū)里最多能放多少個(gè)元素。如果用戶沒(méi)有顯式指定標(biāo)準(zhǔn)庫(kù)會(huì)按一個(gè)經(jīng)驗(yàn)公式?jīng)Q定。下面這段代碼是libstdc中__deque_buf_size的概念性邏輯// 概念性實(shí)現(xiàn)決定一塊deque緩沖區(qū)能容納的元素?cái)?shù)量 static inline size_t __deque_buf_size(size_t __size) { // __size 是模板參數(shù)指定的緩沖區(qū)字節(jié)數(shù)默認(rèn)情況下為 0 // 表示“按經(jīng)驗(yàn)規(guī)則自動(dòng)推導(dǎo)” if (sizeof(_Tp) 512) return size_t(512) / sizeof(_Tp); return size_t(1); }這個(gè)規(guī)則的意圖很清楚讓緩沖區(qū)內(nèi)存總量盡量不小于512字節(jié)但單個(gè)元素如果本身就超過(guò)512字節(jié)那就不含糊一塊緩沖區(qū)只放一個(gè)元素。舉個(gè)例子int通常是4字節(jié)那么一塊緩沖區(qū)放128個(gè)int一個(gè)大型結(jié)構(gòu)體如果有1024字節(jié)那么每個(gè)緩沖區(qū)就只有它自己。實(shí)際默認(rèn)的deque操作中這個(gè)512并不是“絕對(duì)必須”的量它體現(xiàn)的只是一種“內(nèi)存局部性和分配次數(shù)之間的平衡”。為什么不是64字節(jié)或4KB從歷史淵源看512字節(jié)在早期的分頁(yè)和緩存環(huán)境下是一個(gè)折中值太小會(huì)讓deque頻繁申請(qǐng)新緩沖區(qū)碎片和分配開(kāi)銷上升太大又會(huì)讓小元素情況下單塊緩沖區(qū)冗余過(guò)多。現(xiàn)代機(jī)器上這個(gè)值依然不過(guò)時(shí)因?yàn)檎嬲绊懶阅艿耐皇菃螇K緩沖區(qū)的大小而是跨緩沖區(qū)操作時(shí)分支預(yù)測(cè)和緩存命中的成本。如果你的元素是很小的類型并且你能預(yù)估總元素量那么可以在構(gòu)造deque時(shí)顯式傳入更大的緩沖區(qū)參數(shù)或者使用范圍構(gòu)造減少緩沖區(qū)數(shù)量這比默認(rèn)值在某些場(chǎng)景下更高效。2.3 迭代器如何跨塊移動(dòng)deque的迭代器是分析中最需要細(xì)看的部分。不同于vector迭代器可以簡(jiǎn)化為一個(gè)原生指針deque的迭代器在任何主流實(shí)現(xiàn)里都由四個(gè)指針組成。典型的_Deque_iterator結(jié)構(gòu)如下struct _Deque_iterator { _Tp* _M_cur; // 當(dāng)前指向的緩沖區(qū)內(nèi)的元素位置 _Tp* _M_first; // 當(dāng)前所在緩沖區(qū)的首地址 _Tp* _M_last; // 當(dāng)前所在緩沖區(qū)的尾后地址 _Map_pointer _M_node; // 指向map中登記當(dāng)前緩沖區(qū)地址的槽位 };這四個(gè)成員各有分工。_M_cur是真正的“當(dāng)前位置”_M_first和_M_last標(biāo)出當(dāng)前緩沖區(qū)的邊界_M_node用于在到達(dá)緩沖區(qū)末尾后找到下一個(gè)緩沖區(qū)的地址。每當(dāng)_M_cur移動(dòng)到_M_last就觸發(fā)一次“跨塊”操作通過(guò)_M_node拿到下一塊緩沖區(qū)的地址然后把_M_first、_M_last、_M_cur全部切換到新緩沖區(qū)中。對(duì)應(yīng)到源碼操作的邏輯可以用下面這段概念性代碼表示// 概念性實(shí)現(xiàn)deque迭代器自增跨越緩沖區(qū)邊界時(shí)需要切換node self operator() { _M_cur; if (_M_cur _M_last) { // 當(dāng)前緩沖區(qū)走到底了切換到下一塊 _M_set_node(_M_node 1); _M_cur _M_first; } return *this; }是簡(jiǎn)單的難點(diǎn)在于偏移運(yùn)算operator和operator-。這兩個(gè)操作不能直接對(duì)_M_cur做加減因?yàn)榭赡芸缭蕉鄠€(gè)緩沖區(qū)。它們的典型實(shí)現(xiàn)大致思路是先判斷目標(biāo)位置與當(dāng)前_M_cur的距離如果只跨越了當(dāng)前緩沖區(qū)的邊界就直接移動(dòng)cur如果跨度大就需要計(jì)算“當(dāng)前緩沖區(qū)剩余空間”和“每塊緩沖區(qū)可容納元素?cái)?shù)”一次性跳到正確的緩沖區(qū)再定位到塊內(nèi)具體位置。這也是為什么deque的隨機(jī)訪問(wèn)雖然復(fù)雜度是O(1)但常數(shù)比vector大得多vector的[]只需要一次指針運(yùn)算deque需要一次指針運(yùn)算加一次跨塊判斷甚至一次除法和一次取模。// 概念性實(shí)現(xiàn)跨多個(gè)緩沖區(qū)時(shí)的偏移計(jì)算思路 self operator(difference_type __n) { // 先算出當(dāng)前緩沖區(qū)還剩多少元素 difference_type __offset __n (_M_cur - _M_first); if (__offset 0 __offset difference_type(_S_buffer_size())) // 目標(biāo)還在當(dāng)前緩沖區(qū)內(nèi)部直接移動(dòng) _M_cur __n; else { // 需要跳塊 difference_type __node_offset __offset 0 ? __offset / _S_buffer_size() : -((__offset - 1) / _S_buffer_size()); // 切換到目標(biāo)緩沖區(qū) _M_set_node(_M_node __node_offset); // 再定位到塊內(nèi)偏移 _M_cur _M_first __offset - __node_offset * _S_buffer_size(); } return *this; }這段代碼最值得品味的地方就是對(duì)負(fù)數(shù)偏移的處理。當(dāng)__offset為負(fù)時(shí)不能簡(jiǎn)單用整除要做“向上取整”的除偏移計(jì)算否則會(huì)落到錯(cuò)誤緩沖區(qū)。這個(gè)細(xì)節(jié)在標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)里被一些非常精確的位運(yùn)算和判斷處理掉了。讀懂這段邏輯你基本就掌握了deque迭代器的全部精髓。3. 從源碼看deque的插入刪除邏輯上一部分是把deque的靜態(tài)結(jié)構(gòu)講清楚這一部分看動(dòng)態(tài)行為push、insert、erase和map擴(kuò)容分別是怎么實(shí)現(xiàn)的。這些操作最能體現(xiàn)STL源碼的設(shè)計(jì)取舍——哪些地方追求速度哪些地方寧可多花一點(diǎn)代價(jià)也要保證異常安全。3.1 push_back和push_front關(guān)鍵在邊界判斷deque的push_back邏輯并不復(fù)雜。它先看_M_finish._M_cur是不是已經(jīng)到達(dá)當(dāng)前緩沖區(qū)的末尾。如果還沒(méi)到說(shuō)明當(dāng)前緩沖區(qū)還有空位那就在_M_cur處構(gòu)造元素然后移動(dòng)_M_cur。如果已經(jīng)到了末尾就要先申請(qǐng)一塊新緩沖區(qū)把它登記進(jìn)map對(duì)應(yīng)的槽位再在新緩沖區(qū)首位置構(gòu)造元素。// 概念性實(shí)現(xiàn)push_back尾部分支 void push_back(const value_type __x) { if (_M_finish._M_cur ! _M_finish._M_last - 1) { // 當(dāng)前緩沖區(qū)還有空位直接就地構(gòu)造 _Construct(_M_finish._M_cur, __x); _M_finish._M_cur; } else { // 當(dāng)前緩沖區(qū)已滿先分配新緩沖區(qū)再構(gòu)造 _M_push_back_aux(__x); } }push_front完全對(duì)稱只是判斷_M_start._M_cur是否已經(jīng)到達(dá)當(dāng)前緩沖區(qū)的第一個(gè)元素。由于deque的緩沖區(qū)在邏輯上設(shè)定為“每一塊只使用其中一部分位置”兩端插入時(shí)經(jīng)常能直接利用當(dāng)前緩沖區(qū)的剩余空間而不必每次都新建緩沖區(qū)。這種“預(yù)留下一個(gè)槽位”的做法使得連續(xù)n次push_back中只有跨塊那次有明顯額外開(kāi)銷。這里藏著一個(gè)非常重要的源碼細(xì)節(jié)deque的緩沖區(qū)地址是與map槽位綁定的而map兩頭都有預(yù)留空位。當(dāng)你連續(xù)從兩端push元素導(dǎo)致某一端map預(yù)留槽位用盡時(shí)deque會(huì)觸發(fā)map擴(kuò)容而不是立刻搬運(yùn)元素。map擴(kuò)容只搬指針代價(jià)相對(duì)可控。正因?yàn)槿绱薲eque兩端大量操作時(shí)元素對(duì)象本身幾乎不會(huì)被搬動(dòng)已有元素的引用在大多數(shù)情況下依然有效。3.2 insert在中間搬哪邊是核心策略deque中間插入是所有操作里最“微妙”的。你沒(méi)有vector那種整齊的整段搬移也不像list那樣只需要改動(dòng)幾個(gè)指針。deque的做法是選擇“搬動(dòng)元素較少的一側(cè)”。假設(shè)在位置pos插入一個(gè)元素。如果pos到begin的距離小于pos到end的距離deque會(huì)選擇先在前端騰出一個(gè)空位——具體做法是push_front一個(gè)占位值然后從begin開(kāi)始把這一段元素整體向前移動(dòng)一位最終在pos位置填入真正的目標(biāo)值。反之如果pos更靠近尾部deque會(huì)先push_back一個(gè)占位值再把后面那段元素依次向后移動(dòng)一位。這個(gè)邏輯用“少花錢”來(lái)權(quán)衡整體的最壞時(shí)間依然是O(n)因?yàn)橹虚g插入必然導(dǎo)致這么多元素移動(dòng)。但和vector的“統(tǒng)一朝尾部搬”相比deque平均只搬一半元素。源碼中這個(gè)判斷典型出現(xiàn)在insert函數(shù)的分支邏輯里if (__pos._M_cur - __start._M_cur __finish._M_cur - __pos._M_cur) ... else ...。在C11之后的實(shí)現(xiàn)中這個(gè)搬移過(guò)程不再使用老式的逐個(gè)operator構(gòu)造而是引入了rotate_memmove這類機(jī)制。它把移動(dòng)操作轉(zhuǎn)成更底層的memmove調(diào)用大大減少了元素拷貝次數(shù)。也就是說(shuō)對(duì)于可平凡復(fù)制類型deque的中間插入在實(shí)測(cè)中會(huì)明顯快于只使用“逐元素賦值”的版本。3.3 erase的對(duì)稱搬移erase的邏輯與insert正好互補(bǔ)。刪除中間某個(gè)元素時(shí)deque會(huì)看這個(gè)元素離哪端更近。如果離begin更近就把begin到pos之間的元素向后移動(dòng)一位然后把最前端的元素銷毀最后執(zhí)行pop_front如果離end更近就反過(guò)來(lái)把pos到end之間的元素向前移動(dòng)一位銷毀末尾元素再pop_back。這個(gè)設(shè)計(jì)的意圖和insert是同一個(gè)道理只搬動(dòng)較短一側(cè)的元素避免無(wú)謂的長(zhǎng)距離移動(dòng)。源碼里你會(huì)看到對(duì)pos兩側(cè)距離的重復(fù)判斷這不是代碼冗余而是刻意為之。真正實(shí)現(xiàn)時(shí)中間區(qū)域的元素移動(dòng)同樣涉及跨緩沖區(qū)的處理但邏輯上仍然是往“靠近邊界的方向”移動(dòng)因此迭代器跨越緩沖區(qū)的規(guī)則完全能復(fù)用。有一個(gè)容易忽視的點(diǎn)erase刪除中間元素后容器會(huì)保持“所有元素連續(xù)無(wú)空洞”的狀態(tài)這是通過(guò)每次刪除后向一側(cè)填補(bǔ)空位實(shí)現(xiàn)的。也就是說(shuō)deque里不應(yīng)該存在“邏輯空洞”。如果你在調(diào)試時(shí)發(fā)現(xiàn)某個(gè)迭代器指向的值是銷毀后的殘留那通常是迭代器失效使用導(dǎo)致的而不是容器本身有洞。3.4 map擴(kuò)容與重新分配機(jī)制map擴(kuò)容在deque源碼里叫_M_reallocate_map。觸發(fā)條件一般是前端或后端可用的map槽位耗盡或者map整體需要擴(kuò)大。常見(jiàn)的擴(kuò)容策略是重新分配一個(gè)“舊map大小加固定增量再乘2”左右的新指針數(shù)組然后把舊的map指針拷貝到新數(shù)組的中間區(qū)域。為什么必須放在中間區(qū)域因?yàn)閐eque需要在兩端都保留空閑槽位。如果只在一側(cè)預(yù)留那么另一側(cè)的push就會(huì)很快耗盡空間導(dǎo)致map頻繁擴(kuò)容。所以源碼里有一系列計(jì)算確保_M_map[new_map_start old_size] 舊map首地址也就是把舊索引表整體平移一段距離。這個(gè)擴(kuò)容過(guò)程不觸碰任何元素對(duì)象只復(fù)制指針和重新設(shè)置兩個(gè)迭代器的_M_node。所以即使map擴(kuò)容發(fā)生對(duì)deque的使用者來(lái)說(shuō)也只是輕微的指針拷貝開(kāi)銷。但要注意map擴(kuò)容會(huì)讓舊迭代器持有的_M_node失效因?yàn)榕f迭代器還指著廢棄的map內(nèi)存。這時(shí)候如果你有一個(gè)之前保存的迭代器用它繼續(xù)操作就會(huì)產(chǎn)生未定義行為。這是很多deque bug的根源。4. 把deque包成stack和queue如果說(shuō)deque的源碼里寫(xiě)滿了內(nèi)存管理的精巧心思那么stack和queue的源碼就是“簡(jiǎn)潔得讓人驚訝”。它們本質(zhì)上都是適配器不是真正意義上的獨(dú)立容器。所謂適配器就是“我沒(méi)有自己的存儲(chǔ)我只是對(duì)底層容器的接口做了一層限制和包裝”。4.1 stack其實(shí)就是“后進(jìn)先出的單端視圖”一份概念上等價(jià)于libstdc中stack實(shí)現(xiàn)的核心骨架如下template typename T, typename Container std::dequeT class stack { public: using value_type typename Container::value_type; using reference typename Container::reference; using size_type typename Container::size_type; bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference top() { return c.back(); } const reference top() const { return c.back(); } void push(const value_type x) { c.push_back(x); } void push(value_type x) { c.push_back(std::move(x)); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_back(); } void swap(stack other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } protected: Container c; };請(qǐng)注意它的成員只有一個(gè)Container c;。所有對(duì)外接口都是對(duì)c的轉(zhuǎn)發(fā)。top其實(shí)是c.back()push其實(shí)是c.push_back()pop其實(shí)是c.pop_back()。stack沒(méi)有任何辦法訪問(wèn)底層容器的其他能力它只暴露后進(jìn)先出的語(yǔ)義。從設(shè)計(jì)模式角度講這是典型的“組合優(yōu)于繼承”stack不是deque的某種子類而是握著deque的組合者。因?yàn)閟tack只依賴back、push_back、pop_back、empty、size這幾個(gè)操作所以你能給stack換底層容器。用vector、deque、list都是合法的只要容器支持這些方法。面向源碼分析你會(huì)發(fā)現(xiàn)stack自己幾乎不產(chǎn)生任何計(jì)算量它的每一行代碼都是代理。這也是為什么有人開(kāi)玩笑說(shuō)“看了stack的源碼你會(huì)覺(jué)得STL的適配器是最容易被自己重新實(shí)現(xiàn)的部分”。4.2 queue要的是一進(jìn)一出的兩端配合queue的核心源碼骨架如下template typename T, typename Container std::dequeT class queue { public: reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } void push(const value_type x) { c.push_back(x); } void push(value_type x) { c.push_back(std::move(x)); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } protected: Container c; };queue的語(yǔ)義是“尾部進(jìn)、頭部出”所以它的push和stack一樣是push_back但pop換成了pop_front并且額外暴露了front和back兩個(gè)訪問(wèn)口。與stack相比queue對(duì)底層容器的接口要求更苛刻必須支持pop_front而vector沒(méi)有這個(gè)操作。因此標(biāo)準(zhǔn)規(guī)定queue的底層容器不能是vector常見(jiàn)選擇只有deque和list。有些人對(duì)“queue里藏著front/back兩個(gè)口”感到意外覺(jué)得隊(duì)列只需要看頭部就夠。但如果你想遍歷隊(duì)列或者查看隊(duì)尾back其實(shí)很方便。源碼里的這種接口設(shè)計(jì)也體現(xiàn)了標(biāo)準(zhǔn)庫(kù)在“最小必要功能”和“實(shí)用性”之間的取舍。4.3 為什么底層可以換成vector或list既然stack和queue都是適配器那么替換底層容器就是順理成章的事。你可以在定義時(shí)通過(guò)第二個(gè)模板參數(shù)指定容器類型// 用vector做stack的底層性能特征和vector一致 std::stackint, std::vectorint s; // 用list做queue的底層適合不需要隨機(jī)訪問(wèn)的場(chǎng)景 std::queueint, std::listint q;但要滿足約束條件。stack的容器必須提供back、push_back、pop_backvector、deque、list都滿足queue的容器必須額外提供front和pop_frontvector不滿足。如果你硬要傳vector給queue標(biāo)準(zhǔn)庫(kù)會(huì)報(bào)出編譯錯(cuò)誤。這種編譯期約束是模板帶來(lái)的天然類型檢查源碼層面上你甚至能看到一些實(shí)現(xiàn)通過(guò)static_assert反復(fù)確認(rèn)容器的迭代器類型就是為了把這種錯(cuò)誤攔截在編譯期而不是運(yùn)行期。那么默認(rèn)值為什么是deque對(duì)stack來(lái)說(shuō)vector的擴(kuò)容需要搬移元素list的緩存局部性差deque在尾端push_back是O(1)且極少觸發(fā)重分配。對(duì)queue來(lái)說(shuō)deque的頭部pop_front同樣是O(1)而vector連pop_front都不提供。綜合下來(lái)deque成為兩者共同的默認(rèn)選擇這是容器接口和性能預(yù)期雙向匹配的結(jié)果。5. 實(shí)測(cè)驗(yàn)證與避坑記錄看再多源碼不如動(dòng)手跑幾個(gè)實(shí)驗(yàn)。這一部分是我在實(shí)際使用中總結(jié)的幾個(gè)可復(fù)現(xiàn)觀察以及幾個(gè)高頻踩坑點(diǎn)。5.1 sizeof觀察deque的“體重”不輕在常見(jiàn)的64位Linux工具鏈下sizeof(std::dequeint)通常在80字節(jié)附近而sizeof(std::vectorint)是24字節(jié)sizeof(std::listint)也是24字節(jié)。這個(gè)差異看起來(lái)不大但如果你定義的是一個(gè)包含很多deque的數(shù)組或者一個(gè)類里有大量deque成員內(nèi)存開(kāi)銷的差距就比較明顯了。為什么deque對(duì)象這么“重”因?yàn)樗鼉?nèi)部要保存map指針、map大小、首尾兩個(gè)完整迭代器每個(gè)迭代器有四個(gè)指針成員。而vector只需要一個(gè)起始指針、一個(gè)結(jié)束指針、一個(gè)容量指針。如果你需要很多個(gè)小容器實(shí)例每個(gè)實(shí)例只存幾個(gè)元素那么用deque就要掂量一下。相反如果你確實(shí)需要雙端操作那些多出來(lái)的字節(jié)是完全值得的。5.2 迭代器失效規(guī)則不能靠猜deque的迭代器失效規(guī)則比vector和list都要復(fù)雜我見(jiàn)過(guò)太多在這個(gè)問(wèn)題上翻車的情況。先說(shuō)標(biāo)準(zhǔn)規(guī)定在deque中間插入或刪除元素時(shí)會(huì)導(dǎo)致所有迭代器失效并且引用也失效在兩端插入或刪除元素時(shí)所有指向已有元素的迭代器都會(huì)失效但指向已有元素的引用依然有效。這個(gè)規(guī)則初看很反直覺(jué)為什么兩端插入我的舊迭代器會(huì)失效元素卻沒(méi)被搬動(dòng)根源正是map。兩端插入可能觸發(fā)map擴(kuò)容舊迭代器持有的_M_node還指向老的map區(qū)域而map擴(kuò)容后元素實(shí)際所在的緩沖區(qū)被登記到了新map里舊迭代器就追不上新世界了。引用不失效則是因?yàn)樵貙?duì)象本身所在的緩沖區(qū)并沒(méi)有變化引用直接指向?qū)ο髢?nèi)存。實(shí)際編碼中的典型錯(cuò)誤是先保存一個(gè)it dq.begin()然后在另一端dq.push_back(x)再用it訪問(wèn)元素。按標(biāo)準(zhǔn)這是未定義行為。雖然在很多簡(jiǎn)單情況下舊迭代器的cur指針可能還指得對(duì)但那純屬運(yùn)氣。正確的做法是在兩端操作之后重新獲取迭代器比如dq.begin()或dq.end()。中間插入之后一切舊迭代器都要拋棄這一條沒(méi)有回旋余地。5.3 性能表象順序遍歷、隨機(jī)訪問(wèn)和中間插入用常規(guī)優(yōu)化編譯開(kāi)跑的簡(jiǎn)單評(píng)測(cè)下觀測(cè)結(jié)果大致是順序遍歷deque比vector慢但遠(yuǎn)快于list。慢的原因是遍歷時(shí)需要檢測(cè)是否到緩沖區(qū)邊界引入額外分支和緩存失效風(fēng)險(xiǎn)。但因?yàn)槊總€(gè)緩沖區(qū)內(nèi)部是連續(xù)內(nèi)存整體局部性比list好太多。隨機(jī)訪問(wèn)deque比vector慢20%上下這20%主要來(lái)自跨塊時(shí)的邊界計(jì)算。如果你在寫(xiě)一個(gè)大量隨機(jī)訪問(wèn)的算法比如二分查找的中間某層或快速選擇deque不會(huì)是首選。連續(xù)push_backdeque與vector相差不大vector偶爾觸發(fā)擴(kuò)容時(shí)會(huì)有一次大搬移deque則每塊緩沖區(qū)滿時(shí)分配新緩沖區(qū)。在大量push_back場(chǎng)景下deque往往表現(xiàn)得比vector更平緩因?yàn)闆](méi)有“一次性搬全部”的尖峰。中間插入deque和vector都是O(n)但deque只搬一半元素所以平均優(yōu)勢(shì)明顯。如果插入位置恰好接近中間deque通常優(yōu)于vector插入位置接近頭部時(shí)vector要搬幾乎所有元素deque卻可能借著前端插入的便利快速完成。這些細(xì)節(jié)疊加起來(lái)就形成了deque在STL容器里的真實(shí)生態(tài)位適合作為頻繁雙端操作的任務(wù)隊(duì)列、事件隊(duì)列、工作棧但不適合作為高性能隨機(jī)訪問(wèn)容器的底層存儲(chǔ)。6. 最后聊聊我怎么選型說(shuō)到底容器選型是一個(gè)匹配需求的過(guò)程。沒(méi)有任何容器在所有維度上都優(yōu)于其他容器deque的“雙端快”也是付出了“隨機(jī)訪問(wèn)多一次間接”的代價(jià)換來(lái)的。我自己的選擇習(xí)慣是如果任務(wù)只從尾部讀寫(xiě)也就是典型棧場(chǎng)景優(yōu)先用vector作為stack的底層原因很簡(jiǎn)單隨機(jī)訪問(wèn)快內(nèi)存局部性好而stack根本不需要頭部操作。如果任務(wù)需要一進(jìn)一出典型的隊(duì)列場(chǎng)景直接用默認(rèn)deque就好list雖然也可以但塊狀分配的deque在緩存和整體吞吐上通常更讓人放心。如果任務(wù)需要兩端同時(shí)插入刪除比如某些滑動(dòng)窗口或事件池別猶豫deque就是標(biāo)準(zhǔn)答案。如果任務(wù)的核心是大量隨機(jī)訪問(wèn)無(wú)論deque的頭尾操作多么誘人vector才是第一選擇。還有一個(gè)容易被忽略的點(diǎn)deque沒(méi)有reserve和capacity概念。初始化之后如果又預(yù)估會(huì)大量插入你無(wú)法像vector那樣預(yù)留空間。想優(yōu)化的話可以用區(qū)間構(gòu)造函數(shù)一次性填入元素或者顯式指定更大的緩沖區(qū)模板參數(shù)。如果做不到這兩點(diǎn)就接受它每次跨塊申請(qǐng)新緩沖區(qū)的固有開(kāi)銷。最后再分享一個(gè)小技巧閱讀deque源碼時(shí)不必每個(gè)函數(shù)都逐行讀。先看類成員尤其是base類和iterator類把內(nèi)存模型建立起來(lái)然后追蹤一次push_back的完整調(diào)用鏈最后單獨(dú)研究insert和erase的搬移方向判斷。把這四條線串起來(lái)你就能建立起對(duì)deque的整體認(rèn)知。源碼分析的價(jià)值也正在于此——它不教你背結(jié)論而是帶你看清每個(gè)設(shè)計(jì)決策背后的權(quán)衡。后續(xù)如果你再去讀其他容器的源碼會(huì)發(fā)現(xiàn)很多相似的模式在反復(fù)出現(xiàn)那才是真正屬于自己的收獲。