deque 双端队列容器
STL学习笔记-- deque
deque 双端队列容器 ( double-ended queue ) 与 vector 非常相似，不仅可在尾部插入和删除元素，还可以在头部插入和删除，算法的时间复杂度也是常数阶 O(1),是一个实现了 Random access container 、Back insertion sequence 和 Front insertion sequence 概念的模型。
deque 内部的数据机制和执行性能与 vector 不同，一般来说，当考虑到容器元素的内存分配策略和操作的性能时，deque 相对 vector 有优势。
deque 的 C++ 标准头文件为 deque，需要用宏语句 "#include <deque>" 进行导入，才可使用 deque 进行开发应用。
创建 deque 对象
可用如下的几个构造函数创建 deque 容器对象
1. deque()
创建一个没有任何元素的 deque 对象。此构造函数的更一般形式是 " deque(const A& a = A()) "， A 是一个内存分配器，可缺省。
所创建的 deque 容器实际已具有一个 deque 块，只是头尾迭代器重叠，容器还没有任何元素。例如，下面的一行代码创建了 deque 对象 dInt
deque<int> dInt;
2. deque(size_type n)
创建一个具有 n 个元素的 deque 对象，每个元素采用他的类型下的默认值。此时，deque 头尾迭代器已指向 deque 的头尾元素。
例如，下面一行代码创建了具有 10 个元素的 deque 对象 dInt，每个元素初始值为 0
deque<int> dInt(10);
3. deque(size_type n, const T& value)
创建一个具有 n 个元素的 deque 对象，这些元素的初始值为 value。
例如，下面一行代码创建了一个具有 10 个元素的 deque 对象 dDou，每个元素的初始值为 3.1415
deque<double> dDou(10, 3.1415);
4. deque(const deque&)
deque的拷贝构造函数，通过拷贝一个 deque 对象的元素值，创建一个新的 deque 对象。此时，新旧 deque 对象具有相同块数的 deque 块，各自块内部的元素也对应相等。
例如，下面使用了 deque 对象 d1，创建了新的 deque 对象 d2。此时，d2 对象的 5 个元素值也具有字符值 "K"
deque<char> d1(5, 'K');
deque<char> d2(d1);
5. deque(const InputIterator first, const InputIterator last, const A& a = A())
将迭代器区间 [first, last) 所指的元素拷贝到一个新创建的 deque 对象中，其中，内存分配器可缺省。
// 利用 int 数组 iArray,创建了一个 deque 对象 d
int iArray[] = {1, 2, 3, 4, 5};
deque<int> d(iArray, iArray + 5);
初始化赋值
deque 提供的 push_back() 函数，可在尾部压人新元素 value，常用作 deque 容器的初始化赋值
元素的遍历访问
deque 的元素同样可采用数组、 .at() 函数或者迭代器的方式进行遍历访问。
用数组方式访问
1 -------------------------------------------------------- 用数组方式访问 deque 元素
2 #include <deque>
3 #include <iostream>
4 using namespace std;
5 int main()
6 {
7 deque< int > dInt;
8 dInt.push_back( 1 );
9 dInt.push_back( 3 );
10 dInt.push_back( 5 );
11 dInt.push_back( 7 );
12
13 for ( int i= 0 ; i<dInt.size(); i++ )
14 {
15 // 打印 d[0], d[1], d[2], d[3]。访问越界时，不产生异常
16 cout << " d[ " << i << " ]= " << dInt[i] << endl;
17
18 // 输出 dInt 中各个元素。当访问越界时，会抛出异常
19 // cout << dInt.at(i) << endl;
20 }
21
22 return 0 ;
23 }
用迭代器访问deque 元素
1 -------------------------------------------------------- 用迭代器访问 deque 元素
2 #pragma warning(disable:4786) // 必须放在首行，忽略长字符的截断警告
3 #include <deque>
4 #include <iostream>
5 #include < string >
6 using namespace std;
7 int main()
8 {
9 deque< string > dStr;
10 dStr.push_back( " 北京 " );
11 dStr.push_back( " 2008 " );
12 dStr.push_back( " 奥运 " );
13
14 // 迭代器 i 和 iend
15 deque< string > ::iterator i, iend;
16 iend = dStr.end();
17 int j;
18 // 打印 “北京2008奥运”
19 for (i=dStr.begin(), j= 0 ; i!=iend; ++i, ++ j)
20 cout << * i;
21 cout << endl;
22
23 return 0 ;
24 }
头部和中间位置插入 deque 元素
1 /* 解释：
2 由于 deque 使用了两个迭代器分别指向双端队列的首尾，因此，deque 具有高效的【头部】插入元素的函数 push_front()
3 其他位置的插入，将涉及相关元素的移位拷贝。
4 */
5
6 -------------------------------------------------------- 头部和中间位置插入 deque 元素
7 #include <deque>
8 #include <iostream>
9 using namespace std;
10 int main()
11 {
12 deque< int > dInt;
13 dInt.push_back( 6 );
14 dInt.push_back( 7 );
15
16 // 头部插入
17 dInt.push_front( 5 );
18 for ( int i= 0 ; i<dInt.size(); i++ )
19 cout << dInt[i] << ' ' ;
20 cout << endl;
21
22 // 中间位置插入
23 // 在第2个元素之前插入9， 即 5 9 6 7
24 dInt.insert(dInt.begin() + 1 , 9 );
25 for ( int j= 0 ; j<dInt.size(); j++ )
26 cout << dInt[j] << ' ' ;
27 cout << endl;
28
29 return 0 ;
30 }
头尾和其他位置删除 deque 元素
1 /* 解释：
2 deque 容器提供了删除首元素的 pop_front 函数，删除尾元素的 pop_back 函数，删除任意位置或迭代器区间上元素的 erase 函数，以及删除所有元素的 clear 函数。
3 1. void pop_front(); 删除 deque 的第一个元素
4 2. void pop_back(); 删除 deque 的最后一个元素
5 3. iterator erase(iterator pos); 删除 pos 所指向的元素
6 4. iterator erase(iterator first, iterator last); 删除 迭代器区间 [first, last) 所指向的所有元素。
7 5. void clear(); 删除所有元素
8 */
9
10 -------------------------------------------------------- 头尾和其他位置删除 deque 元素
11 #include <deque>
12 #include <iostream>
13 using namespace std;
14 int main()
15 {
16 deque< int > dInt;
17 dInt.push_back( 4 );
18 dInt.push_back( 5 );
19 dInt.push_back( 3 );
20 dInt.push_back( 3 );
21 dInt.push_back( 3 );
22 dInt.push_back( 6 );
23 for ( int i= 0 ; i<dInt.size(); i++ )
24 cout << dInt[i] << ' ' ;
25 cout << endl;
26
27 // 头尾和任意删除元素
28 dInt.erase(dInt.begin() + 1 ); // 删除第 2 个元素 dInt[1]
29 dInt.pop_front(); // 删除首元素
30 dInt.pop_back(); // 删除末尾元素
31 for ( int j= 0 ; j<dInt.size(); j++ )
32 cout << dInt[j] << ' ' ;
33 cout << endl;
34 // 删除所有元素
35 dInt.clear();
36 cout << " 执行 clear() " << endl << " deque 元素全部清除 " << endl;
37
38 return 0 ;
39 }
deque 元素的反向遍历
1 -------------------------------------------------------- deque 元素的反向遍历
2 #include <deque>
3 #include <iostream>
4 using namespace std;
5 int main()
6 {
7 deque< int > dInt;
8 dInt.push_back( 1 );
9 dInt.push_back( 3 );
10 dInt.push_back( 5 );
11 dInt.push_back( 7 );
12 dInt.push_back( 9 );
13 dInt.push_back( 11 );
14 // deque元素的前向遍历
15 deque< int > ::iterator i,iend;
16 iend = dInt.end();
17 for (i=dInt.begin(); i!=iend; ++ i)
18 cout << *i << ' ' ;
19
20 cout << endl;
21 // deque元素的反向遍历
22 deque< int > ::reverse_iterator ri, riend;
23 riend = dInt.rend();
24 for (ri=dInt.rbegin(); ri!=riend; ++ ri)
25 cout << *ri << ' ' ;
26 cout << endl;
27
28 return 0 ;
29 }
两个 deque 容器的元素交换
1 -------------------------------------------------------- 两个 deque 容器的元素交换
2 #include <deque>
3 #include <iostream>
4 using namespace std;
5
6 void print(deque< int >& d);
7
8 int main()
9 {
10 // d1
11 deque< int > d1;
12 d1.push_back( 11 );
13 d1.push_back( 12 );
14 d1.push_back( 13 );
15 cout << " d1 = " ;
16 print(d1);
17
18 // d2
19 deque< int > d2;
20 d2.push_back( 90 );
21 d2.push_back( 91 );
22 d2.push_back( 92 );
23 cout << " d2 = " ;
24 print(d2);
25
26 // d1 和 d2 交换
27 d1.swap(d2);
28 cout << " d1 和 d2 交换后 " << endl;
29 cout << " d1 = " ;
30 print(d1);
31 cout << " d2 = " ;
32 print(d2);
33
34 return 0 ;
35 }
36
37 // deque 元素打印
38 void print(deque< int >& d)
39 {
40
41 for ( int i= 0 ; i<d.size(); i++ )
42 cout << d[i] << ' ' ;
43 cout << endl;
44 }
deque 其他常用函数的使用
1 /* 解释：
2 deque 其他函数的说明，参加 Random access container 、 Back insertion sequence 和 Front insertion sequence 概念的函数定义要求，下面给出 deque 的其他几个常用函数的用法。
3 bool empty() 判断 deque 容器是否已有元素，是则返回 true，否则返回 false
4 size_type size() 当前 deque 容器的元素个数
5 size_type max_size() 系统所支持的 deque 容器的最大元素个数
6 reference front() deque容器的首元素（引用返回），要求 deque 不为空
7 reference back() deque容器的末元素（引用返回），要求 deque 不为空
8 */
9
10 -------------------------------------------------------- deque 其他常用函数的使用
11 #pragma warning(disable:4786)
12 #include <deque>
13 #include <iostream>
14 #include < string >
15 using namespace std;
16 int main()
17 {
18 deque< string > dStr;
19 // 打印 deque 为空
20 cout << " dStr是否为空: " << dStr.empty() << endl;
21 // 装入deque 元素
22 dStr.push_back( " 红楼梦 " );
23 dStr.push_back( " 三国演义 " );
24 dStr.push_back( " 西游记 " );
25 dStr.push_back( " 水浒传 " );
26 dStr.push_back( " 史记 " );
27 dStr.push_back( " 莫言 " );
28 dStr.push_back( " 金庸 " );
29 dStr.push_back( " 何亮到此一游 " );
30 // 打印 deque 所有元素
31 deque< string > ::iterator i, iend;
32 iend = dStr.end();
33 for (i=dStr.begin(); i!=iend; ++ i)
34 cout << *i << " " ;
35 cout << endl;
36 // 打印首元素
37 cout << " deque 首元素为: " << dStr.front() << endl;
38 // 打印末元素
39 cout << " deque 末元素为: " << dStr.back() << endl;
40 // 打印元素个数
41 cout << " deque 元素个数为: " << dStr.size() << endl;
42 // 打印可支持的最大 deque 元素个数
43 cout << " deque 最大元素个数为: " << dStr.max_size() << endl;
44
45 return 0 ;
46 }
------------------ deque 小结
deque 双端队列容器采用分块的线型结构来存储数据，两个迭代器分别指向容器的首尾元素，具有高效的首尾元素的 push_front() 和 pop_front() 函数。
由于 deque 容器是以 deque 块为单位进行内存分配，并使用了二级的 Map 进行管理，因此，不易于实现类似于 vector 的 capacity 和 reverse 函数，而且，deque 容器也不需要这样的获取和调整容器大小的函数。
deque 缺点：频繁的插入删除的时候， deque 不合适。
deque 优点：看前面的介绍。
【好好学习，天天向上】 ||||||| 【 亮仔 到此一游 】
分类: STL学习笔记
标签: STL , C++ , 容器 , deque
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息