什麼是 deque？
deque（Double-Ended Queue）是雙端佇列，支援常數時間在頭尾兩端插入/刪除元素，結合 vector 的隨機存取與 list 的頭尾操作優勢。底層通常以分段連續記憶體實現。
建構與初始化
#include <deque>
using namespace std;
deque<int> d1; // 空佇列
deque<int> d2(d1); // 複製建構
deque<int> d3(10); // 10 個 0
deque<int> d4(10, 5); // 10 個 5
deque<int> d5{1,2,3,4,5}; // C++11 列表初始化
核心操作完整對照表
元素存取
| 函數 | 說明 | 邊界檢查 |
|---|
front() | 首元素參考 | 無（空容器未定義） |
back() | 尾元素參考 | 無 |
at(i) | 第 i 元素 | 有（拋出 out_of_range） |
operator[] | 第 i 元素 | 無 |
頭尾插入/刪除（O(1)）
d.push_back(10); // 尾部插入
d.push_front(5); // 頭部插入
d.pop_back(); // 尾部刪除
d.pop_front(); // 頭部刪除
中間插入/刪除（O(n)）
auto it = d.begin() + 2; // 隨機存取迭代器
d.insert(it, 99); // 指定位置插入
d.erase(it); // 指定位置刪除
d.erase(d.begin(), d.begin()+2); // 區間刪除
容量與狀態
| 函數 | 說明 |
|---|
size() | 當前元素數 |
max_size() | 最大可能元素數 |
empty() | 是否為空 |
clear() | 清空所有元素 |
shrink_to_fit() | 釋放多餘容量（C++11） |
交換與排序
deque<int> other{10,20,30};
d.swap(other); // 常數時間交換內容
sort(d.begin(), d.end()); // 需包含 <algorithm>
迭代器遍歷
// 正向
for (auto it = d.begin(); it != d.end(); ++it) cout << *it << ' ';
// 反向
for (auto it = d.rbegin(); it != d.rend(); ++it) cout << *it << ' ';
// 範圍 for (C++11)
for (const auto& val : d) cout << val << ' ';
完整示範程式
#include <deque>
#include <iostream>
using namespace std;
void print(const deque<int>& d) {
for (int v : d) cout << v << ' ';
cout << endl;
}
int main() {
deque<int> d;
d.push_back(1); d.push_back(2); d.push_back(3); d.push_back(4);
cout << "尾插後："; print(d); // 1 2 3 4
d.push_front(5); d.push_front(6);
cout << "頭插後："; print(d); // 6 5 1 2 3 4
cout << "front=" << d.front() << " back=" << d.back() << endl;
auto it = d.begin() + 2;
d.insert(it, 99);
cout << "插入99："; print(d); // 6 5 99 1 2 3 4
d.erase(d.begin() + 2);
cout << "刪除99："; print(d); // 6 5 1 2 3 4
d.pop_back(); d.pop_front();
cout << "頭尾各刪一："; print(d); // 5 1 2 3
deque<int> d2{11,22,33};
d.swap(d2);
cout << "交換後 d："; print(d); // 11 22 33
cout << "交換後 d2："; print(d2); // 5 1 2 3
cout << "size=" << d.size() << " empty=" << d.empty() << endl;
d.clear();
cout << "clear後 empty=" << d.empty() << endl;
return 0;
}
deque vs vector vs list 選型指南
| 容器 | 隨機存取 | 頭部插刪 | 尾部插刪 | 中間插刪 | 記憶體連續 | 適用場景 |
|---|
| vector | O(1) | O(n) | O(1) 均攤 | O(n) | 是 | 預設首選、需連續記憶體 |
| deque | O(1) | O(1) | O(1) | O(n) | 分段連續 | 雙端操作頻繁、需隨機存取 |
| list | O(n) | O(1) | O(1) | O(1) 已知位置 | 否 | 大量中間插刪、無隨機存取需求 |
效能與注意事項
- 迭代器失效：中間插刪會失效所有迭代器；頭尾插刪僅失效相關迭代器（C++11 保證頭尾插入不失效迭代器）。
- 記憶體碎片：分段配置可能比
vector 稍大，但避免大塊連續記憶體分配失敗。
- 布林特化：
deque<bool> 是位元級壓縮特化，操作較慢，非必要勿用。
