deque容器

简要说明及其定义

deque容器即双端队列容器，擅长在序列头部和尾部添加或删除元素，不擅长在序列中间添加或删除元素，且deque容器可以根据需要修改自身容量大小，但deque容器存储时，并不能保证所有元素都存储到连续的内存空间中

当需要向序列两端频繁添加或删除元素时，应该首选deque容器，同样需要引用同名头文件< deque >

#include<iostream>
#include<deque>
using namespace std;

deque<int> d1;	//创建一个空deque容器
deque<int> d2(10);	//创建具有10个元素的deque容器
deque<int> d3(10,2);	//创建具有10个元素，且初值为2的deque容器
deque<int> d4(d2);	//以d2为模板拷贝构造一个deque容器

int a[]={1,2,3,4,5};
deque<int> d(a,a+2);
//拷贝构造一个装有其他类型容器中指定区域的元素的deque容器

容器提供的成员函数

函数成员 函数功能
begin() 返回指向容器中第一个元素的迭代器
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用
rbegin() 返回指向最后一个元素的迭代器
rend() 返回指向第一个元素所在位置前一个位置的迭代器
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
size() 返回实际元素个数
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 2^32-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()成员函数

deque容器迭代器

deque容器的迭代器类型是随机访问迭代器，相关成员函数有begin/end、rbegin/rend、cbegin/cend、crbegin/crend，具体可参见array和vector篇

迭代器的功能是遍历容器，在遍历的同时可以访问甚至修改容器中元素，但迭代器不能用来初始化空的deque容器（这一点和vector是一样的），故而如下代码错误：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>values;
    auto first = values.begin();
    *first = 1;		//该处错误
    return 0;
}

对于空的deque容器，可以通过push_back()、push_front()、resize()成员函数实现添加元素

此外，向deque容器添加元素时，deque容器会申请更多的内存空间，其包含的所有元素可能会被复制或移动到新的内存地址，导致之前创建的迭代器失效（这点和vector容器也是一样的）

访问deque容器

  1. 容器名[n]——可能越界【通用】
  2. at（）函数访问——性能较前者会有所损耗，但较安全【通用】
  3. front（）和back（）——返回deque容器中第一个和最后一个元素的引用

注：deque容器没有提供data（）函数，同时deque容器存储时不保证存储在连续空间中，故而应该尽可能避免用指针去访问deque容器中指定位置处的元素

添删元素

deque提供增删元素的成员函数如下：

成员函数 功能
push_back() 在容器现有元素的尾部添加一个元素，和 emplace_back() 不同，该函数添加新元素的过程是，先构造元素，然后再将该元素移动或复制到容器的尾部
pop_back() 移除容器尾部的一个元素
push_front() 在容器现有元素的头部添加一个元素，和 emplace_back() 不同，该函数添加新元素的过程是，先构造元素，然后再将该元素移动或复制到容器的头部
pop_front() 移除容器尾部的一个元素
emplace_back() C++11 新添加的成员函数，其功能是在容器尾部生成一个元素。和 push_back() 不同，该函数直接在容器头部构造元素，省去了复制或移动元素的过程
emplace_front() C++ 11 新添加的成员函数，其功能是在容器头部生成一个元素。和 push_front() 不同，该函数直接在容器头部构造元素，省去了复制或移动元素的过程
insert() 在指定的位置直接生成一个元素。和 emplace() 不同的是，该函数添加新元素的过程是，先构造元素，然后再将该元素移动或复制到容器的指定位置
emplace() C++ 11 新添加的成员函数，其功能是 insert() 相同，即在指定的位置直接生成一个元素。和 insert() 不同的是，emplace() 直接在容器指定位置构造元素，省去了复制或移动元素的过程
erase() 移除一个元素或某一区域内的多个元素
clear() 删除容器中所有的元素

在实际应用中，常用emplace()、emplace_front()和emplace_back()分别替代函数insert()、push_front()和push_back()

其中insert()可以有四种语法格式：insert（pos，elem）、insert（pos，n，elem）、insert（pos，first，last）以及insert（pos initlist），具体使用参见vector容器篇的说明

emplace系列函数参数说明：

  • emplace(pos,args)函数：pos为指定位置，元素将插入到该位置之前，args对应元素数据类型的构造函数参数
  • emplace_first(args)函数：将元素插入到容器头部，args对应元素数据类型的构造函数参数
  • emplace_back(args)函数：将元素插入到容器尾部，args对应元素数据类型的构造函数参数

总结

  • deque<数据类型> 数组名(数据个数，初始值)；【参数可省】
  • deque<数据类型> 数组名(另一个deque容器)；
  • deque<数据类型> 数组名(首地址，尾地址)；

  • begin（）/end（）：返回“开头/结尾+1”处的元素的正向迭代器

  • 前加r：返回“开头-1/结尾”的反向迭代器——rbegin（）/rend（）

  • 前加c：返回const类型的元素迭代器——cbegin()/cend(),crbegin()/crend()

  • 容器名[n]——可能越界
  • at（）函数访问——性能较前者会有所损耗，但较安全
  • front（）和back（）——返回deque容器中第一个和最后一个元素的引用
  • deque容器没有data（）函数，且存储空间不连续，不建议用指针
  • 增添元素：insert()、push_front()、push_back
  • 对应的emplace系列：emplace()、emplace_front()、emplace_back()
  • 删除元素：erase()【删除一部分】、clear()【清空容器】

代码实例

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    //初始化一个空deque容量
    deque<int>d;
    //向d容器中的尾部依次添加 1，2,3
    d.push_back(1); //{1}
    d.push_back(2); //{1,2}
    d.push_back(3); //{1,2,3}
    //向d容器的头部添加 0 
    d.push_front(0); //{0,1,2,3}
    //调用 size() 成员函数输出该容器存储的字符个数。
    printf("元素个数为：%d\n", d.size());
   
    //使用迭代器遍历容器
    for (auto i = d.begin(); i < d.end(); i++) {
        cout << *i << " ";
    }
    cout << endl;
    return 0;
}

输出结果为：

元素个数为：4
0 1 2 3



#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int>d{1,2,3,4,5};
    auto first = d.cbegin();
    auto end = d.cend();
    //常量迭代器不能用来修改容器中的元素值
    //*(first + 1) = 6;//尝试修改容器中元素 2 的值
    //*(end - 1) = 10;//尝试修改容器中元素 5 的值
    //常量迭代器可以用来遍历容器、访问容器中的元素
    while(first<end){
        cout << *first << " ";
        ++first;
    }
    return 0;
}

输出结果为：

1 2 3 4 5



#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int> d{ 1,2,3,4,5 };
    cout << "deque 首元素为：" << d.front() << endl;
    cout << "deque 尾元素为：" << d.back() << endl;
    //修改首元素
    d.front() = 10;
    cout << "deque 新的首元素为：" << d.front() << endl;
    //修改尾元素
    d.back() = 20;
    cout << "deque 新的尾元素为：" << d.back() << endl;
    return 0;
}

输出结果为：

deque 首元素为：1
deque 尾元素为：5
deque 新的首元素为：10
deque 新的尾元素为：20