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