本文原创发表地址为：http://www.cppblog.com/kusamba/archive/2010/09/17/126895.html，转载请保留原链接，谢谢！
deque的数据结构示意图：
技术要点：
随机访问每个元素，所需要的时间为常量。
在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除元素所需时间随元素数目呈线性变化。
可动态增加或减少元素，内存管理自动完成，不提供用于内存管理的成员函数。参考代码：
1 /************************************************************************
2 * deque:
3 * 1, 分块分配空间，非顺序存储，随机访问是通过复杂的iterator实现
4 * 2, 在前后插入数据时间复杂度为O(1)
5 * 3, 迭代器失效：
6 * If an element is inserted into an empty sequence, or if an element is
7 erased to leave an empty sequence, then iterators earlier returned
8 by begin and end become invalid.
9
10 If an element is inserted at the first position of the deque,
11 then all iterators, but no references, that designate existing
12 elements become invalid.
13
14 If an element is inserted at the end of the deque, then end and all
15 iterators, but no references, that designate existing elements become invalid.
16
17 If an element is erased at the front of the deque, only that iterator
18 and references to the erased element become invalid.
19
20 If the last element is erased from the end of the deque, only that
21 iterator to the final element and references to the erased element become invalid.
22
23 Otherwise, inserting or erasing an element invalidates all iterators and references.
24
25 * by Kusamba@126.com http://www.cppblog.com/kusamba
26 */
27 void deque_test()
28 {
29 deque<int> dqInt;
30
31 int nSize = dqInt.size();
32 int nMaxSiz = dqInt.max_size();
33
34 dqInt.resize(100);
35 dqInt.resize(10, 2);
36
37 /**
38 * push_back
39 */
40 for (int i = 0; i < 10; ++i)
41 {
42 dqInt[i] = i + 1;
43 }
44 for (int i = 0; i < 10; ++i)
45 {
46 dqInt.push_back(i + 11);
47 }
48
49 /**
50 * insert
51 */
52 for (deque<int>::iterator it = dqInt.begin(); it != dqInt.end();)
53 {
54 if (*it % 3 == 0) //在3的倍数的元素后面插入100
55 {
56 it = dqInt.insert(it + 1, 100);
57 }
58 else
59 {
60 ++it;
61 }
62 }
63
64 /**
65 * erase
66 */
67 for (deque<int>::iterator it = dqInt.begin(); it != dqInt.end();)
68 {
69 if (*it == 4)
70 {
71 it = dqInt.erase(it);
72 }
73 else
74 {
75 ++it;
76 }
77 }
78
79 /**
80 * traverse
81 */
82 printf("print deque: ");
83 for (int i = 0; i < dqInt.size(); ++i)
84 {
85 printf("%d ", dqInt[i]);
86 }
87 printf("\n");
88
89 /**
90 * pop
91 */
92 while (!dqInt.empty())
93 {
94 int nItemVal = dqInt.front();
95 dqInt.pop_front();
96 }
97 }