C++——deque的了解和使用

引言

标准库中的deque

一、deque的基本概念

二、deque的常用接口

1.deque的迭代器

2.deque的初始化

3.deque的容量操作

3.1 有效长度和容量大小

3.2 有效长度和容量操作

4.deque的访问操作

5.deque的修改操作

三、deque的应用场景

结束语

引言

在C++中，deque是STL（标准模板库）提供的一种容器类，专门用于存储各种类型的元素，并支持在两端进行快速的插入和删除操作。今天我们就试着来学习一下这一数据结构。

标准库中的deque

一、deque的基本概念

Deque是一种线性数据结构，它允许在两端进行插入和删除操作。这两端通常被称为前端（front）和后端（rear），或者端点1和端点2。Deque的灵活性在于，它既可以用作队列（FIFO，先进先出），也可以用作栈（LIFO，后进先出），具体取决于元素的插入和删除操作是在哪一端进行的。deque是C++STL（标准模板库）中的一种容器，可以用于存储各种类型的元素。deque的特点是可以在队列的两端进行元素的操作，并且可以高效地在队列的任意位置进行元素的插入和删除操作。

二、deque的常用接口

1.deque的迭代器

与string和vector类似，deque也有迭代器。

由于deque定义在deque类中，因此我们想要使用deque的迭代器需要通过域作用限定符访问——deque<类型>::iterator 。

其中，begin()，end()，rbeign()，rend()的使用访问方法与string和vector的使用方法类似。

我们来看代码：

int main()
{deque<int> d = { 0,1,2,3,4, };deque<int>::iterator it = d.begin();cout << "顺序遍历：";while (it != d.end()){cout << *it << " ";++it;}cout << endl;cout << "逆序遍历：";deque<int>::reverse_iterator rit = d.rbegin();while (rit != d.rend()){cout << *rit << " ";++rit;}return 0;
}

输出结果为：

2.deque的初始化

来看代码演示：

void Print(deque<int>& d)
{for (deque<int>::iterator it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}int main()
{deque<int> d1;for (int i = 0; i < 5; ++i){d1.push_back(i);}deque<int> d2(d1.begin(), d1.end());deque<int> d3(5, 5);deque<int> d4(d3);cout << "打印d1: ";Print(d1);cout << "打印d2: ";Print(d2);cout << "打印d3: ";Print(d3);cout << "打印d4: ";Print(d4);return 0;
}

输出结果为：

3.deque的容量操作

下面是关于deque的容量操作：

函数名称	功能
size	返回deque的有效长度
clear	清空deque
empty	检查deque是否为空，是则返回ture，否则返回false
resize	重新设置有效元素的数量，超过原来有效长度则用c字符填充

3.1 有效长度和容量大小

deque没有capacity接口。deque，即双端队列（Double Ended Queue），是一个双向开口的连续线性空间，允许在头尾两端分别进行插入和删除操作。其特性决定了它不需要像某些其他数据结构（如vector）那样具有固定的容量（capacity）概念。

下面是简单的测试用例：

int main()
{deque<int> d = { 0,1,2,3,4 };cout << d.size() << endl;if (d.empty()){cout << "d为空" << endl;}else{cout << "d不为空" << endl;}d.clear();if (d.empty()){cout << "d为空" << endl;}else{cout << "d不为空" << endl;}return 0;
}

3.2 有效长度和容量操作

deque这个容器没有提供reserve接口，接下来我们来学习一下resize这个接口：

resize()与我们之前学习的string、vector用法一致，在这里就不多介绍了

来看代码演示：

int main()
{deque<int> d = { 1,2,3,4,5 };d.resize(3);for (int i = 0; i < d.size(); i++){cout << d[i] << " ";}cout << endl;d.resize(4);for (int i = 0; i < d.size(); i++){cout << d[i] << " ";}cout << endl;d.resize(5, 9);for (int i = 0; i < d.size(); i++){cout << d[i] << " ";}cout << endl;return 0;
}

输出结果为：

4.deque的访问操作

函数名称	功能
operator[]	返回指定位置的元素，越界则报错
at	返回指定位置的元素，越界则抛异常
front	返回字符串第一个元素
back	返回字符串最后一个元素

这部分内容和之前学习的vector容器部分内容差不多

int main()
{deque<int> d = { 0,1,2,3,4,5,6,7,8,9 };for (int i = 0; i < d.size(); i++){cout << d[i] << " ";}cout << endl;for (int i = 0; i < d.size(); i++){cout << d.at(i) << " ";}cout << endl;cout << "front：" << d.front() << endl;cout << "back：" << d.back() << endl;return 0;
}

输出结果：

5.deque的修改操作

deque的修改操作有如下几个：

函数名称	功能
push_back	在数组后追加元素
pop_back	删除数组最后一个元素
insert	在指定位置追加元素
assign	使用指定数组替换原数组
erase	删除数组指定部分区间
swap	交换两个数组

直接看代码：

尾删和尾插：

int main()
{deque<int> d = { 0,1,2,3,4,5,6,7,8,9 };for (int i = 0; i < d.size(); i++){cout << d.at(i) << " ";}cout << endl;d.push_back(10);for (int i = 0; i < d.size(); i++){cout << d.at(i) << " ";}cout << endl;d.pop_back();for (int i = 0; i < d.size(); i++){cout << d.at(i) << " ";}cout << endl;return 0;
}

输出结果为：

assign和swap：

int main()
{deque<int> d1 = { 9,9,9,9,9 };d1.assign(3, 3);for (int i = 0; i < d1.size(); i++){cout << d1[i] << " ";}cout << endl;deque<int> d2 = { 1,1,1,1,1 };d1.swap(d2);for (int i = 0; i < d1.size(); i++){cout << d1[i] << " ";}cout << endl;for (int i = 0; i < d2.size(); i++){cout << d2[i] << " ";}cout << endl;return 0;
}

输出结果为：

insert：

int main()
{deque<int> d1(5, 10);deque<int>::iterator it = d1.begin();it = d1.insert(it, 100);cout << "d1:";for (it = d1.begin(); it < d1.end(); it++){cout << *it << " ";}cout << endl;d1.insert(it, 2, 1000);it = d1.begin();cout << "d1:";for (it = d1.begin(); it < d1.end(); it++){cout << *it << " ";}cout << endl;deque<int> d2(2, 10000);it = d1.begin();d1.insert(it + 2, d2.begin(), d2.end());cout << "d1:";for (it = d1.begin(); it < d1.end(); it++){cout << *it << " ";}cout << endl;return 0;
}

输出结果为：

erase：

int main()
{deque<int> d = { 0,1,2,3,4,5,6,7,8,9 };deque<int>::iterator it = d.erase(d.begin() + 3);	// 删除值为3的元素it = d.erase(it);	// 删除值为4的元素for (int i = 0; i < d.size(); i++){cout << d[i] << " ";}cout << endl;it = d.erase(d.begin(), d.begin() + 5);for (int i = 0; i < d.size(); i++){cout << d[i] << " ";}cout << endl;return 0;
}

输出结果为：