c++的STL（3）-- deque容器

deque概述

deque的内存模型

注意:

1. deque的默认构造(和vector类似)

代码:

2. deque的有参构造(和vector类似)

代码:

3. deque容器在首部和尾部添加或者元素

代码:

deque概述

deque是一个双端队列，内部是使用数组进行实现的，其内部的空间和vector容器不同，其空间并不一定是连续的。
deque在开头和尾部添加元素都是非常快的，但是deque在中间插入元素是很慢的，因为需要进行元素移动。
deque可以也可以进行随机存取。

deque的内存模型

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

有读者可能会问，如果 map 数组满了怎么办？很简单，再申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧的空间。

注意:

鉴于deque的内存方式 -- 也就是存储数据的内存是不连续的，所以我们不能对deque中的数据使用指针进行访问。 -- 应该使用迭代器。(迭代器是容器内嵌的类，进行了处理)

例子:
int main(void) {deque<int> d1{1,2,3,4,5};d1.emplace_front(6);int* a = &d1[1];
/*++a;cout << "a=" << *a << endl;
*/--a;cout << "a=" << *a << endl;system("pause");return 0;
}
代码中我们使用初始化列表，在d1容器中存放了5个元素，然后使用emplace_back()在其前面插入一个数据6。

按照上面的内存模型，我们知道存储6的空间和存储1-5的空间不是连续的。我们取1的地址存放到指针a当中，对a++之后，打印a中的数据是2。但是如果进行a--，打印a中的数据会发现时一串非法数字。

这就是因为1前面的6和他们不存储在同一片内存并且不连续，当a--的时候访问的是存储1的前一个内存，但是这里存储的并不是6而是一个垃圾值。

但是你会发现我们对a++，就可以正确的访问，这是因为1-5的空间是连续的，对a++后面的空间存储的是2。虽然这样可以，但是还是不要使用指针直接访问deque中的元素，因为你无法确定从哪里开始内存就不连续了，会有风险。

表 deque 容器的成员函数
函数成员	函数功能
begin()	返回指向容器中第一个元素的迭代器。
end()	返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin()	返回指向最后一个元素的迭代器。
rend()	返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
size()	返回实际元素个数。
max_size()	返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-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() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。

要想使用deque容器，需要导入头文件#include <deque>

下面的知识点，如果和vector类似，那么只会给出代码，具体的知识点请看vector容器的那一节。

1. deque的默认构造(和vector类似)

代码:

#include <iostream>
#include <stdlib.h>
#include <deque>using namespace std;class Student {};int main(void) {/*deque<int> d1;deque<float> d1;deque<Student> d1;deque<Student *> d1;deque<int *> d1;*/system("pause");return 0;
}

2. deque的有参构造(和vector类似)

代码:

/*有参构造:方式一:  使用初始化列表  c++11之后支持deque<int> d1{ 1,2,3,4,5 };方式二:  初始化时指定元素个数deque<int> d1(10);  // 指定元素个数为10,并且只为默认值(此处为0)deque<int> d1(10,5);// 10个元素的值为5方式三:  使用指针(数组)int arr[] = { 1,2,3,4,5 };deque<int> d1(arr,arr+2); //  区间左闭右开，将arr数组的前两个元素放到d1中方式四:  使用其它deque的迭代器deque<int> d1{10,20,30,40,50};deque<int> d2(d1.begin(), d1.begin() + 2);  // 区间左闭右开，将d1容器的前两个元// 素放到d2中// 使用其它容器的迭代器vector<int> v1{ 1,2,3,4,5 };deque<int> d1(v1.begin(),v1.end());方式五:   调用拷贝构造函数deque<int> d1{10,20,30,40,50};deque<int> d2(d1);  // 将d1中的元素放到d2中
*/

3. deque容器在首部和尾部添加或者元素

在deque的首尾插入和删除元素都是很快的，在首部插入，它会再开辟一段空间来存放，所以也不需要移动元素。

代码:

/*deque<int> d1;1. 尾部添加:  push_back() , emplace_back();q1.push_back(1);q1.emplace_back(2);int a = 10;q1.push_back(a);q1.emplace_back(a);2. 尾部删除:  pop_back();q1.pop_back();3. 首部添加:  push_front() , emplace_front();q1.push_front(1);q1.emplace_front(2);int a = 10;q1.push_front(a);q1.emplace_front(a);4. 首部删除:  pop_front();q1.pop_front();添加元素时,在空间不够的时候，会开辟空间删除元素时不影响容器容量
*/

4. deque容器的元素个数 (和vector类似)

代码:

deque<int> q1{1,2,3,4,5};cout << "q1容器的元素个数:" << q1.size() << endl; // 输出5

5. deque在指定位置插入元素(和vector类似)

代码:

/*deque<int> d1;deque在指定位置插入元素:方式一:  使用insert()1. d1.insert(d1.begin(), 5);  在开始位置插入52. d1.insert(d1.begin(), 5,3); 在开始位置插入5个33. d1.insert(d1.begin(), {1,2,3,4,5}); 在开始位置插入列表中的数据4. deque<int> d2{ 1,2,3,4,5 };d1.insert(d1.begin(), d2.begin()+1,d2.begin()+3); 在开始的位置插入[d2.begin()+1,d2.begin()+3)范围内的数据,范围为左闭右开vector<int> v1{ 1,2,3,4,5 };deque<int> d1;d1.insert(d1.begin(), v1.begin(), v1.end()); // 将v1中的元素插入到d1的开始位置5. int arr[] = { 1,2,3,5,4 };d1.insert(d1.begin(), arr+1,arr+3); 在开始位置插入指针[arr+1,arr+3)范围(左闭右开)内的数据。(也就是数组中的第二个元素)方式二:  使用emplace()d1.emplace(d1.begin(), 5);  在开始的位置插入5在空间不够的时候，两种方式都会开辟空间
*/

6.deque容器元素的访问(和vector类似)

代码:

/*
deque<int> d1{1,2,3,4,5};
deque的元素访问:
1. 使用[]:d1[0] = 10;cout << d1[2] << endl;
2. 使用at():d1.at(1) = 5;cout << d1.at(1) << endl;
3. 使用front()访问第一个元素d1.front() = 100;cout << d1.front() << endl;
4. 使用back()访问最后一个元素d1.back() =  50;cout << d1.back() << endl;
*/

7. deque的迭代器(和vector使用方法是一样的)

至于迭代器的用法和vector是很类似的，此处就不在演示了。

8. deque容器删除元素(和vector类似)

代码:

/*deque<int> d1{1,2,3,4,5};deque删除元素:1. 使用erase()(1) d1.erase(d1.begin()); // 删除d1开始位置的元素(2) d1.erase(d1.begin(), d1.begin() + 2); // 删除迭代器区间[beg,end)内的元素，左闭右开的范围2. 使用clear()d1.clear()  // 删除所有的元素两者都不修改容器容量
*/

9.deque容器赋值(和vector类似)

代码:

/*deque<int> d1{1,2,3,4,5};deque赋值操作:使用assign()1. d1.assign(5,1);  // 使用5个1覆盖容器中的原来数据2. deque<int> d2{10,11,12,13,14,15}; d1.assign(d2.begin(), d2.end()); // 使用d2中的迭代器范围[beg,end)中的元素覆盖原有数据3. int  arr[] = { 1,2,3,4,5 };  // 使用指针[ptr1,ptrt2)中的元素覆盖原来数据d1.assign(arr, arr + 2);4. d1.assign({ 5,6,7,8,9 }); // 使用列表中的数据覆盖原来数据使用赋值运算符重载d1 = d2;   // 使用d2中的值覆盖原来数据assign在空间不够的时候，会开辟空间
*/