C++中std::deque詳解和實戰工程代碼示例

std::deque（雙端隊列）是 C++ 標準庫中的一個序列容器，與 std::vector 類似，但它支持從頭部和尾部高效地插入和刪除元素。它底層采用分段連續空間實現，兼具靈活性與性能。

---

一、基本特性

特性	描述
隨機訪問	支持下標訪問（operator[]、at()）
快速頭尾操作	push_front 和 push_back 效率高，優于 vector 的頭部插入
分段存儲結構	非一塊連續內存，適合頻繁的插入刪除場景
迭代器失效規則	插入刪除可能導致部分迭代器失效，需小心

---

二、使用注意事項（易錯點）

1. 與 vector 的差異

• std::deque 并不保證所有元素在一塊連續內存中存儲，不能通過 &deque[0] 獲取整個數組地址。
• 不適合與 C 風格 API 一起使用（比如 memcpy(&deque[0], ...) 可能導致未定義行為）。

2. 迭代器失效

• 插入或刪除任意位置的元素都會使所有迭代器失效，不同于 vector 只在 reallocation 時失效。

std::deque<int> dq = {1, 2, 3, 4};
auto it = dq.begin();
dq.push_front(0); // it 現在已失效！

3. 頻繁中間插入性能低

• 插入/刪除位于中間位置的元素效率低，需移動大量元素。
• 如需頻繁中間插入，建議使用 std::list。

4. 容量管理

• 沒有 capacity() 函數（不像 vector），不能預留空間，使用方式略有不同。

5. 對象構造開銷

• 每次插入都可能涉及對象構造和移動，注意對象拷貝開銷。

---

三、常用操作代碼示例

示例 1：基本使用

#include <iostream>
#include <deque>int main() {std::deque<int> dq;dq.push_back(1);   // 尾部插入dq.push_front(0);  // 頭部插入dq.push_back(2);for (int val : dq)std::cout << val << " ";  // 輸出：0 1 2dq.pop_front();  // 刪除頭部dq.pop_back();   // 刪除尾部std::cout << "\nFront: " << dq.front();  // 輸出：1std::cout << "\nBack: " << dq.back();    // 輸出：1
}

示例 2：模擬滑動窗口（典型應用）

#include <deque>
#include <vector>
#include <iostream>std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {std::deque<int> dq;  // 存索引std::vector<int> result;for (int i = 0; i < nums.size(); ++i) {while (!dq.empty() && dq.front() <= i - k)dq.pop_front();  // 移除滑出窗口的元素while (!dq.empty() && nums[dq.back()] < nums[i])dq.pop_back();   // 保持單調性dq.push_back(i);if (i >= k - 1)result.push_back(nums[dq.front()]);}return result;
}

---

四、實際應用場景

場景	使用原因
滑動窗口算法	快速刪除/插入頭尾元素
限長隊列（日志、緩存）	自動彈出舊元素，控制內存
多線程任務隊列（需加鎖）	支持雙端插入，配合 mutex 使用
狀態機緩沖器	記錄有限長度狀態序列

---

五、工程應用實戰

下面是兩個典型 std::deque 實戰場景的完整示例代碼，適合用于滑動窗口最大值算法和限長隊列（比如日志或緩存）實現。

示例一：滑動窗口最大值（單調隊列優化）

用于處理如：[1,3,-1,-3,5,3,6,7]，滑動窗口大小 k=3 時，每個窗口內的最大值。

功能說明：

• 保持一個單調遞減隊列（deque中存下標）。
• 窗口滑動時移除已滑出的元素。
• 每次窗口滿了就將最大值加入結果。

示例代碼：

#include <iostream>
#include <vector>
#include <deque>std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {std::deque<int> dq;std::vector<int> result;for (int i = 0; i < nums.size(); ++i) {// 移除滑出窗口的元素if (!dq.empty() && dq.front() <= i - k)dq.pop_front();// 保持隊列單調遞減（移除小于當前值的）while (!dq.empty() && nums[dq.back()] < nums[i])dq.pop_back();dq.push_back(i);  // 存下標if (i >= k - 1)result.push_back(nums[dq.front()]);}return result;
}int main() {std::vector<int> nums = {1,3,-1,-3,5,3,6,7};int k = 3;auto result = maxSlidingWindow(nums, k);std::cout << "滑動窗口最大值：";for (int val : result)std::cout << val << " ";  // 輸出：3 3 5 5 6 7std::cout << std::endl;
}

---

示例二：限長隊列（固定大小緩存或日志）

模擬一個最大容量為 N 的隊列，插入新元素時若超過容量，自動從頭部彈出舊元素。

功能說明：

• 封裝成 LimitedQueue<T> 模板類
• 支持 push()，pop()，size()，front()，back() 等基本操作

示例代碼：

#include <iostream>
#include <deque>template <typename T>
class LimitedQueue {
public:LimitedQueue(size_t capacity) : max_size(capacity) {}void push(const T& value) {if (dq.size() >= max_size)dq.pop_front();  // 超出容量，彈出舊元素dq.push_back(value);}void print() const {for (const auto& item : dq)std::cout << item << " ";std::cout << "\n";}size_t size() const { return dq.size(); }private:std::deque<T> dq;size_t max_size;
};int main() {LimitedQueue<int> q(5);  // 最多保存 5 個元素for (int i = 1; i <= 10; ++i) {q.push(i);std::cout << "插入 " << i << " 后隊列內容：";q.print();}
}

輸出示例：

插入 1 后隊列內容：1 
插入 2 后隊列內容：1 2 
插入 3 后隊列內容：1 2 3 
插入 4 后隊列內容：1 2 3 4 
插入 5 后隊列內容：1 2 3 4 5 
插入 6 后隊列內容：2 3 4 5 6 
插入 7 后隊列內容：3 4 5 6 7 
...

---

六、與其他容器對比

特性	vector	deque	list
隨機訪問	?	?	?
快速尾部插入	?（均攤常數）	?	?
快速頭部插入	?（O(n)）	?	?
中間插入/刪除	?（慢）	?（稍快）	?（快）
內存連續性	?	?（分段）	?

---

七、建議與最佳實踐

• 推薦用于： 需要雙端插入/刪除，且訪問頻率較高的場景。
• 避免： 中間頻繁插入、與 C 接口配合使用。
• 調試時： 注意調試器中 deque 不總能完整顯示所有元素（因為分段結構）。