本篇將介紹如何使用 C++ std deque 以及用法與範例，C++ std::deque 是一個雙向佇列(double-ended queue)，在頭尾兩端插入及刪除十分快速，在中間插入刪除元素比較費時。
std::deque 是 double-ended queue 而不是 double linked list，底層實做是用間接索引的方式實現的，類似一個 map 索引到若干個固定大小的資料區塊(連續記憶體空間)，利用兩次索引達成跟 vector 一樣的隨機訪問功能。
以下將依序介紹幾個 std::deque 容器常用的用法範例，分別為
- deque 常用功能
- 範例1. 基本的 push_back, pop_front, push_front, pop_back 的用法範例
- 範例2. push_back 自定義類別
- 範例3. 用 for 迴圈遍歷 deque 容器
- 範例4. 用 while 迴圈在 deque 容器裡搜尋/尋找
- deque 的優點與缺點
要使用 deque 容器的話，需要引入的標頭檔：<deque>
deque 常用功能
以下為 std::deque 內常用的成員函式，
修改器push_back：把一個元素添加到尾端push_front：把一個元素插入到頭端pop_back：移除最後一個元素(尾端)pop_front：移除第一個元素(頭端)insert：插入元素erase：移除某個位置元素, 也可以移除某一段範圍的元素clear：清空容器裡所有元素
容量empty：回傳是否為空size：回傳目前長度
元素存取[i]：隨機存取索引值為i的元素back：取得最後一個元素front：取得第一個的元素
迭代器begin：回傳指向第一個元素(頭端)的迭代器cbegin：回傳指向第一個元素(頭端)的迭代器(const)end：回傳指向最後一個元素(尾端)的迭代器cend：回傳指向最後一個元素(尾端)的迭代器(const)rbegin：回傳指向最後一個元素(尾端)的反向迭代器crbegin：回傳指向最後一個元素(尾端)的反向迭代器(const)rend：回傳指向第一個元素(頭端)的反向迭代器crend：回傳指向第一個元素(頭端)的反向迭代器(const)
範例1. 基本的 push_back, pop_front, push_front, pop_back 的用法範例
以下範例為push_back(), pop_front(), push_front(), pop_back() 用法，
其中 push_back() 與 pop_front() 應該是最常用到的函式了。
另外使用 deque 相對於 queue 的好處是deque可以使用隨機訪問的功能 [i]。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24// g++ std-deque.cpp -o a.out -std=c++11
using namespace std;
int main() {
deque<int> d = {1, 2, 3, 4}; // [1, 2, 3, 4]
d.push_back(5); // [1, 2, 3, 4, 5]
d.pop_front(); // [2, 3, 4, 5]
d.push_front(0); // [0, 2, 3, 4, 5]
d.pop_back(); // [0, 2, 3, 4]
// 印出 deque 內所有內容, c++11 才支援
for (int &i : d) {
cout << i << " ";
}
cout << "\n";
cout << d[0] << " " << d[1] << " " << d[2] << "\n";
return 0;
}
輸出內容如下：1
20 2 3 4
0 2 3
範例2. push_back 自定義類別
以下範例為 std::deque 容器使用 push_back() 來推放 Student 自定義類別的範例，使用 push_back() 來放進 deque 的最尾端，這個範例限制 deque 最多塞3個，多的會用 pop_front() 給 pop 掉，最後再將 deque 容器的所有的元素印出來。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37// g++ std-deque2.cpp -o a.out -std=c++11
using namespace std;
class Student {
public:
Student(int id) { this->id = id; }
int id;
};
std::deque<Student> d;
void deque_push_back(Student a) {
d.push_back(a);
if (d.size() > 3) {
d.pop_front();
}
}
int main() {
Student a1(1), a2(2), a3(3), a4(4);
deque_push_back(a1);
deque_push_back(a2);
deque_push_back(a3);
deque_push_back(a4);
// 印出 deque 內所有內容, c++11 才支援
for (auto &i : d) {
cout << i.id << " ";
}
cout << "\n";
return 0;
}
範例3. 用 for 迴圈遍歷 deque 容器
以下範例是用 for 迴圈配合 deque 容器的迭代器，去遍歷 deque 並且把值印出來，前兩種是從頭印到尾，後兩種是從尾印到頭。從頭端印到最尾端就是使用 begin() 搭配 end() ，從最尾端印到頭端就是使用 rbegin() 搭配 rend() 。
這裡的 begin() / end() 與 cbegin() / cend() 有什麼不同呢？begin() / end() 是回傳 iterator，而 cbegin() / cend() 是回傳 const_iterator，iterator 可以修改元素值，const_iterator 則不可修改，簡單說就是回傳的東西能不能被修改的差異，要用哪種就自行判斷要用哪種了。
cbegin(), cend(), crbegin(), crend() 是 C++11 新增的，要使用時記得編譯器要加入-std=c++11選項。
第一個 for 迴圈裡面的迭代器使用懶人快速寫法auto it = d.begin();，其全名為std::deque<int>::iterator it = d.begin();，如果不想寫這麼長的話，就可以像我一樣用 auto 的懶人快速寫法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36// g++ std-deque3.cpp -o a.out -std=c++11
using namespace std;
int main() {
deque<int> d = {1, 2, 3, 4};
// 從頭到尾
//for (std::deque<int>::iterator it = d.begin(); it != d.end(); ++it) {
for (auto it = d.begin(); it != d.end(); ++it) {
cout << *it << " ";
}
cout << "\n";
// 從頭到尾
for (auto it = d.cbegin(); it != d.cend(); ++it) {
cout << *it << " ";
}
cout << "\n";
// 從尾到頭
for (auto it = d.rbegin(); it != d.rend(); ++it) {
cout << *it << " ";
}
cout << "\n";
// 從尾到頭
for (auto it = d.crbegin(); it != d.crend(); ++it) {
cout << *it << " ";
}
cout << "\n";
return 0;
}
輸出1
2
3
41 2 3 4
1 2 3 4
4 3 2 1
4 3 2 1
範例4. 用 while 迴圈在 deque 容器裡搜尋/尋找
以下範例是用 while 迴圈在 deque 容器裡搜尋/尋找數字為3，這裡的 auto 懶人快速寫法如上範例解釋相同就不贅述了。
在 while 迴圈裡如果有找到就印個有找到的訊息，假如整個 while 迴圈都沒找到，最後可以判斷 it == d.end() 代表整個 deque 容器都遍歷過了也沒有找到，就印個沒找到的訊息。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26// g++ std-deque4.cpp -o a.out -std=c++11
using namespace std;
int main() {
deque<int> d = {1, 2, 3, 4};
// 從頭到尾
int find_num = 3;
//std::deque<int>::iterator it = d.begin();
auto it = d.begin();
while (it != d.end()) {
if (*it == find_num) {
cout << "Found " << find_num << endl;
break;
}
it++;
}
if (it == d.end()) {
cout << "Not found " << find_num << endl;
}
return 0;
}
輸出1
Found 3
如果將 find_num 變數改成 5 去搜尋/尋找的話則會找不到，輸出結果會變成1
Not found 5
deque 的優點與缺點
deque 的優點
- 可以再兩端進行 push 和 pop 操作
- 支持隨機訪問[i]
deque 的缺點
- 佔用記憶體較多
補充資料
[ptt] deque的實作內部結構示意圖
[ptt] 在特定條件下，deque與vector的效能比較
[csdn] STL中list,vector,deque,map,set區別、聯繫和使用場景原理
參考
std::deque - cppreference.com
https://en.cppreference.com/w/cpp/container/deque
deque - C++ Reference
http://www.cplusplus.com/reference/deque/deque/
Deque in C++ Standard Template Library (STL) - GeeksforGeeks
https://www.geeksforgeeks.org/deque-cpp-stl/
其它相關文章推薦
如果你想學習 C++ 相關技術，可以參考看看下面的文章，
C/C++ 新手入門教學懶人包
std::queue 用法與範例
std::stack 用法與範例
std::vector 用法與範例
std::set 用法與範例
std::map 用法與範例
std::unordered_map 用法與範例
std::find 用法與範例
std::thread 用法與範例
std::async 用法與範例
C++ 計算程式執行時間
