C++STL——deque容器详解

纵有疾风起，人生不言弃。本文篇幅较长，如有错误请不吝赐教，感谢支持。

💬文章目录

一.deque容器的基本概念

vector容器是单向开口的连续内存空间，deque（['dek]）则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，可以理解为数据结构的双端队列。当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，全部元素都要后移，无法被接受。

✅deque容器和vector容器的差异：

• ①deque是双端队列，可在容器的头部和尾部插入或删除元素。
• ②deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，deque不会像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。deque可以随时将空间串接在首部或尾部，也因此，deque没有必须要提供所谓的空间保留(reserve)功能。

✅deque容器内部实现原理：

deque容器在逻辑上是一片连续的空间，但这只是一种假象，实际deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了（1）重新配置空间申请更大空间 (2)原数据复制新空间 (3)释放原空间三步骤，代价就是复杂的迭代器架构。

既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象。deque内部存在中央控制器，记录与维护每段数据缓冲区（存储数据的空间）的内存地址，缓冲区中存储真实数据，保证可从容器的头部与尾部插入或删除元素。缓冲区才是deque的存储空间主体。

deque容器的迭代器：
支持随机访问的迭代器，可跳跃式访问容器元素。

二.deque容器常用操作

①deque构造函数

作用：创建deque容器。
注：使用deque容器时，需包含头文件

#include <deque>

函数原型解释

deque<T>

deq T;默认构造形式（显示实例化）deque(beg, end);构造函数将[beg, end)区间中的元素拷贝给本身。deque(n, elem);有参构造函数，使用n个elem元素进行初始化。deque(const deque &deq);拷贝构造函数，使用已有deque对象初始化新的对象。
实例：deque构造函数

#include<iostream>usingnamespace std;#include<deque>//包含头文件voidprintdeque(const deque<int>& deq)//形参使用const，避免被修改{//const_iterator只读迭代器for(deque<int>::const_iterator it = deq.begin(); it != deq.end();++it){
        cout <<*it<<"|";}
    cout << endl;}voidtest(){
    deque<int> v1 ={1,2,3};//采用模板实现类实现（显示实例化），默认构造函数，
    deque<int>v2(6,1);//构造函数将n个elem拷贝给本身。int arr[10]={1,2,3,4,5,6,7,8,9,10};
    deque<int>v3(arr, arr +sizeof(arr)/sizeof(arr[0]));//将v[begin(), end())区间中的元素拷贝给本身
    deque<int>v4(v1);//拷贝构造函数，拿另一个vector对象初始化本身printdeque(v1);printdeque(v2);printdeque(v3);printdeque(v4);}intmain(){test();return0;}

②deque元素操作

作用：通过重载赋值运算符operator[]和成员函数at(int index)，对deque容器的单个元素进行读（作为右值）或写（作为左值）。
函数原型解释T &operator[](size_t n);通过[]访问元素，如果越界，不抛异常，程序直接挂掉T &at(size_t n);通过at方法获取下标为n的元素，如果n越界，抛出out_of_range异常。T *data();返回容器中动态数组的首地址。const T *data() const;返回容器中动态数组的首地址。T &front();返回第一个元素。T &back();返回，最后一个元素。

③deque赋值操作

作用：通过重载赋值运算符operator=和成员函数assign()，对deque容器进行赋值。
函数原型解释assign(beg, end);拷贝目标deque容器中[begin(), end())区间的元素，对当前deque容器赋值。assign(n, elem);将n个elem拷贝赋值给本身。deque&operator=(const deque &deq);重载等号操作符swap(deq);将deq与本身的元素互换
实例：deque赋值操作

#include<iostream>usingnamespace std;#include<deque>//包含头文件voidprintdeque(const deque<int>& deq)//形参使用const，避免被修改{//const_iterator只读迭代器for(deque<int>::const_iterator it = deq.begin(); it != deq.end();++it){
        cout <<*it<<"|";}
    cout << endl;}voidtest(){
    deque<int> deq;//尾插法插入元素for(int i =0; i <5; i++){

        deq.push_back(i);}//遍历printdeque(deq);//0 1 2 3 4/* 1.重载运算符=赋值 */
    deque<int> d1;
    d1 = deq;printdeque(d1);//0 1 2 3 4/* 2.assign()函数，区间拷贝 */
    deque<int> d2;
    d2.assign(deq.begin(), deq.end());printdeque(d2);//0 1 2 3 4/* 3.assign()函数，n个elem元素赋值 */
    deque<int> d3;//5个整型元素6
    d3.assign(5,6);printdeque(d3);//6 6 6 6 6}intmain(){test();return0;}

④deque交换操作

💬表格一览：
函数原型解释void swap(deque &deq);把当前容器与deq交换。
实例：deque交换操作

#include<iostream>usingnamespace std;#include<deque>//包含头文件voidprintdeque(const deque<int>& deq)//形参使用const，避免被修改{//const_iterator只读迭代器for(deque<int>::const_iterator it = deq.begin(); it != deq.end();++it){
        cout <<*it<<"|";}
    cout << endl;}voidtest(){
    deque<int> deq;//尾插法插入元素for(int i =0; i <5; i++){

        deq.push_back(i);}//遍历printdeque(deq);//0 1 2 3 4
    deque<int> d1;
    d1.swap(deq);//将deq与本身的元素互换printdeque(d1);}intmain(){test();return0;}

⑤deque大小操作

作用：操作deque容器的大小（即元素个数）。
函数原型解释bool empty() const;判断容器是否为空。size_t size() const;返回容器的实际大小（已使用的空间）。resize(int num)；重新指定容器的长度为num。若容器变长，则以默认值0填充新位置；若容器变短，则容器末尾超出新长度的元素被删除。resize(int num, elem);重新指定容器的长度为num。若容器变长，则以指定值elem填充新位置；若容器变短，则容器末尾超出新长度的元素被删除。
实例：deque大小操作

#include<iostream>usingnamespace std;#include<deque>//包含头文件voidprintdeque(const deque<int>& deq)//形参使用const，避免被修改{//const_iterator只读迭代器for(deque<int>::const_iterator it = deq.begin(); it != deq.end();++it){
        cout <<*it<<"|";}
    cout << endl;}voidtest(){
    deque<int> deq;//尾插法插入元素for(int i =0; i <5; i++){

        deq.push_back(i);}printdeque(deq);//0 1 2 3 4//empty()：判断容器是否为空
    cout <<(deq.empty()?"deq为空":"deq不为空")<< endl;//deq不为空//size(); ：获取容器的大小，即元素个数。
    cout <<"deq的大小/元素个数："<< deq.size()<< endl;//5//resize(int num);：重新指定容器的长度为num//若容器变长，则以默认值0填充新位置；若容器变短，则容器末尾超出新长度的元素被删除。
    deq.resize(10);//长度变大时，使用默认值0填充printdeque(deq);//0 1 2 3 4 0 0 0 0 0

    deq.resize(3);//长度变小时，容器末尾超出新长度的元素被删除printdeque(deq);//0 1 2//resize(int num, elem); ：重新指定容器的长度为num。//若容器变长，则以指定值elem填充新位置；若容器变短，则容器末尾超出新长度的元素被删除。
    deq.resize(8,6);//长度变大时，使用指定值6填充printdeque(deq);//0 1 2 6 6 6 6 6}intmain(){test();return0;}

注：deque容器不存在容量的概念，即不存在capacity()成员函数。可随时开辟缓冲区存储数据。

⑥deque插入和删除

💬表格一览：
函数原型解释iterator insert(iterator pos, const T& ele);在指定位置插入一个元素ele 返回指向插入元素的迭代器。iterator insert(const_iterator pos, int count,ele);迭代器指向位置pos插入count个元素ele.返回指向插入元素的迭代器。void push_front(const T& ele);在容器头部插入一个数据void push_back(const T& ele);尾部插入元素elevoid pop_front();删除容器第一个数据void pop_back();删除最后一个元素void clear();清空容器。iterator erase(const_iterator start, const_iterator end);删除迭代器从start到end之间的元素，返回下一个有效的迭代器。iterator erase(const_iterator pos);删除迭代器指向的元素，返回下一个有效的迭代器。
实例：deque插入和删除

#include<iostream>usingnamespace std;#include<deque>//包含头文件voidprintdeque(const deque<int>& deq)//形参使用const，避免被修改{//const_iterator只读迭代器for(deque<int>::const_iterator it = deq.begin(); it != deq.end();++it){
        cout <<*it<<"|";}
    cout << endl;}voidtest(){
    deque<int> v;for(int i =0; i <5; i++){
        v.push_back(i +1);//尾部插入元素}printdeque(v);//1 2 3 4 5

    v.insert(v.begin()+1,2,100);//在第二个元素插入2个100printdeque(v);//1 100 100 2 3 4 5

    v.pop_front();//头部删除一个元素
    v.pop_back();//尾部删除一个元素printdeque(v);//100 100 2 3 4
    cout <<"-------------"<< endl;
    v.erase(v.begin());//删除第一个元素printdeque(v);//100 2 3 4

    deque<int>::const_iterator it = v.erase(v.begin()+1, v.end()-1);//删除从第二个元素到倒数第二个元素，返回下一个有效迭代器printdeque(v);//100 4

    v.insert(it,66);printdeque(v);//100 66 4

    v.clear();//清空容器}intmain(){test();return0;}