deque容器的相关概念及常用接口

deque的基本概念

作用：作为双端数组，可以很方便的对头尾进行插入和删除操作

注意：适用deque时需包含头文件deque

deque与vector的区别

1、vector对数组头部的插入和删除操作效率低，时间复杂度高。数据量越大，效率越低。deque相比于vector而言，对头部元素操作的效率较高，适用于需要经常对头部数据处理的情形

2、vector访问元素的速度会比deque快，这与两者内部的实现有关

deque内部结构图

deque内部工作原理：

deque内部有一个中控器，维护每段缓冲区中的内容，缓冲区中存放真实的数据。中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的空间一样（其实是由多个缓冲区组成的离散的空间）。当缓冲区存满后，系统会再找一片连续的空间作为缓冲区并将指向缓冲区的指针记录到中控器中

图例：

补：deque的迭代器支持随机访问

注：由于deque和vector的作用非常类似，因此在实现时，二者的对象函数也差不多，学习时可以结合二者一起学习

deque构造函数

功能描述：用于对象的初始化（容器构造）

deque容器的赋值操作

作用：为容器赋值

eg：

#include<iostream>
using namespace std;
#include<deque>
int main()
{deque<int>d;for (int i = 0; i < 5; i++){d.push_back(i);}deque<int>d1;d1.assign(d1.begin(), d1.end());deque<int>d2 = d;system("pause");return 0;
}

deque大小操作

功能：对容器的大小进行指定，或获得容器的大小

注：1、对比参照vector相应对象函数即可

2、对于empty，若容器为空，则返回true，否则返回false

deque的插入与删除

作用：向容器内插入和删除元素

注：插入和删除提供的位置都是迭代器，不能是整数

eg：

#include<iostream>
using namespace std;
#include<deque>
void printDeque(const deque<int>& d)
{/*for (int i = 0; i < d.size(); i++){cout << d[i] << ' ';}*///由于传入的deque是一个只读的容器，因此不能采用传统的迭代器，只能采用只读迭代器，即const_iteratorfor (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)//遍历deque可以采用下标或迭代器的方式{cout << *it << ' ';}cout << endl;
}
int main()
{deque<int>d;for (int i = 0; i < 5; i++){d.push_back(i);}d.insert(d.begin(),1);//从d的开头插入一个1printDeque(d);//1 0 1 2 3 4d.insert(d.begin(), d.begin(), d.end());//从d的开头插入d从区间开始到末尾的元素printDeque(d);//1 0 1 2 3 4 1 0 1 2 3 4d.insert(d.begin(), 5, 1);//在d起始位置插入5个1printDeque(d);d.erase(d.begin(), d.begin() +5 );//删除d中从起始位置开始，到起始位置+5位置之间的元素printDeque(d);d.erase(d.begin());//删除d起始位置元素printDeque(d);system("pause");return 0;
}