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 优点：看前面的介绍。