C++——STL标准模板库——容器详解——deque

一、基本概念

deque：双端队列。和vector容器一样同属于STL中的序列式容器，相较vector容器的尾部操作，多提供了头部的快速插入和删除操作。deque的特点如下：

1、deque提供双端元素的插入和删除操作，物理结构上是由多块离散式连续存储空间（buffer）组成，一般为定长数组缓冲区，这些缓冲区形成双向链表；deque通过中控器（一般是map结构）来维护这些缓冲区的指针。

2、提供双向随机访问迭代器：deque迭代器是一个智能指针，包含4个私有成员变量，分别是cur、first、last、node。cur指向当前访问元素，first指向当前访问元素所在buffer的首地址，last指向当前访问元素所在buffer的最后一个元素位置，node指向当前访问元素所在结点（封装了buffer）

3、deque底层由中控器（map结构）管理，在物理存储层面实现动态扩展。当一个缓冲区满时，中控器会自动为其分配一个新的缓冲区。同样地，当需要释放内存时，中控器会自动回收不再使用的缓冲区。这样的结构也就决定了deque没有capacity的概念。

总的来说，deque的中控器是一个高效的数据结构，它通过使用map来维护缓冲区的位置信息，使得deque可以在头部和尾部进行高效的插入和删除操作。这种设计使得deque成为在需要频繁进行前后端操作的应用中的理想选择。

二、构造函数

deque<T> d;                                               默认构造函数

deque<T> d(int n,const T& value);             带参构造函数，含有n个元素，初始化为value

deque<T> d(deque<T>& d1);                     复制构造函数

deque<T> d(iterator first,iterator last);        范围构造函数，将范围区间内元素复制到新容器

deque<T> d(deque<T>&& d1);                   移动构造函数（c++11）

三、成员函数

（一）访问函数

T& deque<T>::operator[](int index);        数组符号重载，返回该index位置的引用

T& deque<T>::at(int index);                     返回该index位置的引用

T& deque<T>::front();                              返回该该容器头元素的引用

T& deque<T>::back();                              返回该容器尾元素的引用

（二）修改函数

相较vector，新增了头插和头删函数

void deque<T>::push_back(T& value);        尾插

void deque<T>::pop_back();                        尾删

void deque<T>::push_front(T& value);        头插

void deque<T>::pop_front();                        头删

void deque<T>::insert(iterator it,T& value); 在指定位置插入元素

void deque<T>::erase(iterator it);                删除指定位置元素

（三）大小函数

deque双端队列没有容量的概念，但有可容纳最大元素数量，这个数量是由系统决定的

size_t deque<T>::size();                返回当前容器中元素数量

bool deque<T>::empty();               判断当前容器是否为空

size_t deque<T>::max_size();       返回这个系统中双端队列deque能够容纳最大元素数量

（四）赋值操作

deque<T>& operator=(const deque<T>& other);        将other内容复制到当前容器

deque<T>& operator=(initializer_list<T> init);             将初始化列表复制到当前容器

deque<T>& operator=(deque<T>&& other)noexcept;将other内容通过移动赋值给当前容器

移动赋值和移动构造函数一样，需要将参数通过move()函数转换为右值引用，本质上类似于浅拷贝，但在浅拷贝的过程中，解除了原有对象other对资源的所有权和控制权，移交给了当前容器。移动语义技术出现在c++11及以后版本，处理大量数据或资源密集型对象时，避免了大量赋值操作，优化程序性能

四、注意事项

1、越界风险。当使用下标运算符[]，下标超出范围，index>size()时，行为是未定义的。at()不会存在此风险；下标越界时，at()会抛出out_of_range的异常提示。

2、迭代器失效。当容器添加或删除元素时会导致部分迭代器或者指针失效，特别是储存空间重新分配时，所有迭代器和指针都会失效。

3、内存管理。deque的内存管理比vector更复杂，当插入和删除元素时都有可能重新分配储存空间。deque能够自动释放空闲内存。

4、操作性能。deque提供双端插入或删除操作，但是从中间插入或者删除操作时，性能下降。