🐋deque容器

和其他STL容器一样，deque容器也是以模板类deque<T>的<deque>头文件中，并位于std命名空间中。因此，在使用该容器之前，代码中需要包含如下代码(注意：std 命名空间也可以在使用 deque 容器时额外注明，两种方式都可以。)：

1
2
#include <deque>
using namespace std;

deque 是 double-ended queue 的缩写，又称双端队列容器。如果你已经了解vector，在学完deque之后，你就能发现这两者有很多相似之处，比如：

  • deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
  • deque 容器也可以根据需要修改自身的容量和大小。

和vector不同的是，deque还擅长在序列头部添加或删除元素，所耗费的时间复杂度也为常熟阶O(1)。并且更重要的一点是，deque容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

当需要想序列两端频繁的添加元素师，应首选deque容器。

🐋 创建deque容器

创建 deque 容器，根据不同的实际场景，可选择使用如下几种方式。

  1. 创建一个没有任何元素的空 deque 容器：
1
2
3
4
5
6
7
deque<int> d;	//创建一个存放int的deque容器
deque<float> dflt;	//创建一个存放float的deque容器
deque<string> dstr;	// 创建一个存放string的deque容器
//在头插入使用push_front()
d.push_front(1); //d = {1}
//在尾插入则使用push_back()
d.push_back(2); // d = {1,2}

和空 array 容器不同，空的 deque 容器在创建之后可以做添加或删除元素的操作，因此这种简单创建 deque 容器的方式比较常见。

  1. 创建一个具有 n 个元素的 deque 容器，其中每个元素都采用对应类型的默认值：
1
2
//创建一个大小为10的deque容器，默认元素为0
deque<int> d(10);

此行代码创建一个具有 10 个元素（默认都为 0）的 deque 容器。

  1. 创建一个具有 n 个元素的 deque 容器，并为每个元素都指定初始值，例如：
  • deque(n,elem); //构造函数将n个elem拷贝给本身。
1
2
//创建具有10个元素为5的deque 容器
deque<int> d(10, 5)

如此就创建了一个包含 10 个元素（值都为 5）的 deque 容器。

  1. 在已有 deque 容器的情况下，可以通过拷贝该容器创建一个新的 deque 容器，例如：
  • deque(const deque &deq); 拷贝构造函数。
1
2
deque<int> d1(5); 	// 创建大小为5的deque容器d1
deque<int> d2(d1);		//通过拷贝构造函数创建d2

注意，采用此方式，必须保证新旧容器存储的元素类型一致。

  1. 通过拷贝其他类型容器中指定区域内的元素（也可以是普通数组），可以创建一个新容器，例如：
  • deque(beg,end); 构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。
1
2
3
4
5
6
//拷贝普通数组，创建deque容器
int a[] = { 1,2,3,4,5 };
deque<int>d(a, a + 5);
//适用于所有类型的容器
array<int, 5> arr{ 11,12,13,14,15 };
deque<int>d(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

🐋deque容器的操作

🐋deque末尾的添加移除操作

1
2
3
4
deque.push_back(elem);	//在容器尾部添加一个数据
deque.push_front(elem);	//在容器头部插入一个数据
deque.pop_back();   	//删除容器最后一个数据
deque.pop_front();		//删除容器第一个数据

deque的赋值

1
2
3
4
deque.assign(beg,end);   //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
deque.assign(n,elem);  //将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq);	//重载等号操作符 
deque.swap(deq);  // 将vec与本身的元素互换

deque的大小

1
2
3
4
deque.size();	  //返回容器中元素的个数
deque.empty();	  //判断容器是否为空
deque.resize(num);  //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem);  //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

deque的插入

第一个参数为迭代器

1
2
3
deque.insert(pos,elem);  //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
deque.insert(pos,n,elem);  //在pos位置插入n个elem数据，无返回值。
deque.insert(pos,beg,end);  //在pos位置插入[beg,end)区间的数据，无返回值。

deque的删除

1
2
3
deque.clear();	//移除容器的所有数据 执行此操作之后deque.size() = 0
deque.erase(beg,end);  //删除[beg,end)区间的数据，返回下一个数据的位置。
deque.erase(pos);   //删除pos位置的数据，返回下一个数据的位置。

🐋deque容器成员方法

基于deque双端队列的特点，该容器包含一些 array、vector 容器都没有的成员函数。

下表中罗列了deque容器提供的所有成员函数。

函数成员 函数功能
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
at() 使用经过边界检查的索引访问元素。
front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。
insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素，容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。

和 vector 相比，额外增加了实现在容器头部添加和删除元素的成员函数，同时删除了 capacity()、reserve() 和 data() 成员函数。

💻程序演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <deque>
using namespace std;
int main()
{
	deque<int> dq(1,2);
	dq.push_front(1);
	dq.push_back(3);
	cout << "dq当前的大小为：" << dq.size() << endl;
	cout << "dq中的元素为：";
	for (auto it : dq)
		cout << it << " ";
	cout << endl;
	deque<int> dq2(dq.begin(),dq.end()); //拷贝构造赋值
	cout << "dq2的大小为：" << dq2.size() << endl; //dq2.size() = 3
	dq2.insert(dq2.end(),4,4);  //第一个参数是迭代器 dq2 = {1,2,3,4,4,4,4} 
	dq2.clear(); // 移除容器的所有数据 dq2.size() = 0
	cout << "执行\"dq2.clear()\"移除容器后dq2.size() = " << dq2.size() << endl;
	dq2.resize(5, 5); //重新定义 dq2 = {5,5,5,5,5}
	cout << "执行\"dq2.resize(5, 5)\"移除容器后dq2.size() = " << dq2.size() << endl;
	system("pause");
	return 0;
}

运行结果为：

dq当前的大小为：3
dq中的元素为：1 2 3
dq2的大小为：3
执行"dq2.clear()"移除容器后dq2.size() = 0
执行"dq2.resize(5, 5)"移除容器后dq2.size() = 5