本文已收录至《C++语言》专栏！
作者：ARMCSKGT

---

---

前言

前面我们介绍了适配器模式中的反向迭代器，反向迭代器通过容器所支持的正向迭代器适配为具有反向迭代功能的迭代器，本节我们介绍STL中另一种适配器：容器适配器！

---

正文

容器适配器

---

前面我们提到过STL适配器模式，关于适配器的解释：STL适配器思想

适配器思想是利用已有的对象对其进行封装以满足我们的需要！

容器适配器与反向迭代器相似；容器适配器是对每个容器进行封装，以适合容器适配器的使用要求，只要被封装容器所提供的接口和功能满足容器适配器容器则可以使用，所以容器适配器是对另一个容器进行封装！

既然是封装容器，那么只要满足容器适配器容器的条件，则都可以作为底层容器，所以容器适配器的底层容器可以不固定！

在STL中适配器式容器有三个

• stack 栈
• queue 队列
• priority_queue 优先级队列(堆)
  
  这些容器有一个特性，都是使用线性表作为底层容器；所以，对于已经有满足条件的容器可以充当这个容器时，可以采用对象之间的组合封装进行合理使用。
  当然，这是大范围和小范围的概念，例如stack和queue都可以使用vector和list封装，因为list和vector所支持的功能大于stack和queue所需要的功能！

---

stack 栈

---

stack的使用

STL库为我们提供了 stack栈 容器，我们只需要声明头文件stack即可使用！
参考文档：stack

接口说明

• empty：判断栈是否为空
• size：获取栈元素个数
• top：访问栈顶元素(两个函数版本：分别为返回值为 引用 和 const引用)
• push：在栈顶插入一个元素(实际是容器尾插)
• pop：删除栈顶元素
• swap：stack提供的交换函数
• relational operators：关于stack支持的运算符(==，!=，>，<，<=，>=)
• swap(stack)：算法库中swap支持stack对象的交换

栈的思想是 先进后出(LIFO) ，栈在容器的一端进行插入和删除，只能访问栈顶元素，所以栈没有迭代器，接口也比较少！

栈的使用非常简单，常用的接口都是插入删除取元素等等，但stack先入栈的元素后出栈！

stack的模板参数有两个

• T：实例化数据类型
• Container：底层容器
  
  
  对于stack，我们可以指定容器进行实例化，如果不指定，则默认是 deque双端队列 ！

stack只有一个构造函数，那就是实例化一个栈对象！

所以说stack的使用非常简单，接下来我们把大部分接口都使用一遍大家就知道了！

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

int main()
{
	stack<int> st1; //实例化容器栈st1和st2
	stack<int> st2;
	for (int i = 1; i < 6; ++i) st1.push(i);
	st2.swap(st1);
	while (!st2.empty())
	{
		cout << st2.top() << " ";
		st2.pop();
	}
	cout << endl;
	return 0;
}

当然，我们也可以指定容器进行实例化！
注意：在指定底层容器时，传递的容器模板参数Container需要指定底层容器的实例化数据类型，与实例化stack数据类型保持一致!

#include <iostream>
#include <stack>
#include <vector>
#include <list>
using namespace std;

int main()
{
	stack<int,vector<int>> st1; //实例化栈st1 底层容器为vector<int>
	stack<int,list<int>> st2; //实例化栈st2 底层容器为list<int>
	for (int i = 1; i < 6; ++i)
	{
		st1.push(i);
		st2.push(6 - i);
	}
	cout << "st1：";
	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}
	cout << endl;
	cout << "st2：";
	while (!st2.empty())
	{
		cout << st2.top() << " ";
		st2.pop();
	}
	cout << endl;
	return 0;
}

但是两个stack如果实例化的容器不一样，则不能使用swap函数，因为底层调用的是封装容器的swap，类型会不匹配！

关于emplace函数，也是一种插入函数，但是其作用更广！

---

stack模拟实现

这里着重讲对栈的封装，关于栈的思想和算法学习：数据结构-栈

对于封装容器适配器 栈 所需要的容器函数

• push_back 尾插
• pop_back 尾删
• back 访问尾部元素
• empty 容器是否为空
• size 数据个数
  
  底层容器只要满足stack适配器所需的函数，那么就可以为其适配出一个容器适配器！
  stack的默认底层容器是 deque双端队列，当然也可以使用vector和list等线性容器！
  
  stack默认在容器尾部插入删除，在尾部操作对于适配的容器效率可能较高！
  库中之所以选择 deque 是因为其头尾操作效率较高，后面我们会简单介绍 deque ！

关于stack的封装实现，就是对其要求的几个函数进行封装，调用的都是底层容器的函数，所以也比较简单！

#pragma once
#include<iostream>
#include<deque>

namespace my_stack
{
	//stack是一个适配器模式，可以借助其他容器实现
	template<class T, class Container = std::deque<T>>//
	class stack
	{
		typedef stack<T, Container> _stack; //stack对象类型
	public:
		stack()
			:_con(Container())
		{}

		//尾插
		void push(const T& val) { _con.push_back(val); }

		//尾删
		void pop() { _con.pop_back(); }

		//取栈顶数据
		T& top() { return _con.back(); }
		const T& top() const { return _con.back(); }

		//数据个数
		size_t size() const { return _con.size(); }

		//是否为空
		bool empty()const { return _con.empty(); }

		//交换
		void swap(_stack& _s) { _con.swap(_s._con); };
	private:
		Container _con; //底层容器对象
	};
}

---

queue 队列

---

queue的使用

STL库为我们提供了 queue队列 容器，我们只需要声明头文件queue即可使用！
参考文档：queue

接口说明

• empty：判断队列是否为空
• size：查询队列元素个数
• front：查看队头元素(两个函数版本：分别为返回值为 引用 和 const引用)
• back：查看队尾元素(两个函数版本：分别为返回值为 引用 和 const引用)
• push：插入一个元素(插在队尾)
• pop：删除一个元素(从队头删除)
• swap：queue提供的交换函数
• relational operators：关于queue支持的运算符(==，!=，>，<，<=，>=)
• swap(queue)：算法库中swap支持queue对象的交换

队列是一种 先进先出(FIFO) 的思想，头删尾插，在STL中也是容器适配器，但受其规则限制，也没有迭代器！

queue的使用也很简单，与stack不同的是queue先插入的先出队！

queue的模板参数有两个

• T：实例化数据类型
• Container：底层容器

对于queue，我们可以指定容器进行实例化，如果不指定，则默认也是 deque双端队列 ！

queue也只有一个构造函数，那就是实例化一个队列对象！

queue的使用也非常简单，在实例化时也可以指定底层容器，只不过插入和删除元素的顺序不同，所以栈和队列根据不同场景使用即可！

#include <iostream>
#include <queue>
#include <list>
using namespace std;

int main()
{
	queue<char> q1; //实例化队列 默认deque容器
	queue<char, list<char>> q2; //实例化队列 底层容器list
	for (char i = 'a'; i <= 'z'; ++i)
	{
		q1.push(i);
		q2.push(i - 32);
	}
	cout << endl << "q1:";
	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}
	cout << endl << "q2:";
	while (!q2.empty())
	{
		cout << q2.front() << " ";
		q2.pop();
	}
	cout << endl;
	return 0;
}

注意

• 同样的，queue在指定底层容器后，不同容器实例化出的queue对象不能交换
• queue底层需要头删函数，对于不支持头删的容器不能适配和实例化(例如vector)

---

queue模拟实现

这里着重讲对队列的封装，关于队列的思想和算法学习：数据结构-队列

对于封装容器适配器 队列 所需要的容器函数

• push_back 尾插
• pop_front 头删
• empty 判断容器是否为空
• size 获取容器中元素个数
• front 访问头部元素
• back 访问尾部元素
  
  注意：队列要求容器支持尾插和头删，vector因为头删性能较差所以没有实现，对于不支持尾插和头删的容器将无法适配！

queue的默认底层容器是 deque双端队列，当然也可以使用list线性容器！

关于queue的封装，与stack一样，也是调用底层容器的接口，适配器本身只是封装，这里为了跟库保持一致，我们仍然使用deque作为默认底层容器！

#pragma once
#include<iostream>
#include<deque>

namespace my_queue
{
	template<class T,class Container = std::deque<T>>//也可以使用list链表头尾入出效率较高
	class queue
	{
		typedef queue<T, Container> _queue; //queue对象类型
	public:
		queue()
			:_con(Container())
		{}

		//尾插
		void push(const T& x) { _con.push_back(x); }

		//头删
		void pop() { _con.pop_front(); }

		//取尾部数据
		T& back() { return _con.back(); }
		const T& back() const { return _con.back(); }

		//取头部数据
		T& front() { return _con.front(); }
		const T& front() const { return _con.front(); }

		//数据个数
		size_t size() const { return _con.size(); }

		//是否为空
		bool empty()const { return _con.empty(); }

		//交换
		void swap(_queue& _q) { _con.swap(_q._con); }

	private:
		Container _con;
	};
}

---

priority_queue 优先级队列

---

优先级队列这个词大家可能没有听说过，但是 数据结构-堆 一定有所耳闻，没错，优先级队列就是堆，而且优先级队列也是容器适配器！

以上图片出自《STL源码剖析》

---

priority_queue的使用

STL库为我们提供了 priority_queue优先级队列 容器，我们只需要声明头文件 queue 即可使用！
参考文档：priority_queue

模板参数

priority_queue有三个模板参数：

• T：实例化数据类型
• Container：底层容器
• Compare：比较函数(仿函数-默认升序)
  
  
  注意：priority_queue要求Container底层容器迭代器支持随机访问，因为堆需要随时进行调整！

构造函数

priority_queue有两个构造函数：

• 默认构造：构造一个空对象
• 迭代器区间构造：通过迭代器区间的遍历元素插入priority_queue对象

实例演示

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

int main()
{
	priority_queue<int> pq1; //构造一个空堆

	int arr[] = { 9,10,1,2,4,6,5,3,8,7 };
	priority_queue<int> pq2(arr,arr+10); //迭代器区间构造

	return 0;
}

我们将堆调整过的序列以二叉树的形式画出来，可以发现是一个大堆，父节点总是比子节点要大；所以，默认情况下，priority_queue建大堆！


大堆：父节点大于子节点
小堆：父节点小于子节点


当然，我们也可以通过传递Compare比较函数的方式控制建堆方式！

//T表示实例化数据类型 对于用于比较的仿函数也需要传递比较的值类型T
priority_queue<T,less<T>> BigPile; //通过less仿函数比较建大堆
priority_queue<T, vector<T>,greater<T>> SmallHeaps; //通过greater仿函数比较建小堆

上面我们演示了建大堆，下面我们用greater仿函数建小堆！

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	int arr[] = { 9,10,1,2,4,6,5,3,8,7 };
	//通过迭代器区间构造并建小堆
	priority_queue<int, vector<int> ,greater<int>> pq(arr,arr+10);
	return 0;
}

这里需要注意的是，在priority_queue的模板参数列表，其顺序依次是 数据类型T，底层容器Container和比较函数Compare，Container和Compare都有缺省参数，但是如果我们需要指定比较函数，需要先指定底层容器，这是缺省参数的使用规定，否则按照顺序传参的话，我们的比较函数就传给底层容器参数Container了！

关于剩下的接口，使用起来就非常简单了，无非是出堆入堆或者取堆顶数据等等！

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

int main()
{
	//堆排序 - 降序输出
	int arr[] = { 9,10,1,2,4,6,5,3,8,7 };
	//迭代器区间构造	
	priority_queue<int> pq(arr,arr+10);
	pq.push(668); //插入一个最大元素668数字
	cout << "heap size:" << pq.size() << endl; //输出当前的元素数
	while (!pq.empty()) //循环取堆顶数据输出 - 呈有序序列
	{
		cout << pq.top() << " ";
		pq.pop(); //输出一个 出堆一个
	}
	cout << endl;
	return 0;
}

对于某些特殊场景，例如存入指针，但需要按指针所指向的值去比较的场景，就需要我们自己实现比较函数！

可以发现，存入指针的情况下，如果我们想按其地址存入的值进行比较，必须自己实现比较函数，否则默认按地址的大小进行比较！

---

priority_queue模拟实现

priority_queue属于容器适配器的一种，因为自身规则限制与栈和队列一样，无法遍历，没有迭代器，同时也不需要实现自己的具体功能，调用底层容器的函数接口就行了，不过因为堆比较特殊，需要具备 向上调整 和 向下调整 的能力，这个能力需要底层容器支持迭代器的随机访问，确保符合堆的规则！

这里主要介绍对底层容器的封装，关于堆的详细介绍：数据结构-堆

对于封装容器适配器 优先级队列 所需要的容器函数

• push_back 尾插
• pop_back 尾删
• empty 判断容器是否为空
• size 获取堆元素个数
• front 获取容器首元素(栈顶元素)

这里需要说明一下，大家可能看到容器适配器是能用尾插尾删来封装容器就不用头插头删，是因为尾上的操作相当于头部操作相对于大部分线性容器来说是性能较好的，例如vector没有头部操作(因为性能极差)，容器适配器想尽可能适配更多容器，所以会兼容容器中实现最多的接口进行统一！

基本框架及构造函数
我们是对容器的封装加持可以控制堆的大小，所以与库中保持一致，三个模板参数：

• 数据类型T
• 底层容器Container
• 比较函数Compare

关于priority_queue的框架设计和构造函数：

• priority_queue有两个构造函数，默认构造 和 迭代器区间构造 ！
  –对于默认构造，只需要初始化两个成员变量即可
  –对于迭代器区间构造，需要初始化成员变量后通过迭代器将值逐一插入容器中
• priority_queue底层默认容器是vector，其随机访问性能相对于deque来说要好一些！
• 我们使用命名空间封装容器，并在命名空间中实现两个仿函数作为默认比较函数供使用者选择，对于priority_queue默认的比较方式，我们使用less大堆作为缺省参数！

namespace my_Priority_queue //priority_queue命名空间
{
	//仿函数实现判断小于
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	//仿函数实现判断大于
	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	//通过仿函数可以自定义比较方法！相当于qsort传指针来说，方便易懂
	template<class T, class Container = std::vector<T>, class Comapre = less<T>>
	class priority_queue
	{
		typedef priority_queue<T, Container, Comapre> _priority_queue; //priority_queue对象类型
	public:
		priority_queue() //默认构造
			:_c(Container()) //初始化底层容器对象
			, _com(Comapre()) //初始化比较函数对象
		{}

		template <class InputIterator> //迭代器区间构造
		priority_queue(InputIterator first, InputIterator last)
			:_c(Container())
			, _com(Comapre())
		{
			while (first != last)
			{
				push(*first);
				++first;
			}
		}

	private:
		Container _c; //底层容器对象
		Comapre _com; //比较函数对象
}

关于仿函数： 仿函数是通过重载运算符 () 实现的，在一些涉及比较大小的函数例如sort排序和部分STL容器中会使用，通常less是小，greater是大，在使用时进行实例化就行了，之所以会有仿函数这样的语法，是因为C语言对于将函数作为参数传递十分不友好，C++使用仿函数传递参数极大的方便了函数作为参数进行传递的不足！

查询交换类
对于查询类无非就是三个函数：empty判空，size查询元素个数和top取栈顶元素
对于这些函数，我们直接调用底层容器通过的函数即可！

//查询元素个数
size_t size() const { return _c.size(); }

//取栈顶元素 返回const引用类型
const T& top() const { return _c.front(); }

//检查容器中是否为空
bool empty() const { return _c.empty(); }

//交换
void swap(_priority_queue& _pq) { _c.swap(_pq._c); }

注意：top不能随意修改，为了提高性能使用const引用，修改堆中任意元素都有可能破坏堆结构；而且除了swap其他的函数不会涉及修改数据，可以使用const修饰this指针保证容器安全！

插入删除类
堆的插入和删除都需要进行检查和调整以确保堆结构的完整！
对于大堆：父节点值大于子节点
对于小堆：父节点值小于子节点

​​
插入数据
对于数据的插入，尾插在容器中，然后通过随机访问特性对比父子节点进行向上调整；一旦向上调整过程中，父子节点满足关系了就break跳出(因为上面的堆元素一定是满足堆条件的)！

void push(const T& val) //插入数据
{
	_c.push_back(val); //尾插数据
	adjust_up(_c.size() - 1); //向上调整
}

向上调整

void adjust_up(size_t child) //向上调整
{
	size_t parent = (child - 1) / 2; //计算父节点下标
	while (child > 0)
	{
		if (_com(_c[parent], _c[child])) //调用仿函数比较
		{
			std::swap(_c[parent], _c[child]); //库函数交换父子元素
			child = parent; //更新子节点下标
			parent = (child - 1) / 2; //更新父节点下标
		} else break;	
	}
}

删除数据
删除数据的原理是删除堆顶数据，将堆顶数据与容器尾部数据交换，然后容器尾删进行向下调整，这样堆顶的数据就被删除且保证了堆的完整性，之所以不直接删除堆顶元素然后向上调整，向上调整的性能没有向下调整的性能优秀！

void pop() //删除堆顶数据
{
	assert//	
	std::swap(_c[0], _c[_c.size() - 1]); //堆顶数据与容器尾数据交换
	_c.pop_back(); //容器尾删淘汰堆顶数据
	adjust_down(0); //从堆顶开始向下调整
}

向下调整
对于向下调整也是一样的，如果父子关系满足条件则break，不满足则继续向下调整！

void adjust_down(size_t parent) //向下调整
{
	size_t child = (parent * 2) + 1; //确定子节点下标
	while (child < _c.size())
	{
		//左右子节点最大或最小的
		if (child + 1 < _c.size() &&_com( _c[child], _c[child+1]))  { ++child; }

		if (_com(_c[parent], _c[child])) //判断父子元素关系
		{
			std::swap(_c[parent], _c[child]); ///交换父子元素
			parent = child; //关系父节点下标
			child = (parent * 2) + 1; //更新子节点下标
		} else break; //满足则直接break
	}
}

这里有一个细节问题，我们通过父节点向下调整，一开始确定的子节点是左子节点，需要与通过计算与右节点对比出最符合条件的哪个与父节点比对，否则会出现问题！

priority_queue模拟实现完整源码

#pragma once
#include<iostream>
#include<vector>

namespace my_Priority_queue
{
	//仿函数实现判断小于
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	//仿函数实现判断大于
	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	//通过仿函数可以自定义比较方法！相当于qsort传指针来说，方便易懂

	template<class T,class Container = std::vector<T>,class Comapre = less<T>>
	class priority_queue
	{
		typedef priority_queue<T, Container, Comapre> _priority_queue; //priority_queue对象类型
	public:
		priority_queue()
			:_c(Container()) //初始化底层容器对象
			,_com(Comapre()) //初始化比较函数对象
		{}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			: _c(Container())
			, _com(Comapre())
		{
			while (first != last)
			{
				push(*first);
				++first;
			}
		}

		void push(const T& val)
		{
			_c.push_back(val); //插入数据
			adjust_up(_c.size() - 1); //向上调整
		}

		void pop()
		{
			std::swap(_c[0], _c[_c.size() - 1]); //堆顶数据与容器尾数据交换
			_c.pop_back(); //容器尾删淘汰堆顶数据
			adjust_down(0); //从堆顶开始向下调整
		}

		size_t size() const { return _c.size(); }

		const T& top() const { return _c.front(); }

		bool empty() const { return _c.empty(); }

		void swap(_priority_queue& _pq) { _c.swap(_pq._c); }

	private:
		Container _c;
		Comapre _com;

		void adjust_up(size_t child) //向上调整
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_com(_c[parent], _c[child]))
				{
					std::swap(_c[parent], _c[child]);
					child = parent;
					parent = (child - 1) / 2;
				} else break;
			}
		}

		void adjust_down(size_t parent) //向下调整
		{
			size_t child = (parent * 2) + 1;
			while (child < _c.size())
			{
				if (child + 1 < _c.size() &&_com( _c[child], _c[child+1])) { ++child; }
				
				if (_com(_c[parent], _c[child]))
				{
					std::swap(_c[parent], _c[child]);
					parent = child;
					child = (parent * 2) + 1;
				} else break;
			}
		}

	};
}

---

deque 双端队列

---

deque双端队列是stack和queue底层指定默认容器，其结构上的特殊设计决定了它只适合于头尾操作需求高的场景；双端队列 = vector + list，设计时就想汲取二者的优点，即下标随机访问和极致的空间使用，但鱼和熊掌不可兼得，在复杂结构的加持之下，双端队列趋于中庸，无法做到 vector 和 list 那样极致，因此实际中也很少使用，比较适合当作适配器的底层容器!

图片出自《STL源码剖析》

deque的使用

使用deque只需要声明deque头文件即可！
参考文档：deque

deque有两个模板参数，空间配置器Alloc我们暂时不管，只需要传递实例化模板参数T即可！

默认成员函数
deque有4个构造函数，三个初始化构造函数和一个拷贝构造

初始化拷贝构造：构造一个空双端队列，构造一个有n个值为val的双端队列，迭代器区间构造！

这里拷贝构造就不演示了，与其他容器基本相同！


deque支持赋值重载函数

迭代器部分
deque支持正向和反向迭代器，且deque的迭代器是随机迭代器，非常强大！

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

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	deque<int> dq(arr, arr + 10);

	deque<int>::iterator it = dq.begin(); //正向迭代器
	for (int i = 0; (it + i) != dq.end(); ++i)
		cout << *(it + i) << " "; //随机访问
	cout << endl;

	deque<int>::reverse_iterator rit = dq.rbegin(); //反向迭代器
	for (int i = 0; (rit + i) != dq.rend(); ++i)
		cout << *(rit + i) << " "; //随机访问
	cout << endl;
	return 0;
}

容量和数据访问类

接口说明

• size：获取元素个数
• max_size：获取当前deque对象可存储的最大元素数
• resize(n,val)：增加n个val值，如果 n<size() 则什么也不做，val有缺省值，为类型的默认值
• empty：判断当前deque是否为空
• shrink_to_fit：缩容，缩小到一个合适的范围
• [ ] ：下标随机访问，下标非法就报错
• at ：下标随机访问，下标非法就抛异常
• front ：获取头部元素的 引用 或 const引用 (根据实际场景由编译器调用)
• back ：获取尾部元素的 引用 或 const引用 (根据实际场景由编译器调用)

deque支持增加容器元素以及缩容，但我们极其不建议使用shrink_to_fit缩容，因为其底层的结构负责，缩容会造成更大的性能损失！

deque支持方便的下标随机访问，但这个随机访问并不代表其底层是连续的内存空间，会有一定性能损失，迭代器与此也有相同的问题！

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

int main()
{
	deque<int> dq(3, 668);
	cout << "size:" << dq.size() << endl;
	cout << "max_size:" << dq.max_size() << endl;
	cout << "empty:" << dq.empty() << endl;
	dq.resize(5, 888);
	for (int i = 0; i < dq.size(); ++i) cout << dq[i] << " ";
	cout << endl;
	for (int i = 0; i < dq.size(); ++i) cout << dq.at(i) << " ";
	cout << endl;
	cout << "dq front:" << dq.front() << endl;
	cout << "dq back:" << dq.back() << endl;
	return 0;
}

数据插删类

接口说明

• assign：重新分配，先情况deque中的原数据再分配数据，类似于 operator= 的功能，有两个版本：
  – 分配n个val值元素
  – 迭代器区间分配
  
  
• push_back：尾插
• push_front：头插
• pop_back：尾删
• pop_front：头删
• insert 任意位置插入，有三个版本：
  – 在指定的position迭代器位置插入一个val值，并返回新插入值位置的迭代器
  – 在指定的position迭代器位置插入n个val值
  – 在指定的position迭代器位置插入一个迭代器区间
  
  
• erase 任意位置删除，有两个版本：
  – 删除position迭代器所指向的元素并返回该迭代器的下一个指向的元素迭代器
  – 删除一个迭代器区间，返回这个区间的下一个元素迭代器
  
  
  swap：deque提供的交换函数，交换两个deque的底层数据
  clear：清空deque容器中的所有数据

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

void Print(const deque<int>& dq)
{
	for (const auto& x : dq) cout << x << " ";
	cout << endl;
}

int main()
{
	deque<int> dq(3,668);
	Print(dq);

	int arr[] = { 1,2,3 };
	dq.assign(arr, arr + 3);
	Print(dq);

	dq.pop_front();
	dq.pop_back();
	Print(dq);

	dq.push_front(128);
	dq.push_back(1024);
	Print(dq);

	dq.insert(dq.begin(), 2048); //相当于头插
	dq.erase(--(dq.end())); //相当于尾删
	Print(dq);

	dq.clear();
	Print(dq);

	return 0;
}

---

deque底层思想

抛开底层不谈，deque是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque底层是 vector + list 的思想，其想对标 vector和list，即想拥有vector那样随机访问的功能，又想如list一样，头尾删除轻松自如，但实际上并不是很突出，雨露均沾但并没有两者的优点极限！

deque底层组成

• 由一个一个的vector组成的数组buffer，buffer中存储数据
• 由list中的节点指向每一个buffer首地址，这是一个中控数组，控制每一个buffer，这个主控数组在底层叫map，但底层并不是map容器，只是名字相同

将二者结合起来，就得到了复杂的双端队列！

deque的扩容与buffer数组无关，只对中控数组map进行扩容，再将原中控数组中指向各buffer的指针拷贝过去即可！

deque随机访问实现

• (下标 - 前预留位) / 单个数组长度 = 对应小数组buffer在map中的位置
• (下标 - 前预留位) % 单个数组长度 = 数据在该buffer中下标位置

由扩容和随机访问的计算可以发现，单个数组buffer的大小需要固定，否则访问时计算会比较麻烦(冗余计算)，但长度定长后，又会引发中间位置插入删除效率低的问题；对此 SGI 版的 STL 选择牺牲中间位置插入，提高下标随机访问速度，令小数组定长，这也是将它作为 栈和队列 默认底层容器的原因之一，因为 栈和队列 不需要对中间进行操作！

deque迭代器结构
由于deque的中控数组只记录了每个buffer数组的起始位置，所以其设计也比较复杂！
迭代器含有以下成员对deque进行控制：

• cur指针：指向当前需要的数据位置
• first指针：指向 buffer 数组起始位置
• last指针： 指向 buffer 数组终止位置
• node指针：指向中控数组(当迭代器指向buffer临界区时，进行buffer切换)
  
  deque的迭代器支持随机访问，所以可以使用sort进行排序，但是其随机访问牺牲性能，不如直接导入vector排完序再导入deque！

简单了解了其底层结构，我们盘点一下deque缺点：

• 结构设计复杂，性能没有vector和list各种的优点极致
• 中间位置插入删除非常麻烦，可以通过对buffer扩容的方式解决，但是该操作会影响随机访问的性能
• 虽然支持随机访问，但是牺牲性能，所以不适合遍历，因为迭代器需要频繁检测是否移动某段小空间的边界，效率很低

通过上面的介绍我们发现，deque天生适合stack和queue的底层容器，不需要在中间位置进行插入和删除，所以底层默认使用deque，而因为其随机访问没有vector极致，所以priority_queue底层默认并不是deque，而是vector！(当然，我们也可以使用deque作为priority_queue底层容器，但是性能没有vector好)
因为deque结构复杂，且平时用处不多，所以我们简单了解即可，需要深究的同学可以参考 《STL源码剖析》 中对deque的讲解！

---

以上演示图片出自《STL源码剖析》

---

最后

本节容器适配器的讲解就到这里了，本节我们又介绍了STL适配器模式下的容器适配器，容器适配器的学习让我们对类和对象的封装又有了进一步的认识，类和类之间的组合应用有了初步的了解，最后我们学习了deque这个适配器容器的底层容器，了解了其底层结构的复杂和优缺点，这些将为我们后面的学习打下基础！

本次 <C++ STL容器适配器> 就先介绍到这里啦，希望能够尽可能帮助到大家。

如果文章中有瑕疵，还请各位大佬细心点评和留言，我将立即修补错误，谢谢！

🌟其他文章阅读推荐🌟
C++ <STL容器反向迭代器> -CSDN博客
C++ <STL之list模拟实现> -CSDN博客
C++ <STL之list使用> -CSDN博客
C++ <STL之vector模拟实现> -CSDN博客
C++ <STL之vector的使用> -CSDN博客
🌹欢迎读者多多浏览多多支持!🌹