C++ STL之deque的使用和模擬實現

deque

核心本質與定位

與stack和queue的關系:

deque的使用

deque的底層實現

deque的原理介紹

deque的缺陷

總結:

deque

deque文檔 :?deque

翻譯:

雙端隊列

deque（通常發音類似“deck”）是“double-ended queue”（雙端隊列）的非常規縮寫。雙端隊列是動態大小的序列容器，可在兩端（前端或后端）進行擴展或收縮操作。
具體的庫可能會以不同方式實現 deque，一般是某種形式的動態數組。但無論如何，它們允許通過隨機訪問迭代器直接訪問單個元素，并且容器會根據需要自動擴展或收縮來管理存儲。
因此，它們提供的功能與 vector 類似，但在序列的開頭也能高效地插入和刪除元素，而不僅僅是在末尾。但與 vector 不同的是，deque 不保證所有元素都存儲在連續的內存位置：通過偏移一個元素的指針來訪問 deque 中的其他元素會導致未定義行為。
vector 和 deque 提供的接口非常相似，可用于類似的場景，但在內部工作方式上有很大不同：
vector 使用需要偶爾重新分配的單個數組來實現增長，而 deque 的元素可以分散在不同的存儲塊中，容器在內部保存必要的信息，以常數時間直接訪問任何元素，并通過迭代器提供統一的順序接口。因此，deque 在內部比 vector 更復雜，但這使得它在某些情況下（尤其是超長序列，重新分配開銷更大時）能更高效地增長。
對于需要頻繁在開頭或末尾之外的位置插入或刪除元素的操作，deque 的表現比 list 和 forward_list 更差，且迭代器和引用的一致性也更弱。

在 C++ STL 中，deque（雙端隊列，Double-Ended Queue）是核心的序列式容器之一，設計目標是平衡“兩端高效操作”與“隨機訪問”能力，填補了 vector（尾部高效、頭部低效）和 list（兩端高效、無隨機訪問）的功能空白。雖然它名字里有隊列，但是并不是隊列，并不要求先進先出。

核心本質與定位

基礎容器而非適配器：deque 是直接管理內存和元素的底層容器，與 vector、list 同級，不屬于 stack/queue 這類“封裝底層容器的適配器”，能獨立提供完整的元素操作接口。
功能核心：以 O(1) 時間復雜度實現頭部和尾部的插入/刪除操作，同時支持 O(1) 隨機訪問（像 vector 一樣用 ?[]??下標訪問元素），是兼顧“兩端靈活性”和“訪問效率”的中間選擇。

與stack和queue的關系:

在上篇文章中，在介紹stack和queue時就提到了deque，deque 是 stack 和 queue 的“默認底層實現”，在 C++ 中，stack、queue 與 deque 的核心關系是 “容器適配器”與“默認底層基礎容器”的依賴關系，具體可拆解為兩點：

1. deque 是 stack 和 queue 的“默認底層實現”
stack（棧）和 queue（隊列）本身不存儲元素，必須依賴一個基礎容器來管理數據，而 deque 是 STL 為它們預設的默認底層容器。

當你直接定義 ?stack<int> s;??或 ?queue<int> q;??時，底層實際是用 deque 來存儲元素的，相當于 ?stack<int, deque<int>> s;??和 ?queue<int, deque<int>> q;?。
選擇 deque 作為默認的原因：deque 支持 O(1) 時間復雜度的兩端操作（頭部/尾部插入/刪除），剛好匹配 stack（僅需棧頂，即 deque 尾部操作）和 queue（需隊尾插入、隊首刪除）的功能需求，且比 vector（頭部操作低效）、list（無隨機訪問）更適配。

2. 三者本質不同：適配器 vs 基礎容器

stack/queue：是“容器適配器”，作用是“封裝底層容器的接口”，強制特定的數據訪問規則（stack 先進后出、queue 先進先出），自身不具備元素存儲和內存管理能力。
deque：是“基礎序列容器”，能獨立管理元素存儲和內存，提供完整的元素操作接口（如隨機訪問、兩端/中間操作），是 stack/queue 實現功能的“底層支撐”。

下面我們就來詳細學習deque的主要內容:

deque的使用

deque?、?vector??和 ?list? 均作為 STL 基礎序列容器，在成員函數上的共同點主要有以下幾類：

元素增刪（基礎）：都支持 ?push_back?（尾部添加元素）和 ?pop_back?（尾部刪除元素）操作；也都提供 ?clear??函數用于清空容器內所有元素。
狀態查詢：均包含 ?empty??函數判斷容器是否為空，?size??函數獲取容器內元素的個數。
迭代器遍歷：都提供 ?begin?、?end??用于正向遍歷元素，?rbegin?、?rend??用于反向遍歷元素。
元素訪問（部分）：都支持 ?front??獲取容器頭部元素的引用，?back??獲取容器尾部元素的引用。
賦值與交換：都實現了 ?operator=??用于容器間的賦值操作，也都有 ?swap??函數用于交換兩個同類型容器的元素。

#include<deque>
#include<iostream>
using namespace std;void test_deque()
{deque<int> dp;//尾插dp.push_back(1);dp.push_back(2);dp.push_back(3);dp.push_back(4);//頭插dp.push_front(10);dp.push_front(20);dp.push_front(30);dp.push_front(40);//尾刪dp.pop_back();//頭刪dp.pop_front();//隨機訪問for (size_t i = 0; i < dp.size(); i++){cout << dp[i] <<" ";}cout << endl;
}
int main()
{test_deque();return 0;
}

可以看到它既支持頭插尾插，又支持頭刪尾刪，還支持隨機訪問，它融合了vector和list的優點，從使用的角度，避開了它們各自的缺點：

list的缺點：不支持隨機訪問
vector的缺點：頭部和中間插入刪除效率低

deque的底層實現

deque?、?vector??和 ?list? 均作為 STL 基礎序列容器，它們之間究竟有什么區別呢 ? 首先我們來看一下vector和list的優缺點：

vector

核心特點:

基于連續內存空間存儲，支持隨機訪問（通過下標 ?[]??或 ?at()??直接定位元素）。
元素在內存中緊密排列，尾部增刪效率高，中間/頭部增刪效率低。
容量（capacity）會自動擴容（通常擴容為原容量的1.5-2倍），擴容時需拷貝舊元素到新內存，可能產生性能開銷。

優點:

1.?隨機訪問速度快（時間復雜度 O(1)），適合需要頻繁通過下標讀取元素的場景（如數組遍歷、索引訪問）。
2.?內存緩存利用率高（連續內存易被CPU緩存命中），遍歷元素時速度比 ?list??快。
3.?尾部 ?push_back?/?pop_back??操作高效（O(1)，無內存移動）。
4.?接口簡潔，支持 ?reserve()??預分配容量，避免頻繁擴容，優化性能。

缺點:

1.?中間或頭部插入/刪除元素效率低（O(n)）：需移動插入點后所有元素，內存移動開銷大。
2.?擴容時可能浪費內存（擴容后的容量大于實際元素個數），且拷貝舊元素會產生額外性能消耗。
3.?不適合存儲大量大型對象（擴容時拷貝大型對象開銷高），也不適合頻繁修改中間元素的場景。

list

核心特點:

基于非連續內存空間存儲，元素通過前后指針連接，不支持隨機訪問。
元素在內存中分散存儲，任意位置增刪效率高，訪問元素需從頭/尾遍歷。
無容量概念，元素增刪時直接分配/釋放單個節點內存，無需擴容和拷貝。

優點:

1.?任意位置（頭部、中間、尾部）插入/刪除元素效率高（時間復雜度 O(1)）：只需修改對應節點的指針，無需移動其他元素。
2.?無擴容開銷，內存分配靈活，不會浪費內存（每個元素按需分配節點）。
3.?適合頻繁在中間位置增刪元素的場景（如鏈表結構、頻繁插入的隊列）。

缺點:

1.?不支持隨機訪問（訪問指定元素需遍歷鏈表，時間復雜度 O(n)），無法通過下標快速定位元素。
2.?內存緩存利用率低（非連續內存難被CPU緩存命中），遍歷元素時速度比 ?vector??慢。
3.?每個元素需額外存儲前后指針，內存開銷比 ?vector??大（存儲相同數量元素時，?list??占用更多內存）。
4.?不支持 ?reserve()??預分配內存，也無法通過下標訪問，功能比 ?vector??受限。

結合上面deque的使用，我們可以看出deque既支持頭插尾插，又支持頭刪尾刪，還支持隨機訪問，它融合了vector和list的優點，從使用的角度，避開了它們各自的缺點，如果deque真的像上面說的那么優秀，那么vector和list可能就被淘汰了。

其實，deque還是有缺陷的，它的底層怎么實現的呢？

deque的原理介紹

deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與 list比較，空間利用率比較高。

deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個 動態的二維數組，其底層結構如下圖所示:

這張圖準確展示了 deque（雙端隊列）的底層結構，核心由三部分組成：

中控器（map）：是指針數組，每個指針指向一個緩沖區（buffer）（連續內存塊），用于管理所有分段的內存。
緩沖區（buffer）：多個分段的連續內存塊，實際存儲元素。圖中不同緩沖區的填充狀態體現了元素的分布（如中間緩沖區有部分元素已存儲）。
迭代器（iterator）：

start(iterator)?：標記 deque 的起始范圍，由 ?cur?（當前元素指針）、?first?（起始緩沖區的起始指針）、?last?（起始緩沖區的末尾指針）、?node?（指向中控器對應節點的指針）組成。
finish(iterator)?：標記 deque 的末尾范圍，結構與 ?start??一致，用于界定元素的結束位置。

這種結構的核心優勢是：

雙端操作高效：在起始緩沖區執行 ?push_front?/?pop_front?，在末尾緩沖區執行 ?push_back?/?pop_back?，均只需操作分段內存的兩端，無需整體移動元素。
隨機訪問可行：通過中控器的指針數組快速定位目標元素所在的緩沖區，再結合迭代器的 ?cur??指針偏移，實現 O(1) 時間的隨機訪問。

雙端隊列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”以及隨機訪問 的假象，落在了deque的迭代器身上，因此deque的迭代器設計就比較復雜，如下圖所示：

中控器（map）：一個指針數組，每個指針指向一塊連續的內存區域（稱為“緩沖區 buffer”）。
緩沖區（buffer）：分段的連續內存塊，用于實際存儲元素，解決了 vector 單一連續內存擴容時的拷貝開銷問題。
迭代器（iterator）：通過 ?cur?（當前元素指針）、?first?（緩沖區起始指針）、?last?（緩沖區末尾指針）、?node?（指向中控器對應節點的指針），實現跨分段的元素訪問和迭代。

?那deque是如何借助其迭代器維護其假想連續的結構呢？

這張圖通過可視化的方式，解釋了 deque 執行 ?push_back?（尾插）操作時的內部邏輯：
?
1.?緩沖區與中控器的配合：
deque 底層由多個緩沖區（buffer）（連續內存塊）組成，這些緩沖區的地址由中控器（map，指針數組）管理。圖中可以看到多個緩沖區（如存儲 0-7、8-15、16-19 及后續元素的塊），中控器的指針數組指向這些緩沖區的起始地址。
2.?尾插的執行流程：
當調用 ?push_back(0)?、?push_back(1)?、?push_back(2)??時：
- deque 會找到最末尾的緩沖區（圖中存儲 16-19 及后續元素的塊）。
- 從該緩沖區的空閑位置開始依次插入元素 0、1、2。
- 若當前緩沖區已滿，deque 會自動分配新的緩沖區，并通過中控器的指針數組維護新緩沖區的地址，保證后續尾插操作的連續性。
3.?迭代器的角色：
?finish(iterator)??標記了 deque 的末尾范圍，其內部的 ?cur??指針會隨著尾插操作不斷后移，始終指向“下一個可插入的位置”，從而維護了 deque“假想連續”的邏輯結構——盡管物理內存是分段的，但通過迭代器和中控器的配合，用戶可以感知到元素是連續存儲的。
?
簡言之，這張圖直觀呈現了 deque 如何通過分段緩沖區 + 中控器管理 + 迭代器標記，實現高效的尾插操作，同時維持“邏輯連續”的抽象結構。

deque的缺陷

deque 雖然在雙端操作和隨機訪問之間做了平衡，但也存在以下缺陷：
1. 中間操作效率低
在中間位置（非頭部、非尾部）插入或刪除元素時，需要移動該位置前后的元素，時間復雜度為 O(n)，遠不如 list（中間操作 O(1)）高效。
2. 隨機訪問略遜于 vector
盡管支持隨機訪問，但由于內存是分段存儲的，訪問元素時需要先通過中控器定位到對應的緩沖區，再在緩沖區內偏移訪問，實際速度比 vector（單一連續內存直接訪問）稍慢。
3. 內存結構復雜
底層需要維護“中控器（map）+ 分段緩沖區”的結構，實現邏輯比 vector 和 list 更復雜，這也導致其迭代器的實現和維護成本較高。
4. 迭代器穩定性不足
當在 deque 的頭部或尾部之外的位置進行插入/刪除操作，或者因中控器擴容導致緩沖區地址變化時，迭代器可能會失效，穩定性不如 list（list 僅被刪除節點的迭代器失效）。
5. 不適合大量中間操作場景
如果業務場景中需要頻繁對中間元素進行增刪，deque 的性能表現會明顯不如 list；而如果需要頻繁隨機訪問，又不如 vector 高效，存在一定的使用場景局限性。

與vector比較，deque的優勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴 容時，也不需要搬移大量的元素，因此其效率是必vector高的。

與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。

但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其 是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實 際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看 到的一個應用就是，STL用其作為stack和queue的底層數據結構。

為什么選擇deque作為stack和queue的底層默認容器?

stack是一種后進先出的特殊線性數據結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性數據結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如 list。但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高。結合了deque的優點，而完美的避開了其缺陷。

總結:

摘要：雙端隊列deque是STL中的動態序列容器，支持兩端高效插入/刪除和隨機訪問，填補了vector和list的功能空白。其底層通過"中控器+分段緩沖區"實現，兼具vector的隨機訪問和list的雙端操作優勢，但中間操作效率較低。deque是stack和queue的默認底層容器，因其完美適配二者僅需單端或雙端操作的特點。雖然deque平衡了功能與性能，但在實際應用中仍存在遍歷效率低、中間操作慢等缺陷，通常在需要頻繁隨機訪問時選擇vector，頻繁中間操作時選擇list更為合適。

感謝大家的觀看!