影石C++二面：解析deque底層實(shí)現(xiàn)原理與操作？
在日常開發(fā)中，我們常會(huì)遇到 “需要頻繁在兩端添加 / 刪除數(shù)據(jù)” 的場景 —— 比如實(shí)現(xiàn)滑動(dòng)窗口算法、封裝雙端隊(duì)列組件，或是構(gòu)建棧與隊(duì)列的底層容器。這時(shí)候，vector 的 “尾插高效但頭插需移動(dòng)大量元素”、list 的 “雙端操作快但隨機(jī)訪問低效”，都顯得不夠適配。而 deque（雙端隊(duì)列）恰好填補(bǔ)了這個(gè)空白：它既能像 vector 一樣支持隨機(jī)訪問，又能像 list 一樣實(shí)現(xiàn)雙端 O (1) 級(jí)別的插入 / 刪除。
但你是否好奇：deque 是如何做到 “魚與熊掌兼得” 的？它的底層既不是 vector 的 “單一連續(xù)內(nèi)存”，也不是 list 的 “離散節(jié)點(diǎn)鏈表”，而是一套更精巧的 “分段連續(xù)存儲(chǔ)” 架構(gòu)。理解這套架構(gòu)，不僅能幫你更合理地選擇容器，還能洞悉 “平衡效率與空間” 的設(shè)計(jì)思路。接下來，我們就從底層實(shí)現(xiàn)原理切入，拆解 deque 的存儲(chǔ)結(jié)構(gòu)，再逐一解析核心操作的執(zhí)行邏輯。
一、什么是deque？
在算法題的世界里，求解滑動(dòng)窗口最大值問題時(shí)，我們需要頻繁地在隊(duì)頭刪除元素以及在隊(duì)尾插入元素。傳統(tǒng)的隊(duì)列或數(shù)組結(jié)構(gòu)在應(yīng)對(duì)這種高頻次的兩端操作時(shí)，往往顯得力不從心。比如使用數(shù)組，隊(duì)頭刪除需要移動(dòng)大量元素，時(shí)間復(fù)雜度飆升；普通隊(duì)列雖然能滿足一端進(jìn)一端出，但對(duì)于兩端頻繁操作效率極低。而 deque 卻能以高效的雙端操作特性，為這類問題提供優(yōu)雅的解決方案，在每次窗口滑動(dòng)時(shí)，快速調(diào)整隊(duì)列元素，保證在 O (1) 時(shí)間復(fù)雜度內(nèi)完成隊(duì)頭刪除與隊(duì)尾插入 ，極大提升算法效率。
在微服務(wù)架構(gòu)里，任務(wù)隊(duì)列是協(xié)調(diào)各個(gè)服務(wù)間工作的關(guān)鍵組件。不同優(yōu)先級(jí)的任務(wù)需要高效地在隊(duì)列兩端進(jìn)行處理：高優(yōu)先級(jí)任務(wù)從隊(duì)頭進(jìn)入優(yōu)先處理，普通任務(wù)從隊(duì)尾正常排隊(duì)。若使用其他數(shù)據(jù)結(jié)構(gòu)，如鏈表雖然插入刪除靈活，但隨機(jī)訪問和整體管理復(fù)雜；數(shù)組雖能隨機(jī)訪問，但兩端操作效率低下，無法滿足任務(wù)隊(duì)列對(duì)兩端數(shù)據(jù)流轉(zhuǎn)的高效要求。deque 憑借其在兩端進(jìn)行 O (1) 級(jí)操作的特性，以及一定程度上支持隨機(jī)訪問的能力，能夠很好地適應(yīng)任務(wù)隊(duì)列的復(fù)雜場景，優(yōu)化任務(wù)調(diào)度流程，提高整個(gè)微服務(wù)系統(tǒng)的響應(yīng)速度和吞吐量。
在 C++ 標(biāo)準(zhǔn)庫中，stack（棧）和 queue（隊(duì)列）這兩種常用的容器適配器，默認(rèn)選擇 deque 作為底層容器。stack 需要高效的后進(jìn)先出操作，queue 需要高效的先進(jìn)先出操作，deque 既能在頭部和尾部快速插入和刪除元素，滿足 stack 和 queue 對(duì)兩端操作的需求，又具備一定的空間連續(xù)特性（雖不是真正連續(xù)，但邏輯上可隨機(jī)訪問），相較于 vector 在頭部操作時(shí)需要大量元素搬移，以及 list 在空間利用率和隨機(jī)訪問上的不足，deque 成為了實(shí)現(xiàn) stack 和 queue 底層的理想選擇 ，這也體現(xiàn)了 deque 在設(shè)計(jì)上對(duì)特定場景的高度適配性。
這些場景都指向同一個(gè)數(shù)據(jù)結(jié)構(gòu) ——deque（雙端隊(duì)列）。它就像是數(shù)據(jù)結(jié)構(gòu)領(lǐng)域的 “多面手”，既能像 vector 一樣支持隨機(jī)訪問，在需要快速定位元素時(shí)發(fā)揮作用；又能像 list 一樣實(shí)現(xiàn)雙端 O (1) 級(jí)操作，在頻繁進(jìn)行兩端元素的添加和刪除時(shí)展現(xiàn)出卓越的性能。其底層設(shè)計(jì)的精妙之處，正是破解 “效率與靈活性平衡” 難題的關(guān)鍵。本文將從底層存儲(chǔ)結(jié)構(gòu)開始，逐層解析 deque 的核心原理與操作邏輯，幫助開發(fā)者理解其設(shè)計(jì)哲學(xué)與適用場景。
二、deque底層實(shí)現(xiàn)原理
2.1 打破 “連續(xù)內(nèi)存” 的迷思：分段存儲(chǔ)架構(gòu)
在 C++ 中，deque（雙端隊(duì)列）的底層存儲(chǔ)結(jié)構(gòu)十分獨(dú)特，既不同于 vector 那種單一的連續(xù)數(shù)組，也不像 list 那樣是離散的鏈表。deque 采用的是 “中控?cái)?shù)組 + 分段緩沖區(qū)” 的復(fù)合結(jié)構(gòu)，這種設(shè)計(jì)讓它兼具了數(shù)組和鏈表的部分優(yōu)勢(shì) 。
具體來說，deque 有緩沖區(qū)（Buffer），這是實(shí)際存儲(chǔ)數(shù)據(jù)的地方，每個(gè)緩沖區(qū)是一塊固定大小的連續(xù)內(nèi)存塊。在 SGI STL 中，其默認(rèn)大小通常是 512 字節(jié)。當(dāng)一個(gè)緩沖區(qū)滿了之后，就會(huì)新建一個(gè)緩沖區(qū)，然后通過中控?cái)?shù)組將這些緩沖區(qū)關(guān)聯(lián)起來。這種方式避免了像 vector 那樣一次性分配大塊內(nèi)存可能失敗的問題，也減少了內(nèi)存碎片的產(chǎn)生。
中控?cái)?shù)組（Map）則是管理這些緩沖區(qū)的關(guān)鍵。它本質(zhì)上是一個(gè)指針數(shù)組，數(shù)組中的每個(gè)元素都指向一個(gè)緩沖區(qū)的起始地址。比如，中控?cái)?shù)組的第 i 個(gè)元素，就指向了第 i 個(gè)緩沖區(qū)。通過這種方式，deque 在邏輯上把這些分段的緩沖區(qū)連接成了一個(gè)連續(xù)的序列，盡管它們?cè)谖锢韮?nèi)存上可能并不連續(xù)。
圖片
迭代器（Iterator）在 deque 中也有著特殊的設(shè)計(jì)。由于 deque 的分段存儲(chǔ)特性，其迭代器不能像普通指針那樣簡單地進(jìn)行自增或自減操作。deque 的迭代器需要記錄當(dāng)前元素指針 cur、緩沖區(qū)起始指針 first、緩沖區(qū)末尾指針 last，以及中控?cái)?shù)組指針 node。通過這些指針，迭代器可以在不同的緩沖區(qū)之間跳轉(zhuǎn)，從而實(shí)現(xiàn)對(duì) deque 中所有元素的無縫遍歷。
圖片
2.2 中控?cái)?shù)組：管理分段內(nèi)存的 “目錄系統(tǒng)”
中控?cái)?shù)組在 deque 的底層實(shí)現(xiàn)中扮演著核心角色，它就像是一個(gè) “目錄系統(tǒng)”，精準(zhǔn)地管理著各個(gè)分段緩沖區(qū)的地址信息 。
當(dāng)中控?cái)?shù)組需要擴(kuò)容時(shí)，比如原有緩沖區(qū)指針已經(jīng)存滿，此時(shí)僅需分配新的中控?cái)?shù)組，并將原中控?cái)?shù)組中的指針拷貝到新數(shù)組中即可。相較于 vector 擴(kuò)容時(shí)需要遷移大量元素，這種方式的成本要低得多。在實(shí)際應(yīng)用中，當(dāng) deque 不斷向兩端添加元素，導(dǎo)致緩沖區(qū)數(shù)量增多，中控?cái)?shù)組原有的空間不足時(shí)，就會(huì)觸發(fā)這種高效的擴(kuò)容機(jī)制。這一設(shè)計(jì)使得 deque 在進(jìn)行雙端擴(kuò)展時(shí)，能夠始終保持高效，同時(shí)還避免了內(nèi)存碎片問題，確保了內(nèi)存使用的高效性和穩(wěn)定性。
2.3 迭代器的 “跨界” 魔法：如何實(shí)現(xiàn)邏輯連續(xù)訪問？
deque 迭代器的設(shè)計(jì)是實(shí)現(xiàn)其邏輯連續(xù)訪問的關(guān)鍵，當(dāng)?shù)鞯竭_(dá)當(dāng)前緩沖區(qū)末尾（cur == last）時(shí)，它會(huì)通過 node 指針找到中控?cái)?shù)組中下一個(gè)緩沖區(qū)的指針，然后將 cur 重置為新緩沖區(qū)的 first 位置，從而實(shí)現(xiàn)跨緩沖區(qū)的無縫迭代 。這一過程對(duì)用戶是完全透明的，用戶在使用 deque 時(shí)，無需關(guān)心其內(nèi)部復(fù)雜的存儲(chǔ)結(jié)構(gòu)和迭代器實(shí)現(xiàn)細(xì)節(jié)，就能夠像使用連續(xù)數(shù)組一樣，通過迭代器自由地遍歷 deque 中的元素，充分體現(xiàn)了 deque 在設(shè)計(jì)上的精妙之處。
用過 deque 的開發(fā)者都知道，它既能像 vector 一樣支持隨機(jī)訪問，又能像 list 一樣高效完成雙端插入 —— 但很少有人注意到，這背后藏著迭代器的 “跨界” 絕技：明明底層是分段內(nèi)存（中控?cái)?shù)組管理的零散緩沖區(qū)），迭代器卻能讓用戶感知到 “邏輯連續(xù)” 的訪問體驗(yàn)，就像在一塊完整內(nèi)存里遍歷一樣。
①第一步：看清 deque 的 “分段家底”
deque 的底層不是連續(xù)內(nèi)存，而是由兩部分組成：
- 中控?cái)?shù)組：本質(zhì)是個(gè) “指針目錄”，每個(gè)元素指向一塊固定大小的分段緩沖區(qū)（比如每個(gè)緩沖區(qū)存 100 個(gè) int）；
- 分段緩沖區(qū)：真正存數(shù)據(jù)的地方，緩沖區(qū)之間物理地址不連續(xù)，靠中控?cái)?shù)組的指針關(guān)聯(lián)。
比如一個(gè)存了 250 個(gè) int 的 deque，可能長這樣：
- 中控?cái)?shù)組有3個(gè)指針，分別指向Buffer1（存前 100 個(gè) int）、Buffer2（中間 100 個(gè)）、Buffer3（最后 50 個(gè)）；
- 三個(gè) Buffer 的物理地址可能相差很遠(yuǎn)，但中控?cái)?shù)組把它們 “串” 成了邏輯上的 “連續(xù)序列”。
而迭代器要做的，就是讓用戶在遍歷這 3 個(gè) Buffer 時(shí)，感覺不到 “跳轉(zhuǎn)”—— 這就需要它自帶 “定位 + 跨界導(dǎo)航” 能力。
②第二步：迭代器的 “四件套裝備”
deque 的迭代器不是簡單的 “內(nèi)存指針”（像 vector 的迭代器那樣），而是一個(gè) “智能導(dǎo)航儀”，內(nèi)置 4 個(gè)關(guān)鍵成員：
- cur：指向當(dāng)前訪問的元素（比如 Buffer1 里的第 50 個(gè) int）
- first：指向當(dāng)前緩沖區(qū)的起始地址（比如 Buffer1 的第一個(gè)元素）
- last：指向當(dāng)前緩沖區(qū)的末尾地址（比如 Buffer1 的第 100 個(gè)元素的下一位，標(biāo)記邊界）
- map_ptr：指向中控?cái)?shù)組中當(dāng)前緩沖區(qū)對(duì)應(yīng)的指針（比如中控?cái)?shù)組的第 0 個(gè)元素，即指向 Buffer1 的指針）
這四件套，就是 “跨界” 的核心 ——first和last用來判斷是否到了當(dāng)前緩沖區(qū)的邊界，map_ptr用來找下一個(gè) / 上一個(gè)緩沖區(qū)，cur負(fù)責(zé)定位具體元素。
③第三步：拆解 “跨界” 的核心邏輯
當(dāng)我們調(diào)用++it（迭代器向后移動(dòng)）或--it（向前移動(dòng)）時(shí)，迭代器會(huì)默默完成 “邊界判斷→緩沖區(qū)跳轉(zhuǎn)→重新定位” 的流程，用戶完全感知不到。
案例 1：向后迭代（++it）的 “跨界”
假設(shè)迭代器當(dāng)前在 Buffer1 的最后一個(gè)元素（cur == last - 1），此時(shí)執(zhí)行++it：
- 邊界檢測：迭代器發(fā)現(xiàn)cur + 1 == last（已經(jīng)到 Buffer1 的末尾），需要 “跨界”；
- 找下一個(gè)緩沖區(qū)：通過map_ptr（指向中控?cái)?shù)組第 0 個(gè)元素），移動(dòng)到下一個(gè)位置map_ptr++（現(xiàn)在指向中控?cái)?shù)組第 1 個(gè)元素，即 Buffer2 的地址）；
- 切換緩沖區(qū)：將first更新為 Buffer2 的起始地址，last更新為 Buffer2 的末尾地址；
- 定位新元素：將cur設(shè)為first（Buffer2 的第一個(gè)元素），完成 “跨界”。
整個(gè)過程就像：你在書架 A 的最后一本書，翻到下一頁時(shí)，系統(tǒng)自動(dòng)帶你走到書架 B 的第一本書 —— 你只覺得 “翻了一頁”，卻不知道背后換了書架。
案例 2：向前迭代（--it）的 “跨界”
如果迭代器當(dāng)前在 Buffer2 的第一個(gè)元素（cur == first），執(zhí)行--it：
- 邊界檢測：發(fā)現(xiàn)cur == first（到 Buffer2 的開頭），需要 “跨界”；
- 找前一個(gè)緩沖區(qū)：map_ptr--（回到中控?cái)?shù)組第 0 個(gè)元素，指向 Buffer1）；
- 切換緩沖區(qū)：first更新為 Buffer1 的起始地址，last更新為 Buffer1 的末尾地址；
- 定位新元素：cur設(shè)為last - 1（Buffer1 的最后一個(gè)元素），完成反向 “跨界”。
④第四步：為什么這很重要？
這種 “跨界” 設(shè)計(jì)，讓 deque 兼顧了兩種優(yōu)勢(shì)：
- 底層高效：分段內(nèi)存避免了 vector 擴(kuò)容時(shí)的大量數(shù)據(jù)遷移，中控?cái)?shù)組擴(kuò)容只需拷貝指針；
- 上層易用：迭代器的 “邏輯連續(xù)” 讓用戶可以像用 vector 一樣遍歷、隨機(jī)訪問（比如it + 5），不用關(guān)心底層分段。
舉個(gè)實(shí)際場景：用 deque 存儲(chǔ)日志數(shù)據(jù)，需要頻繁在頭部插入時(shí)間戳、尾部追加日志，同時(shí)還要遍歷打印所有日志。如果用 list，遍歷效率低；用 vector，頭部插入會(huì)移動(dòng)大量數(shù)據(jù)；而 deque 的迭代器讓 “遍歷” 和 “雙端插入” 都高效 —— 這就是 “跨界” 魔法的價(jià)值。
最后：deque 迭代器的 “跨界”，本質(zhì)是用 “智能導(dǎo)航邏輯”（四件套成員 + 邊界跳轉(zhuǎn)），掩蓋了底層分段內(nèi)存的物理不連續(xù)，給用戶呈現(xiàn)出 “邏輯連續(xù)” 的訪問體驗(yàn) —— 就像地圖軟件用 “無縫縮放” 掩蓋了地圖切片的拼接，讓你以為看到的是一整張地圖。
三、核心操作解析：雙端高效背后的算法邏輯
3.1 雙端插入 / 刪除：O (1) 效率的實(shí)現(xiàn)密碼
在 deque 的雙端插入和刪除操作中，以尾插（push_back）為例，當(dāng)我們執(zhí)行 push_back 操作時(shí)，deque 會(huì)首先檢查尾部緩沖區(qū)是否還有空余空間 。如果有，就如同在一個(gè)還有空位的書架上直接放置一本書一樣，直接將元素插入到尾部緩沖區(qū)的空閑位置，這一步操作的時(shí)間復(fù)雜度為 O (1)。但如果尾部緩沖區(qū)已滿，情況就會(huì)復(fù)雜一些。
此時(shí)，deque 需要新建一個(gè)緩沖區(qū)，就像在書架擺滿后需要添加一個(gè)新書架。接著，更新中控?cái)?shù)組，將新緩沖區(qū)的指針添加到中控?cái)?shù)組的相應(yīng)位置，最后把元素插入到新緩沖區(qū)的起始位置。雖然這個(gè)過程涉及到新緩沖區(qū)的分配和中控?cái)?shù)組的更新，但由于這些操作并不頻繁，所以均攤下來，尾插操作的時(shí)間復(fù)雜度仍然是 O (1)。
頭部插入（push_front）的邏輯與尾插類似，只是方向相反。當(dāng)頭部緩沖區(qū)有空間時(shí)，直接插入元素；若頭部緩沖區(qū)已滿，則新建緩沖區(qū)，在中控?cái)?shù)組的頭部添加新緩沖區(qū)的指針，然后插入元素。這種雙端插入的高效性，使得 deque 在需要頻繁在兩端添加元素的場景中表現(xiàn)出色，比如在實(shí)現(xiàn)一個(gè)支持快速添加任務(wù)的任務(wù)隊(duì)列時(shí)，無論是高優(yōu)先級(jí)任務(wù)從隊(duì)頭插入，還是普通任務(wù)從隊(duì)尾插入，deque 都能以高效的 O (1) 時(shí)間復(fù)雜度完成操作，大大提升了任務(wù)處理的效率 。
實(shí)現(xiàn)高效的雙端操作示例：
class Deque:
def __init__(self, buffer_size=4):
"""初始化雙端隊(duì)列，buffer_size為每個(gè)緩沖區(qū)的大小"""
self.buffer_size = buffer_size
# 中控?cái)?shù)組，存儲(chǔ)各個(gè)緩沖區(qū)的引用
self.map = []
# 頭部緩沖區(qū)索引和位置
self.head_buffer = 0
self.head_pos = 0
# 尾部緩沖區(qū)索引和位置
self.tail_buffer = 0
self.tail_pos = -1 # 初始化為-1表示空
# 當(dāng)前元素?cái)?shù)量
self.size = 0
def push_back(self, value):
"""在尾部插入元素"""
# 如果是第一個(gè)元素
if self.size == 0:
self.map.append([None] * self.buffer_size)
self.tail_pos = 0
self.map[self.tail_buffer][self.tail_pos] = value
self.size += 1
return
# 檢查尾部緩沖區(qū)是否已滿
if self.tail_pos == self.buffer_size - 1:
# 需要新建緩沖區(qū)
self.map.append([None] * self.buffer_size)
self.tail_buffer += 1
self.tail_pos = 0
else:
# 尾部緩沖區(qū)還有空間
self.tail_pos += 1
# 插入元素
self.map[self.tail_buffer][self.tail_pos] = value
self.size += 1
def push_front(self, value):
"""在頭部插入元素"""
# 如果是第一個(gè)元素
if self.size == 0:
self.map.append([None] * self.buffer_size)
self.head_pos = self.buffer_size - 1
self.map[self.head_buffer][self.head_pos] = value
self.size += 1
return
# 檢查頭部緩沖區(qū)是否已滿
if self.head_pos == 0:
# 需要新建緩沖區(qū)
self.map.insert(0, [None] * self.buffer_size)
self.head_pos = self.buffer_size - 1
# 尾部緩沖區(qū)索引也需要加1，因?yàn)樵陬^部插入了新緩沖區(qū)
self.tail_buffer += 1
else:
# 頭部緩沖區(qū)還有空間
self.head_pos -= 1
# 插入元素
self.map[self.head_buffer][self.head_pos] = value
self.size += 1
def pop_back(self):
"""從尾部刪除元素"""
if self.size == 0:
raise IndexError("pop from empty deque")
# 獲取尾部元素
value = self.map[self.tail_buffer][self.tail_pos]
# 更新尾部位置
if self.tail_pos == 0:
# 如果是緩沖區(qū)的第一個(gè)元素，刪除整個(gè)緩沖區(qū)
del self.map[self.tail_buffer]
self.tail_buffer -= 1
self.tail_pos = self.buffer_size - 1 if self.tail_buffer >= 0 else -1
else:
self.tail_pos -= 1
self.size -= 1
return value
def pop_front(self):
"""從頭部刪除元素"""
if self.size == 0:
raise IndexError("pop from empty deque")
# 獲取頭部元素
value = self.map[self.head_buffer][self.head_pos]
# 更新頭部位置
if self.head_pos == self.buffer_size - 1:
# 如果是緩沖區(qū)的最后一個(gè)元素，刪除整個(gè)緩沖區(qū)
del self.map[self.head_buffer]
# 尾部緩沖區(qū)索引也需要減1，因?yàn)閯h除了頭部的緩沖區(qū)
self.tail_buffer -= 1
self.head_pos = 0 if self.tail_buffer >= 0 else -1
else:
self.head_pos += 1
self.size -= 1
return value
def __str__(self):
"""返回deque的字符串表示"""
result = []
# 遍歷所有緩沖區(qū)
for i in range(len(self.map)):
# 確定當(dāng)前緩沖區(qū)的起始和結(jié)束位置
if i == self.head_buffer and i == self.tail_buffer:
# 頭部和尾部在同一個(gè)緩沖區(qū)
start, end = self.head_pos, self.tail_pos
elif i == self.head_buffer:
# 只是頭部緩沖區(qū)
start, end = self.head_pos, self.buffer_size - 1
elif i == self.tail_buffer:
# 只是尾部緩沖區(qū)
start, end = 0, self.tail_pos
else:
# 中間的完整緩沖區(qū)
start, end = 0, self.buffer_size - 1
# 添加元素
for j in range(start, end + 1):
result.append(str(self.map[i][j]))
return "Deque([" + ", ".join(result) + "])"
def __len__(self):
"""返回元素?cái)?shù)量"""
return self.size
# 使用案例
if __name__ == "__main__":
# 創(chuàng)建一個(gè)緩沖區(qū)大小為4的deque
dq = Deque(buffer_size=4)
print("初始狀態(tài):", dq)
# 尾部插入元素
for i in range(6):
dq.push_back(i)
print(f"push_back({i}): {dq}")
# 頭部插入元素
for i in range(1, 5):
dq.push_front(-i)
print(f"push_front(-{i}): {dq}")
print(f"當(dāng)前元素?cái)?shù)量: {len(dq)}")
# 尾部刪除元素
print("\n尾部刪除操作:")
for _ in range(3):
val = dq.pop_back()
print(f"pop_back() -> {val}, 剩余: {dq}")
# 頭部刪除元素
print("\n頭部刪除操作:")
for _ in range(3):
val = dq.pop_front()
print(f"pop_front() -> {val}, 剩余: {dq}")
# 混合操作
print("\n混合操作:")
dq.push_back(100)
print(f"push_back(100): {dq}")
dq.push_front(-100)
print(f"push_front(-100): {dq}")
dq.pop_back()
print(f"pop_back(): {dq}")
dq.pop_front()
print(f"pop_front(): {dq}")3.2 隨機(jī)訪問：分段結(jié)構(gòu)下的 O (1) 如何實(shí)現(xiàn)？
在 deque 中，雖然其元素存儲(chǔ)在分段的緩沖區(qū)中，但通過巧妙的數(shù)學(xué)計(jì)算，依然能夠?qū)崿F(xiàn) O (1) 的隨機(jī)訪問。假設(shè)我們要訪問 deque 中的第 n 個(gè)元素 。首先，計(jì)算緩沖區(qū)索引，即 buf_idx = n / 緩沖區(qū)大小，這一步就像是在一個(gè)多層書架中確定目標(biāo)書籍所在的書架層數(shù)。然后，計(jì)算緩沖區(qū)內(nèi)偏移量，offset = n % 緩沖區(qū)大小，這相當(dāng)于在確定的書架層中找到目標(biāo)書籍的具體位置。最后，通過中控?cái)?shù)組獲取緩沖區(qū)指針，訪問緩沖區(qū)起始地址 + offset，這樣就能準(zhǔn)確地定位到目標(biāo)元素。
盡管這個(gè)過程比在連續(xù)內(nèi)存的數(shù)組中直接通過索引訪問多了一次指針跳轉(zhuǎn)，即先通過中控?cái)?shù)組找到緩沖區(qū)指針，再在緩沖區(qū)內(nèi)定位元素，但由于每一步操作都是簡單的數(shù)學(xué)計(jì)算和指針操作，所以整體的時(shí)間復(fù)雜度仍然保持在 O (1)。在實(shí)際應(yīng)用中，當(dāng)我們需要快速獲取 deque 中某個(gè)位置的元素時(shí)，這種隨機(jī)訪問機(jī)制能夠快速響應(yīng)，雖然性能略遜于 vector 的直接內(nèi)存訪問，但遠(yuǎn)優(yōu)于 list 的鏈表式遍歷，比如在一個(gè)需要頻繁隨機(jī)讀取元素的數(shù)據(jù)分析場景中，deque 能夠在保證雙端操作高效的同時(shí)，較好地滿足隨機(jī)訪問的需求。
實(shí)現(xiàn)在分段結(jié)構(gòu)下的高效隨機(jī)訪問示例如下：
class Deque:
def __init__(self, buffer_size=4):
"""初始化雙端隊(duì)列，buffer_size為每個(gè)緩沖區(qū)的大小"""
self.buffer_size = buffer_size
self.map = [] # 中控?cái)?shù)組，存儲(chǔ)各個(gè)緩沖區(qū)的引用
# 頭部緩沖區(qū)索引和位置
self.head_buffer = 0
self.head_pos = 0
# 尾部緩沖區(qū)索引和位置
self.tail_buffer = 0
self.tail_pos = -1 # 初始化為-1表示空
self.size = 0 # 當(dāng)前元素?cái)?shù)量
def push_back(self, value):
"""在尾部插入元素"""
if self.size == 0:
self.map.append([None] * self.buffer_size)
self.tail_pos = 0
self.map[self.tail_buffer][self.tail_pos] = value
self.size += 1
return
if self.tail_pos == self.buffer_size - 1:
self.map.append([None] * self.buffer_size)
self.tail_buffer += 1
self.tail_pos = 0
else:
self.tail_pos += 1
self.map[self.tail_buffer][self.tail_pos] = value
self.size += 1
def push_front(self, value):
"""在頭部插入元素"""
if self.size == 0:
self.map.append([None] * self.buffer_size)
self.head_pos = self.buffer_size - 1
self.map[self.head_buffer][self.head_pos] = value
self.size += 1
return
if self.head_pos == 0:
self.map.insert(0, [None] * self.buffer_size)
self.head_pos = self.buffer_size - 1
self.tail_buffer += 1
else:
self.head_pos -= 1
self.map[self.head_buffer][self.head_pos] = value
self.size += 1
def pop_back(self):
"""從尾部刪除元素"""
if self.size == 0:
raise IndexError("pop from empty deque")
value = self.map[self.tail_buffer][self.tail_pos]
if self.tail_pos == 0:
del self.map[self.tail_buffer]
self.tail_buffer -= 1
self.tail_pos = self.buffer_size - 1 if self.tail_buffer >= 0 else -1
else:
self.tail_pos -= 1
self.size -= 1
return value
def pop_front(self):
"""從頭部刪除元素"""
if self.size == 0:
raise IndexError("pop from empty deque")
value = self.map[self.head_buffer][self.head_pos]
if self.head_pos == self.buffer_size - 1:
del self.map[self.head_buffer]
self.tail_buffer -= 1
self.head_pos = 0 if self.tail_buffer >= 0 else -1
else:
self.head_pos += 1
self.size -= 1
return value
def __getitem__(self, index):
"""實(shí)現(xiàn)隨機(jī)訪問，時(shí)間復(fù)雜度O(1)"""
if index < 0 or index >= self.size:
raise IndexError("deque index out of range")
# 計(jì)算目標(biāo)元素所在的緩沖區(qū)和位置
current_buffer = self.head_buffer
current_pos = self.head_pos
# 如果在頭部緩沖區(qū)
if index < (self.buffer_size - self.head_pos):
return self.map[current_buffer][current_pos + index]
# 減去頭部緩沖區(qū)的元素?cái)?shù)量
index -= (self.buffer_size - self.head_pos)
current_buffer += 1
# 遍歷中間緩沖區(qū)
while current_buffer < self.tail_buffer:
if index < self.buffer_size:
return self.map[current_buffer][index]
index -= self.buffer_size
current_buffer += 1
# 最后在尾部緩沖區(qū)
return self.map[current_buffer][index]
def __str__(self):
"""返回deque的字符串表示"""
result = []
for i in range(len(self.map)):
if i == self.head_buffer and i == self.tail_buffer:
start, end = self.head_pos, self.tail_pos
elif i == self.head_buffer:
start, end = self.head_pos, self.buffer_size - 1
elif i == self.tail_buffer:
start, end = 0, self.tail_pos
else:
start, end = 0, self.buffer_size - 1
for j in range(start, end + 1):
result.append(str(self.map[i][j]))
return "Deque([" + ", ".join(result) + "])"
def __len__(self):
"""返回元素?cái)?shù)量"""
return self.size
# 使用案例：測試隨機(jī)訪問功能
if __name__ == "__main__":
dq = Deque(buffer_size=4)
# 向隊(duì)列中添加元素
for i in range(1, 11):
dq.push_back(i)
for i in range(1, 6):
dq.push_front(-i)
print("隊(duì)列內(nèi)容:", dq)
print("隊(duì)列長度:", len(dq))
# 測試隨機(jī)訪問
print("\n隨機(jī)訪問測試:")
indices = [0, 2, 5, 8, 10, 14]
for idx in indices:
print(f"dq[{idx}] = {dq[idx]}")
# 測試邊界情況
print("\n邊界測試:")
print(f"第一個(gè)元素: dq[0] = {dq[0]}")
print(f"最后一個(gè)元素: dq[{len(dq)-1}] = {dq[len(dq)-1]}")
# 測試插入刪除后再訪問
print("\n操作后訪問測試:")
dq.pop_front()
dq.pop_back()
dq.push_back(99)
print("操作后的隊(duì)列:", dq)
print(f"dq[3] = {dq[3]}, dq[10] = {dq[10]}")3.3 中間操作：為何 deque 不擅長 “中間地帶”？
deque 在中間位置進(jìn)行插入和刪除操作時(shí)，效率并不高。當(dāng)在中間位置插入元素時(shí)，如果插入位置在當(dāng)前緩沖區(qū)內(nèi)部，那么需要將插入位置之后的元素依次向后移動(dòng)一個(gè)位置，為新元素騰出空間 。這就好比在一排緊密排列的書架中間插入一本新書，需要將后面的書依次向后挪動(dòng)。如果插入位置跨緩沖區(qū)，不僅要移動(dòng)元素，還需要調(diào)整中控?cái)?shù)組的指針，以保證邏輯上的連續(xù)性。刪除操作同理，需要將刪除位置之后的元素向前移動(dòng)，若跨緩沖區(qū)同樣要調(diào)整中控?cái)?shù)組。這種操作涉及到大量元素的移動(dòng)以及中控?cái)?shù)組的調(diào)整，時(shí)間復(fù)雜度為 O (n)，與 list 在中間位置通過指針操作實(shí)現(xiàn) O (1) 的插入刪除效率相比，deque 在中間操作上明顯處于劣勢(shì)。
所以，在實(shí)際使用 deque 時(shí)，應(yīng)盡量避免在中間位置進(jìn)行頻繁操作，而將其應(yīng)用場景主要聚焦在雙端操作上。比如在實(shí)現(xiàn)一個(gè)消息隊(duì)列時(shí)，如果消息主要是從隊(duì)頭取出和隊(duì)尾插入，偶爾需要獲取隊(duì)列中間的某個(gè)消息，deque 能夠很好地勝任；但如果需要頻繁在隊(duì)列中間插入或刪除消息，那么 deque 就不是最佳選擇，此時(shí)可以考慮使用 list 等更適合中間操作的數(shù)據(jù)結(jié)構(gòu) 。
代碼示例如下：
import time
class Deque:
def __init__(self, buffer_size=4):
"""初始化雙端隊(duì)列，buffer_size為每個(gè)緩沖區(qū)的大小"""
self.buffer_size = buffer_size
self.map = [] # 中控?cái)?shù)組，存儲(chǔ)各個(gè)緩沖區(qū)的引用
# 頭部緩沖區(qū)索引和位置
self.head_buffer = 0
self.head_pos = 0
# 尾部緩沖區(qū)索引和位置
self.tail_buffer = 0
self.tail_pos = -1 # 初始化為-1表示空
self.size = 0 # 當(dāng)前元素?cái)?shù)量
def push_back(self, value):
"""在尾部插入元素"""
if self.size == 0:
self.map.append([None] * self.buffer_size)
self.tail_pos = 0
self.map[self.tail_buffer][self.tail_pos] = value
self.size += 1
return
if self.tail_pos == self.buffer_size - 1:
self.map.append([None] * self.buffer_size)
self.tail_buffer += 1
self.tail_pos = 0
else:
self.tail_pos += 1
self.map[self.tail_buffer][self.tail_pos] = value
self.size += 1
def push_front(self, value):
"""在頭部插入元素"""
if self.size == 0:
self.map.append([None] * self.buffer_size)
self.head_pos = self.buffer_size - 1
self.map[self.head_buffer][self.head_pos] = value
self.size += 1
return
if self.head_pos == 0:
self.map.insert(0, [None] * self.buffer_size)
self.head_pos = self.buffer_size - 1
self.tail_buffer += 1
else:
self.head_pos -= 1
self.map[self.head_buffer][self.head_pos] = value
self.size += 1
def pop_back(self):
"""從尾部刪除元素"""
if self.size == 0:
raise IndexError("pop from empty deque")
value = self.map[self.tail_buffer][self.tail_pos]
if self.tail_pos == 0:
del self.map[self.tail_buffer]
self.tail_buffer -= 1
self.tail_pos = self.buffer_size - 1 if self.tail_buffer >= 0 else -1
else:
self.tail_pos -= 1
self.size -= 1
return value
def pop_front(self):
"""從頭部刪除元素"""
if self.size == 0:
raise IndexError("pop from empty deque")
value = self.map[self.head_buffer][self.head_pos]
if self.head_pos == self.buffer_size - 1:
del self.map[self.head_buffer]
self.tail_buffer -= 1
self.head_pos = 0 if self.tail_buffer >= 0 else -1
else:
self.head_pos += 1
self.size -= 1
return value
def __getitem__(self, index):
"""實(shí)現(xiàn)隨機(jī)訪問，時(shí)間復(fù)雜度O(1)"""
if index < 0 or index >= self.size:
raise IndexError("deque index out of range")
# 計(jì)算目標(biāo)元素所在的緩沖區(qū)和位置
current_buffer = self.head_buffer
current_pos = self.head_pos
# 如果在頭部緩沖區(qū)
if index < (self.buffer_size - self.head_pos):
return self.map[current_buffer][current_pos + index]
# 減去頭部緩沖區(qū)的元素?cái)?shù)量
index -= (self.buffer_size - self.head_pos)
current_buffer += 1
# 遍歷中間緩沖區(qū)
while current_buffer < self.tail_buffer:
if index < self.buffer_size:
return self.map[current_buffer][index]
index -= self.buffer_size
current_buffer += 1
# 最后在尾部緩沖區(qū)
return self.map[current_buffer][index]
def _get_buffer_and_pos(self, index):
"""輔助方法：獲取指定索引對(duì)應(yīng)的緩沖區(qū)和位置"""
if index < 0 or index >= self.size:
raise IndexError("deque index out of range")
current_buffer = self.head_buffer
current_pos = self.head_pos
# 檢查頭部緩沖區(qū)
if index < (self.buffer_size - self.head_pos):
return current_buffer, current_pos + index
# 減去頭部緩沖區(qū)的元素?cái)?shù)量
index -= (self.buffer_size - self.head_pos)
current_buffer += 1
# 檢查中間緩沖區(qū)
while current_buffer < self.tail_buffer:
if index < self.buffer_size:
return current_buffer, index
index -= self.buffer_size
current_buffer += 1
# 尾部緩沖區(qū)
return current_buffer, index
def insert(self, index, value):
"""在指定索引位置插入元素（中間操作，效率低）"""
if index < 0 or index > self.size:
raise IndexError("insert index out of range")
# 特殊情況：在頭部或尾部插入
if index == 0:
self.push_front(value)
return
if index == self.size:
self.push_back(value)
return
# 找到插入位置所在的緩沖區(qū)和位置
buf_idx, pos = self._get_buffer_and_pos(index)
# 檢查當(dāng)前緩沖區(qū)是否有空間
# 計(jì)算當(dāng)前緩沖區(qū)的元素?cái)?shù)量
if buf_idx == self.head_buffer and buf_idx == self.tail_buffer:
buf_elements = self.tail_pos - self.head_pos + 1
elif buf_idx == self.head_buffer:
buf_elements = self.buffer_size - self.head_pos
elif buf_idx == self.tail_buffer:
buf_elements = self.tail_pos + 1
else:
buf_elements = self.buffer_size
# 如果當(dāng)前緩沖區(qū)有空間
if buf_elements < self.buffer_size:
# 移動(dòng)當(dāng)前緩沖區(qū)中插入位置后的元素
for i in range(buf_elements - (pos - (self.head_pos if buf_idx == self.head_buffer else 0)), 0, -1):
self.map[buf_idx][pos + i] = self.map[buf_idx][pos + i - 1]
self.map[buf_idx][pos] = value
self.size += 1
# 更新尾部位置（如果是尾部緩沖區(qū)）
if buf_idx == self.tail_buffer:
self.tail_pos += 1
return
# 如果當(dāng)前緩沖區(qū)已滿，需要拆分緩沖區(qū)
# 這是更復(fù)雜的情況，需要?jiǎng)?chuàng)建新緩沖區(qū)并移動(dòng)元素
# 創(chuàng)建新緩沖區(qū)
new_buf = [None] * self.buffer_size
self.map.insert(buf_idx + 1, new_buf)
# 移動(dòng)當(dāng)前緩沖區(qū)后半部分元素到新緩沖區(qū)
elements_to_move = self.buffer_size - pos
for i in range(elements_to_move):
new_buf[i] = self.map[buf_idx][pos + i]
self.map[buf_idx][pos + i] = None
# 插入新元素
self.map[buf_idx][pos] = value
# 更新尾部緩沖區(qū)索引（因?yàn)椴迦肓诵戮彌_區(qū)）
if self.tail_buffer >= buf_idx:
self.tail_buffer += 1
# 更新尾部位置（如果需要）
if buf_idx == self.tail_buffer - 1:
self.tail_pos = elements_to_move - 1
self.size += 1
def delete(self, index):
"""刪除指定索引位置的元素（中間操作，效率低）"""
if index < 0 or index >= self.size:
raise IndexError("delete index out of range")
# 特殊情況：刪除頭部或尾部元素
if index == 0:
return self.pop_front()
if index == self.size - 1:
return self.pop_back()
# 找到要?jiǎng)h除的元素所在的緩沖區(qū)和位置
buf_idx, pos = self._get_buffer_and_pos(index)
# 保存要?jiǎng)h除的值
value = self.map[buf_idx][pos]
# 移動(dòng)元素填補(bǔ)空缺
# 計(jì)算當(dāng)前緩沖區(qū)的結(jié)束位置
if buf_idx == self.tail_buffer:
end_pos = self.tail_pos
else:
end_pos = self.buffer_size - 1
# 移動(dòng)當(dāng)前緩沖區(qū)的元素
for i in range(pos, end_pos):
self.map[buf_idx][i] = self.map[buf_idx][i + 1]
self.map[buf_idx][end_pos] = None
# 如果不是尾部緩沖區(qū)，需要從下一個(gè)緩沖區(qū)移動(dòng)一個(gè)元素過來
current_buf = buf_idx
while current_buf < self.tail_buffer:
# 獲取下一個(gè)緩沖區(qū)
next_buf = current_buf + 1
# 將下一個(gè)緩沖區(qū)的第一個(gè)元素移到當(dāng)前緩沖區(qū)的末尾
self.map[current_buf][end_pos] = self.map[next_buf][0]
self.map[next_buf][0] = None
# 移動(dòng)下一個(gè)緩沖區(qū)的所有元素
next_end_pos = self.tail_pos if next_buf == self.tail_buffer else self.buffer_size - 1
for i in range(0, next_end_pos):
self.map[next_buf][i] = self.map[next_buf][i + 1]
self.map[next_buf][i + 1] = None
current_buf = next_buf
end_pos = self.buffer_size - 1
# 更新尾部位置
if self.tail_pos > 0:
self.tail_pos -= 1
else:
# 如果尾部緩沖區(qū)為空，刪除它
if self.tail_buffer > 0:
del self.map[self.tail_buffer]
self.tail_buffer -= 1
self.tail_pos = self.buffer_size - 1
else:
# 只剩下一個(gè)緩沖區(qū)且為空
self.tail_pos = -1
self.size -= 1
return value
def __str__(self):
"""返回deque的字符串表示"""
result = []
for i in range(len(self.map)):
if i == self.head_buffer and i == self.tail_buffer:
start, end = self.head_pos, self.tail_pos
elif i == self.head_buffer:
start, end = self.head_pos, self.buffer_size - 1
elif i == self.tail_buffer:
start, end = 0, self.tail_pos
else:
start, end = 0, self.buffer_size - 1
for j in range(start, end + 1):
result.append(str(self.map[i][j]))
return "Deque([" + ", ".join(result) + "])"
def __len__(self):
"""返回元素?cái)?shù)量"""
return self.size
# 測試deque的中間操作
def test_deque_middle_operations():
dq = Deque(buffer_size=4)
# 初始化隊(duì)列
for i in range(1, 11):
dq.push_back(i)
print("初始隊(duì)列:", dq)
# 測試中間插入
dq.insert(3, 99)
print("在索引3插入99后:", dq)
dq.insert(7, 100)
print("在索引7插入100后:", dq)
# 測試中間刪除
dq.delete(4)
print("刪除索引4的元素后:", dq)
dq.delete(5)
print("刪除索引5的元素后:", dq)
# 性能對(duì)比測試
def performance_comparison():
# 測試規(guī)模
size = 10000
iterations = 1000
# 初始化deque和list
dq = Deque(buffer_size=100)
lst = []
# 填充數(shù)據(jù)
for i in range(size):
dq.push_back(i)
lst.append(i)
# 測試deque的中間插入
start = time.time()
for i in range(iterations):
# 在中間位置插入
dq.insert(size//2, i)
deque_insert_time = time.time() - start
# 測試list的中間插入
start = time.time()
for i in range(iterations):
# 在中間位置插入
lst.insert(size//2, i)
list_insert_time = time.time() - start
# 測試deque的中間刪除
start = time.time()
for _ in range(iterations):
# 刪除中間位置的元素
dq.delete(size//2)
deque_delete_time = time.time() - start
# 測試list的中間刪除
start = time.time()
for _ in range(iterations):
# 刪除中間位置的元素
del lst[size//2]
list_delete_time = time.time() - start
print(f"\n性能對(duì)比測試 (規(guī)模: {size}, 操作次數(shù): {iterations}):")
print(f"deque中間插入耗時(shí): {deque_insert_time:.6f}秒")
print(f"list中間插入耗時(shí): {list_insert_time:.6f}秒")
print(f"deque中間刪除耗時(shí): {deque_delete_time:.6f}秒")
print(f"list中間刪除耗時(shí): {list_delete_time:.6f}秒")
print(f"deque插入比list慢 {deque_insert_time/list_insert_time:.2f}倍")
print(f"deque刪除比list慢 {deque_delete_time/list_delete_time:.2f}倍")
if __name__ == "__main__":
test_deque_middle_operations()
performance_comparison()運(yùn)行結(jié)果會(huì)清晰顯示：雖然 deque 在雙端操作上表現(xiàn)出色，但在中間位置的插入和刪除操作上，其效率遠(yuǎn)低于 list。這驗(yàn)證了 deque 不適合頻繁進(jìn)行中間操作的特性，應(yīng)將其主要用于雙端操作場景。
3.4 容量管理：無 capacity () 的背后設(shè)計(jì)
deque 與 vector 不同，它沒有 capacity () 的概念。vector 為了避免頻繁的內(nèi)存重新分配，會(huì)預(yù)先分配一定的內(nèi)存空間，當(dāng)元素?cái)?shù)量超過當(dāng)前容量時(shí)，再進(jìn)行擴(kuò)容操作，這可能涉及到大量元素的拷貝和舊內(nèi)存的釋放 。而 deque 采用分段存儲(chǔ)的方式，天然支持動(dòng)態(tài)擴(kuò)展。當(dāng)需要存儲(chǔ)更多元素時(shí)，只需添加新的緩沖區(qū)，并在中控?cái)?shù)組中添加對(duì)應(yīng)的指針即可，無需一次性預(yù)分配大量內(nèi)存。這種方式使得 deque 的內(nèi)存利用率更高，不會(huì)因?yàn)轭A(yù)分配過多內(nèi)存而造成浪費(fèi)。
然而，這種設(shè)計(jì)也意味著 deque 無法通過預(yù)分配內(nèi)存來優(yōu)化批量插入性能。在某些需要批量插入大量元素的場景中，vector 可以通過 reserve () 函數(shù)預(yù)先分配足夠的內(nèi)存，從而減少插入過程中的內(nèi)存重新分配次數(shù)，提高插入效率 。但 deque 由于其獨(dú)特的存儲(chǔ)結(jié)構(gòu)，無法采用類似的優(yōu)化方式。
不過，在大多數(shù)情況下，deque 在雙端操作上的高效性以及良好的內(nèi)存管理特性，使其在許多場景中依然是一種非常實(shí)用的數(shù)據(jù)結(jié)構(gòu)，比如在實(shí)現(xiàn)一個(gè)實(shí)時(shí)數(shù)據(jù)處理系統(tǒng)中的數(shù)據(jù)緩沖區(qū)時(shí)，deque 能夠根據(jù)數(shù)據(jù)的實(shí)時(shí)流入動(dòng)態(tài)擴(kuò)展，有效地利用內(nèi)存資源 。C++ 實(shí)現(xiàn) deque 的容量管理機(jī)制：
#include <iostream>
#include <vector>
#include <chrono>
#include <iomanip>
// 自定義Deque實(shí)現(xiàn)，用于展示容量管理機(jī)制
template <typename T>
class CustomDeque {
private:
size_t buffer_size_; // 每個(gè)緩沖區(qū)的大小
std::vector<std::vector<T>> map_; // 中控?cái)?shù)組，存儲(chǔ)緩沖區(qū)
size_t head_buffer_; // 頭部緩沖區(qū)索引
size_t head_pos_; // 頭部位置
size_t tail_buffer_; // 尾部緩沖區(qū)索引
size_t tail_pos_; // 尾部位置
size_t size_; // 元素總數(shù)
public:
// 構(gòu)造函數(shù)
CustomDeque(size_t buffer_size = 4)
: buffer_size_(buffer_size),
head_buffer_(0),
head_pos_(0),
tail_buffer_(0),
tail_pos_(-1), // -1表示空
size_(0) {}
// 尾部插入元素
void push_back(const T& value) {
if (size_ == 0) {
map_.emplace_back(buffer_size_);
tail_pos_ = 0;
map_[tail_buffer_][tail_pos_] = value;
size_++;
return;
}
// 檢查尾部緩沖區(qū)是否已滿
if (tail_pos_ == buffer_size_ - 1) {
// 新建緩沖區(qū)
map_.emplace_back(buffer_size_);
tail_buffer_++;
tail_pos_ = 0;
} else {
tail_pos_++;
}
map_[tail_buffer_][tail_pos_] = value;
size_++;
}
// 獲取緩沖區(qū)數(shù)量
size_t get_buffer_count() const {
return map_.size();
}
// 獲取總分配的槽位數(shù)量（包括未使用的）
size_t get_total_allocated_slots() const {
return map_.size() * buffer_size_;
}
// 獲取元素?cái)?shù)量
size_t size() const {
return size_;
}
};
// 演示容量管理對(duì)比
void demonstrate_capacity_management() {
const size_t buffer_size = 4;
CustomDeque<int> dq(buffer_size);
std::vector<int> vec; // 用vector模擬C++的vector（動(dòng)態(tài)數(shù)組）
// 檢查點(diǎn)：緩沖區(qū)可能發(fā)生變化的位置
std::vector<size_t> check_points = {1, 3, 4, 5, 8, 9, 15, 16, 17, 31, 32, 33};
std::cout << "容量管理對(duì)比測試（元素?cái)?shù)量 -> deque緩沖區(qū)數(shù)/總槽位 vs vector容量）：" << std::endl;
std::cout << std::left
<< std::setw(8) << "元素?cái)?shù)"
<< std::setw(16) << "deque緩沖區(qū)數(shù)"
<< std::setw(16) << "deque總槽位"
<< std::setw(16) << "vector容量" << std::endl;
std::cout << std::string(56, '-') << std::endl;
for (size_t i = 1; i <= 33; ++i) {
dq.push_back(i);
vec.push_back(i);
if (std::find(check_points.begin(), check_points.end(), i) != check_points.end()) {
size_t dq_buffers = dq.get_buffer_count();
size_t dq_slots = dq.get_total_allocated_slots();
size_t vec_capacity = vec.capacity();
std::cout << std::left
<< std::setw(8) << i
<< std::setw(16) << dq_buffers
<< std::setw(16) << dq_slots
<< std::setw(16) << vec_capacity << std::endl;
}
}
}
// 批量插入性能測試
void bulk_insert_performance() {
const size_t data_size = 100000;
// 準(zhǔn)備測試數(shù)據(jù)
std::vector<int> test_data(data_size);
for (size_t i = 0; i < data_size; ++i) {
test_data[i] = i;
}
// 測試CustomDeque的批量插入
CustomDeque<int> dq(100);
auto start = std::chrono::high_resolution_clock::now();
for (int val : test_data) {
dq.push_back(val);
}
auto end = std::chrono::high_resolution_clock::now();
double deque_time = std::chrono::duration<double>(end - start).count();
// 測試普通vector的批量插入
std::vector<int> vec;
start = std::chrono::high_resolution_clock::now();
for (int val : test_data) {
vec.push_back(val);
}
end = std::chrono::high_resolution_clock::now();
double vector_time = std::chrono::duration<double>(end - start).count();
// 測試預(yù)分配容量的vector插入
std::vector<int> prealloc_vec;
prealloc_vec.reserve(data_size); // 預(yù)分配容量
start = std::chrono::high_resolution_clock::now();
for (int val : test_data) {
prealloc_vec.push_back(val);
}
end = std::chrono::high_resolution_clock::now();
double prealloc_time = std::chrono::duration<double>(end - start).count();
std::cout << "\n批量插入性能測試（" << data_size << "個(gè)元素）：" << std::endl;
std::cout << std::fixed << std::setprecision(6);
std::cout << "deque插入時(shí)間: " << deque_time << "秒" << std::endl;
std::cout << "普通vector插入時(shí)間: " << vector_time << "秒" << std::endl;
std::cout << "預(yù)分配vector插入時(shí)間: " << prealloc_time << "秒" << std::endl;
std::cout << "deque vs 普通vector: " << (deque_time / vector_time) << "倍" << std::endl;
std::cout << "deque vs 預(yù)分配vector: " << (deque_time / prealloc_time) << "倍" << std::endl;
}
int main() {
demonstrate_capacity_management();
bulk_insert_performance();
return 0;
}這正是 deque 設(shè)計(jì)的特點(diǎn)：不提供capacity()和reserve()方法，通過分段存儲(chǔ)實(shí)現(xiàn)高效的動(dòng)態(tài)擴(kuò)展，在內(nèi)存利用和雙端操作效率上具有優(yōu)勢(shì)，但在批量插入場景中略遜于預(yù)分配的 vector。
四、與兄弟容器的對(duì)比：何時(shí)選擇 deque？
4.1代碼說明
在 C++ 的標(biāo)準(zhǔn)庫中，deque 與 vector 和 list 一同構(gòu)成了順序容器的重要成員，但它們各自有著獨(dú)特的設(shè)計(jì)理念和適用場景 。
vector 是連續(xù)內(nèi)存存儲(chǔ)的代表，就像一整條緊密排列的書架，所有元素在內(nèi)存中依次緊密相連。這使得它在隨機(jī)訪問時(shí)性能卓越，通過索引直接定位元素就如同在書架上按編號(hào)取書一樣迅速，時(shí)間復(fù)雜度為 O (1)。vector 在尾端插入和刪除元素時(shí)也有不錯(cuò)的效率，平均時(shí)間復(fù)雜度為 O (1) 。但在中間位置插入或刪除元素時(shí)，vector 就需要移動(dòng)大量元素，效率較低，時(shí)間復(fù)雜度為 O (n)，比如在已經(jīng)擺滿書的書架中間插入一本新書，就需要將后面的書依次挪動(dòng)。
list 則是離散存儲(chǔ)的典型，采用雙向鏈表結(jié)構(gòu)，每個(gè)元素都像一個(gè)獨(dú)立的小房間，通過指針與前后元素相連。這讓 list 在插入和刪除操作上極為靈活，無論在鏈表的任何位置，只需修改指針指向，就能完成元素的插入或刪除，時(shí)間復(fù)雜度為 O (1) 。但由于這種離散的結(jié)構(gòu)，list 的隨機(jī)訪問需要從鏈表頭開始遍歷，就像在一排不相鄰的房間中找特定房間，效率低下，時(shí)間復(fù)雜度為 O (n)。
再看 deque，它結(jié)合了 vector 和 list 的部分優(yōu)點(diǎn)，采用分段連續(xù)內(nèi)存存儲(chǔ)。在雙端操作上，deque 和 list 一樣高效，能在 O (1) 時(shí)間內(nèi)完成插入和刪除 。在隨機(jī)訪問方面，雖然不如 vector 直接，但通過中控?cái)?shù)組和數(shù)學(xué)計(jì)算，也能實(shí)現(xiàn) O (1) 的時(shí)間復(fù)雜度，只是多了一次指針跳轉(zhuǎn)。在中間位置操作時(shí)，deque 的效率與 vector 類似，時(shí)間復(fù)雜度為 O (n) 。
具體選擇哪種容器，需要根據(jù)實(shí)際需求來判斷。如果你的場景需要頻繁進(jìn)行雙端操作，比如實(shí)現(xiàn)任務(wù)隊(duì)列、滑動(dòng)窗口等，且偶爾有隨機(jī)訪問的需求，那么 deque 是首選 。像在實(shí)現(xiàn)一個(gè)實(shí)時(shí)數(shù)據(jù)處理系統(tǒng)的任務(wù)隊(duì)列時(shí)，任務(wù)不斷從隊(duì)頭取出、從隊(duì)尾插入，同時(shí)可能需要偶爾查看隊(duì)列中間某個(gè)任務(wù)的狀態(tài)，deque 就能很好地勝任。但如果追求極致的隨機(jī)訪問性能，比如實(shí)現(xiàn)一個(gè)頻繁讀取數(shù)據(jù)的數(shù)組型數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，vector 無疑是更好的選擇 。而當(dāng)需要在容器中間頻繁進(jìn)行插入和刪除操作時(shí)，list 則更勝一籌，比如在實(shí)現(xiàn)一個(gè)頻繁修改節(jié)點(diǎn)的雙向鏈表結(jié)構(gòu)時(shí)，list 的優(yōu)勢(shì)就會(huì)充分體現(xiàn)出來 。
下面我將通過 C++ 代碼對(duì)比 deque 與 vector、list 的核心性能差異，并分析何時(shí)選擇 deque 作為最佳容器：
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <chrono>
#include <iomanip>
#include <random>
// 計(jì)時(shí)工具函數(shù)
template <typename Func>
double measure_time(Func func) {
auto start = std::chrono::high_resolution_clock::now();
func();
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration<double>(end - start).count();
}
// 1. 雙端操作性能測試（頭插、尾插、頭刪、尾刪）
void test_double_ended_operations(size_t operations) {
std::cout << "\n=== 雙端操作性能測試（" << operations << "次操作） ===" << std::endl;
// deque測試
std::deque<int> dq;
double dq_time = measure_time([&]() {
for (size_t i = 0; i < operations; ++i) {
if (i % 2 == 0) {
dq.push_back(i); // 尾插
} else {
dq.push_front(i); // 頭插
}
}
for (size_t i = 0; i < operations / 2; ++i) {
dq.pop_back(); // 尾刪
dq.pop_front(); // 頭刪
}
});
// vector測試（頭插效率低）
std::vector<int> vec;
double vec_time = measure_time([&]() {
for (size_t i = 0; i < operations; ++i) {
if (i % 2 == 0) {
vec.push_back(i); // 尾插
} else {
vec.insert(vec.begin(), i); // 頭插（低效）
}
}
for (size_t i = 0; i < operations / 2; ++i) {
vec.pop_back(); // 尾刪
vec.erase(vec.begin());// 頭刪（低效）
}
});
// list測試
std::list<int> lst;
double lst_time = measure_time([&]() {
for (size_t i = 0; i < operations; ++i) {
if (i % 2 == 0) {
lst.push_back(i); // 尾插
} else {
lst.push_front(i); // 頭插
}
}
for (size_t i = 0; i < operations / 2; ++i) {
lst.pop_back(); // 尾刪
lst.pop_front(); // 頭刪
}
});
std::cout << std::fixed << std::setprecision(6);
std::cout << "deque: " << dq_time << "秒\n";
std::cout << "vector: " << vec_time << "秒\n";
std::cout << "list: " << lst_time << "秒\n";
std::cout << "vector比deque慢 " << vec_time / dq_time << "倍\n";
std::cout << "list比deque慢 " << lst_time / dq_time << "倍\n";
}
// 2. 隨機(jī)訪問性能測試
void test_random_access(size_t size) {
std::cout << "\n=== 隨機(jī)訪問性能測試（" << size << "個(gè)元素） ===" << std::endl;
// 準(zhǔn)備數(shù)據(jù)
std::vector<int> data(size);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<size_t> dist(0, size - 1);
// 初始化容器
std::deque<int> dq(data.begin(), data.end());
std::vector<int> vec(data.begin(), data.end());
std::list<int> lst(data.begin(), data.end());
auto lst_it = lst.begin(); // list需要迭代器訪問
// deque隨機(jī)訪問
double dq_time = measure_time([&]() {
for (size_t i = 0; i < size; ++i) {
size_t idx = dist(gen);
volatile int val = dq[idx]; // volatile防止編譯器優(yōu)化
}
});
// vector隨機(jī)訪問
double vec_time = measure_time([&]() {
for (size_t i = 0; i < size; ++i) {
size_t idx = dist(gen);
volatile int val = vec[idx];
}
});
// list隨機(jī)訪問（需要遍歷，效率極低）
double lst_time = measure_time([&]() {
for (size_t i = 0; i < size; ++i) {
size_t idx = dist(gen);
// list需從頭遍歷到目標(biāo)位置
auto it = lst.begin();
std::advance(it, idx);
volatile int val = *it;
}
});
std::cout << std::fixed << std::setprecision(6);
std::cout << "deque: " << dq_time << "秒\n";
std::cout << "vector: " << vec_time << "秒\n";
std::cout << "list: " << lst_time << "秒\n";
std::cout << "deque比vector慢 " << dq_time / vec_time << "倍\n";
std::cout << "list比deque慢 " << lst_time / dq_time << "倍\n";
}
// 3. 中間插入刪除性能測試
void test_middle_operations(size_t size) {
std::cout << "\n=== 中間插入刪除測試（" << size << "次操作） ===" << std::endl;
// 初始化容器（預(yù)先填充數(shù)據(jù)）
std::deque<int> dq(size / 2);
std::vector<int> vec(size / 2);
std::list<int> lst(size / 2);
// deque中間操作
double dq_time = measure_time([&]() {
auto mid = dq.begin() + dq.size() / 2;
for (size_t i = 0; i < size; ++i) {
mid = dq.insert(mid, i); // 中間插入
if (i % 3 == 0) {
mid = dq.erase(mid); // 中間刪除
}
}
});
// vector中間操作
double vec_time = measure_time([&]() {
auto mid = vec.begin() + vec.size() / 2;
for (size_t i = 0; i < size; ++i) {
mid = vec.insert(mid, i); // 中間插入
if (i % 3 == 0) {
mid = vec.erase(mid); // 中間刪除
}
}
});
// list中間操作
double lst_time = measure_time([&]() {
auto mid = lst.begin();
std::advance(mid, lst.size() / 2);
for (size_t i = 0; i < size; ++i) {
mid = lst.insert(mid, i); // 中間插入
if (i % 3 == 0) {
mid = lst.erase(mid); // 中間刪除
}
}
});
std::cout << std::fixed << std::setprecision(6);
std::cout << "deque: " << dq_time << "秒\n";
std::cout << "vector: " << vec_time << "秒\n";
std::cout << "list: " << lst_time << "秒\n";
std::cout << "deque比list慢 " << dq_time / lst_time << "倍\n";
std::cout << "vector比deque慢 " << vec_time / dq_time << "倍\n";
}
// 4. 內(nèi)存使用對(duì)比
void test_memory_usage(size_t size) {
std::cout << "\n=== 內(nèi)存使用對(duì)比（" << size << "個(gè)元素） ===" << std::endl;
std::deque<int> dq(size);
std::vector<int> vec(size);
std::list<int> lst(size, 0); // list每個(gè)節(jié)點(diǎn)有額外指針開銷
// 估算內(nèi)存使用（簡化計(jì)算）
size_t dq_memory = dq.size() * sizeof(int) +
dq.max_size() / sizeof(int) * sizeof(void*); // 中控?cái)?shù)組開銷
size_t vec_memory = vec.capacity() * sizeof(int); // vector預(yù)分配內(nèi)存
size_t lst_memory = lst.size() * (sizeof(int) + 2 * sizeof(void*)); // 節(jié)點(diǎn)+前后指針
std::cout << "deque: ~" << dq_memory / 1024 << " KB\n";
std::cout << "vector: ~" << vec_memory / 1024 << " KB\n";
std::cout << "list: ~" << lst_memory / 1024 << " KB\n";
}
int main() {
const size_t ops = 100000; // 操作次數(shù)
const size_t size = 50000; // 數(shù)據(jù)規(guī)模
test_double_ended_operations(ops);
test_random_access(size);
test_middle_operations(ops / 10); // 中間操作次數(shù)減少，避免過慢
test_memory_usage(size);
return 0;
}4.2何時(shí)選擇 deque？
根據(jù)測試結(jié)果，deque 的最佳適用場景為：
- 需要頻繁雙端操作（如隊(duì)列、棧的混合使用，首尾均有插入刪除）。
- 需要隨機(jī)訪問（如按索引獲取元素），但又不想承受 vector 頭操作的低效。
- 內(nèi)存敏感場景（避免 vector 預(yù)分配導(dǎo)致的內(nèi)存浪費(fèi)）。
- 數(shù)據(jù)規(guī)模不確定（無需提前預(yù)估容量，動(dòng)態(tài)擴(kuò)展更靈活）。
典型案例：
- 實(shí)現(xiàn)雙端隊(duì)列（如任務(wù)調(diào)度隊(duì)列，支持高優(yōu)先級(jí)任務(wù)頭插、普通任務(wù)尾插）。
- 滑動(dòng)窗口算法（需頻繁在兩端增刪，同時(shí)隨機(jī)訪問窗口內(nèi)元素）。
- 緩存系統(tǒng)（需高效更新首尾元素，同時(shí)支持隨機(jī)訪問緩存項(xiàng)）。
若場景以中間操作為主（如頻繁插入刪除元素），選擇 list；若以尾部操作和隨機(jī)訪問為主，選擇 vector。
五、實(shí)戰(zhàn)場景：deque 的典型應(yīng)用范式
5.1 滑動(dòng)窗口最大值：deque 的經(jīng)典算法場景
在求解滑動(dòng)窗口最大值這類經(jīng)典算法問題時(shí)，deque 有著獨(dú)特的應(yīng)用優(yōu)勢(shì)。以給定數(shù)組[1, 3, -1, -3, 5, 3, 6, 7]，窗口大小k = 3為例，我們需要在每次窗口滑動(dòng)時(shí)，快速找出窗口內(nèi)的最大值 。
這里，我們通過維護(hù)一個(gè)單調(diào)遞減隊(duì)列來實(shí)現(xiàn)。當(dāng)窗口滑動(dòng)時(shí)，首先要移除過期元素，即隊(duì)頭元素的索引超出當(dāng)前窗口范圍時(shí)，將其從隊(duì)頭移除 。這就好比在一個(gè)不斷前進(jìn)的隊(duì)伍中，已經(jīng)走出隊(duì)伍范圍的成員需要被剔除。接著，要移除小于當(dāng)前元素的所有隊(duì)尾元素，因?yàn)檫@些較小的元素在后續(xù)窗口中不可能成為最大值 。比如新加入的成員實(shí)力更強(qiáng)，那么原本隊(duì)伍中實(shí)力不如他的成員就不再有成為最強(qiáng)者的可能。最后，將當(dāng)前元素的索引插入隊(duì)列。通過這樣的操作，隊(duì)頭元素始終是當(dāng)前窗口內(nèi)的最大值 。在整個(gè)數(shù)組遍歷過程中，每次窗口形成（即遍歷到第k - 1個(gè)元素及之后），就將隊(duì)頭元素對(duì)應(yīng)的數(shù)組值加入結(jié)果數(shù)組 。
這種實(shí)現(xiàn)方式的時(shí)間復(fù)雜度為 O (n)，與暴力解法每次窗口滑動(dòng)都需要遍歷窗口內(nèi)所有元素，時(shí)間復(fù)雜度為 O (n * k) 相比，效率得到了顯著提升 。在實(shí)際的算法競賽或數(shù)據(jù)處理任務(wù)中，如果遇到需要在滑動(dòng)窗口內(nèi)快速獲取最值的場景，使用 deque 維護(hù)單調(diào)隊(duì)列是一種非常高效的解決方案，能夠大大提高程序的運(yùn)行效率，減少計(jì)算資源的浪費(fèi) 。
5.2 容器適配器：stack/queue 的底層選擇
在 C++ 標(biāo)準(zhǔn)庫中，stack（棧）和 queue（隊(duì)列）這兩種容器適配器默認(rèn)以 deque 為底層容器 。這是因?yàn)?stack 和 queue 的操作特性決定了它們僅需雙端操作即可滿足需求。
對(duì)于 stack，它遵循后進(jìn)先出（LIFO）的原則，通過使用 deque 的 push_back 操作在棧頂插入元素，pop_back 操作從棧頂刪除元素，就能輕松實(shí)現(xiàn)后進(jìn)先出的特性 。例如，在一個(gè)函數(shù)調(diào)用棧中，每次函數(shù)調(diào)用就像往棧中壓入一個(gè)元素（使用 push_back），函數(shù)返回時(shí)就像從棧中彈出一個(gè)元素（使用 pop_back） 。
queue 則遵循先進(jìn)先出（FIFO）的原則，利用 deque 的 push_back 操作在隊(duì)尾插入元素，pop_front 操作從隊(duì)頭刪除元素，完美契合先進(jìn)先出的邏輯 。比如在一個(gè)打印任務(wù)隊(duì)列中，新的打印任務(wù)從隊(duì)尾加入（使用 push_back），而打印機(jī)每次從隊(duì)頭取出任務(wù)進(jìn)行打?。ㄊ褂?pop_front） 。
這種設(shè)計(jì)充分利用了 deque 雙端高效操作的特性，同時(shí)避免了 vector 在頭部插入元素時(shí)需要移動(dòng)大量元素的低效問題，以及 list 隨機(jī)訪問性能差的不足 。在實(shí)際開發(fā)中，如果需要使用 stack 或 queue，直接使用 C++ 標(biāo)準(zhǔn)庫中基于 deque 實(shí)現(xiàn)的版本，既能保證代碼的簡潔性，又能獲得高效的性能 。
5.3 固定大小緩沖區(qū)：自動(dòng)淘汰舊數(shù)據(jù)
在一些需要固定大小緩沖區(qū)的場景中，比如日志緩存、實(shí)時(shí)數(shù)據(jù)窗口等，deque 可以通過設(shè)置最大容量來實(shí)現(xiàn)自動(dòng)淘汰舊數(shù)據(jù)的功能 。
假設(shè)我們創(chuàng)建一個(gè)最大容量為N的deque，當(dāng)不斷向其中新增元素時(shí)，如果元素?cái)?shù)量超過了N，deque 會(huì)自動(dòng)從另一端刪除舊元素 。就像一個(gè)固定大小的書架，當(dāng)新書不斷放入，書架滿了之后，就需要把最舊的書移除，以騰出空間放置新書 。
在日志緩存場景中，我們可能只需要保留最近的N條日志信息，當(dāng)新的日志產(chǎn)生時(shí)，直接添加到 deque 中，如果超過了最大容量，deque 會(huì)自動(dòng)刪除最早的日志 。這樣可以確保緩存中始終保留最新的有效數(shù)據(jù)，同時(shí)避免了緩存無限增長導(dǎo)致的內(nèi)存溢出問題 。在實(shí)時(shí)數(shù)據(jù)窗口場景中，比如統(tǒng)計(jì)最近 10 秒內(nèi)的用戶行為數(shù)據(jù)，將每個(gè)時(shí)間點(diǎn)的用戶行為數(shù)據(jù)作為元素添加到 deque 中，通過設(shè)置 deque 的最大容量，就可以自動(dòng)維護(hù)一個(gè)固定時(shí)間窗口內(nèi)的數(shù)據(jù)，方便進(jìn)行實(shí)時(shí)數(shù)據(jù)分析和處理 。
六、避坑指南：使用 deque 的三個(gè)注意事項(xiàng)
在使用 deque 時(shí)，有幾個(gè)容易踩坑的地方需要特別注意，以確保程序的正確性和穩(wěn)定性。
6.1 迭代器失效問題：任何插入 / 刪除操作都會(huì)導(dǎo)致迭代器失效，不同于 vector 僅在擴(kuò)容時(shí)失效，需避免保存中間迭代器。
在使用 deque 時(shí)，迭代器失效是一個(gè)需要特別注意的問題。不同于 vector 僅在擴(kuò)容時(shí)才會(huì)導(dǎo)致迭代器失效，deque 的任何插入或刪除操作，無論在雙端還是中間位置，都會(huì)使所有迭代器失效 。這是因?yàn)?deque 的分段存儲(chǔ)結(jié)構(gòu)，插入或刪除元素可能會(huì)導(dǎo)致緩沖區(qū)的調(diào)整以及中控?cái)?shù)組的變化，從而使迭代器指向的位置不再有效。
比如，在遍歷deque的過程中，如果進(jìn)行插入或刪除操作，就會(huì)導(dǎo)致迭代器失效，進(jìn)而引發(fā)未定義行為 。在實(shí)際開發(fā)中，我們應(yīng)盡量避免在遍歷deque時(shí)進(jìn)行插入或刪除操作。如果確實(shí)需要在遍歷過程中修改deque，可以考慮使用其他數(shù)據(jù)結(jié)構(gòu)，或者先將需要插入或刪除的元素記錄下來，在遍歷結(jié)束后再統(tǒng)一進(jìn)行操作 。
6.2 C 風(fēng)格 API 兼容：因內(nèi)存非連續(xù)，&deque [0] 無法獲取完整數(shù)組地址，避免用于 memcpy 等需要連續(xù)內(nèi)存的操作。
由于 deque 的內(nèi)存并非連續(xù)存儲(chǔ)，不能簡單地通過&deque[0]來獲取整個(gè)數(shù)組的地址 。這是因?yàn)?amp;deque[0]僅僅返回第一個(gè)緩沖區(qū)的起始地址，而不是整個(gè) deque 的內(nèi)存起始地址。在使用 C 風(fēng)格 API 時(shí)，像memcpy這類需要連續(xù)內(nèi)存的操作，如果直接使用&deque[0]，就會(huì)導(dǎo)致未定義行為，因?yàn)樗鼰o法涵蓋 deque 中所有分段存儲(chǔ)的元素 。
在實(shí)際應(yīng)用中，如果需要將 deque 的數(shù)據(jù)傳遞給 C 風(fēng)格 API，應(yīng)先將 deque 的數(shù)據(jù)復(fù)制到一個(gè)連續(xù)的數(shù)組中，然后再進(jìn)行操作 。比如，可以使用std::vector作為中間容器，將 deque 的數(shù)據(jù)復(fù)制到 vector 中，再利用&vector[0]獲取連續(xù)內(nèi)存地址傳遞給 C 風(fēng)格 API，以確保操作的正確性 。
6.3 調(diào)試工具適配：部分 IDE 調(diào)試時(shí)無法完整顯示分段存儲(chǔ)的所有元素，需通過遍歷或轉(zhuǎn)換為列表查看。
在使用部分 IDE 進(jìn)行調(diào)試時(shí)，由于 deque 的分段存儲(chǔ)結(jié)構(gòu)，可能無法完整顯示所有元素 。調(diào)試工具可能只能顯示第一個(gè)緩沖區(qū)的內(nèi)容，而忽略了其他緩沖區(qū)的元素，這會(huì)給調(diào)試工作帶來困擾。
為了在調(diào)試時(shí)查看 deque 的所有元素，可以通過手動(dòng)遍歷 deque 來打印每個(gè)元素的值 。也可以將 deque 轉(zhuǎn)換為std::list或std::vector，因?yàn)檫@兩種容器在調(diào)試時(shí)更容易完整顯示所有元素 。比如，將 deque 的元素逐個(gè)插入到std::list中，然后在調(diào)試時(shí)查看std::list的內(nèi)容，這樣就能確?？吹?deque 中的所有元素，方便進(jìn)行調(diào)試和排查問題。
