STL——deque 雙向隊列

from：http://blog.csdn.net/morewindows/article/details/6946811

deque雙向隊列是一種雙向開口的連續線性空間，可以高效的在頭尾兩端插入和删除元素，deque在接口上和vector非常相似，下面列出deque的常用成員函數：

deque的實作比較複雜，内部會維護一個map（注意！不是STL中的map容器）即一小塊連續的空間，該空間中每個元素都是指針，指向另一段（較大的）區域，這個區域稱為緩沖區，緩沖區用來儲存deque中的資料。是以deque在随機通路和周遊資料會比vector慢。具體的deque實作可以參考《STL源碼剖析》，當然此書中使用的SGI STL與VS2008所使用的PJ STL的實作方法還是有差別的。下面給出了deque的結構圖：

由于篇幅問題，deque的實作細節就不再深入了，下面給出deque的使用範例：

[cpp]  view plain  copy

1. //雙向隊列 deque  
2. //by MoreWindows http://blog.csdn.net/morewindows  
3. #include <deque>  
4. #include <cstdio>  
5. #include <algorithm>  
6. using namespace std;  
7. int main()  
8. {  
9.     deque<int> ideq(20); //Create a deque ideq with 20 elements of default value 0  
10.     deque<int>::iterator pos;  
11.     int i;  
12.     //使用assign()指派  assign在計算機中就是指派的意思  
13.     for (i = 0; i < 20; ++i)  
14.         ideq[i] = i;  
15.     //輸出deque  
16.     printf("輸出deque中資料:\n");  
17.     for (i = 0; i < 20; ++i)  
18.         printf("%d ", ideq[i]);  
19.     putchar('\n');  
20.     //在頭尾加入新資料  
21.     printf("\n在頭尾加入新資料...\n");  
22.     ideq.push_back(100);  
23.     ideq.push_front(i);  
24.     //輸出deque  
25.     printf("\n輸出deque中資料:\n");  
26.     for (pos = ideq.begin(); pos != ideq.end(); pos++)  
27.         printf("%d ", *pos);  
28.     putchar('\n');  
29.     //查找  
30.     const int FINDNUMBER = 19;  
31.     printf("\n查找%d\n", FINDNUMBER);  
32.     pos = find(ideq.begin(), ideq.end(), FINDNUMBER);  
33.     if (pos != ideq.end())  
34.         printf("find %d success\n", *pos);  
35.     else  
36.         printf("find failed\n");  
37.     //在頭尾删除資料  
38.     printf("\n在頭尾删除資料...\n");  
39.     ideq.pop_back();  
40.     ideq.pop_front();  
41.     //輸出deque  
42.     printf("\n輸出deque中資料:\n");  
43.     for (pos = ideq.begin(); pos != ideq.end(); pos++)  
44.         printf("%d ", *pos);  
45.     putchar('\n');  
46.     return 0;  
47. }  

運作結果如下：

另外要注意一點。對于deque和vector來說，盡量少用erase(pos)和erase(beg,end)。因為這在中間删除資料後會導緻後面的資料向前移動，進而使效率低下。