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中

  方式五:   调用拷贝构造函数
  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);  在开始位置插入5
 2. d1.insert(d1.begin(), 5,3); 在开始位置插入5个3
 3. 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)范围内的数据,范围为左闭右开
 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在空间不够的时候，会开辟空间
*/