STL容器适配器

欢迎来到本期节目- - -

STL容器适配器

适配器模式：

既然是容器适配器当然是适配容器的了，这里简单了解一下这些适配器通常会适配哪些容器：
栈通常默认适配双端队列deque，也可以使用向量vector或者链表list.
队列通常也默认适配双端队列deque，也可以使用链表list.
优先级队列通常是使用向量vector，也可以使用双端队列deque，但效率不如vector.

容器vector和list相信大家并不陌生，不多做介绍，这里我们来了解一下双端队列;

deque定义:

deque底层结构：
这里我把存放有效数据的数组空间简称_buff数组；
_buff数组的首地址将存储在中控数组中，迭代器维护_buff数组与中控数组的结构；
首个_buff数组的首地址放在中控数组的中间位置，头插时申请的_buff数组首地址往左边放，尾插申请的往右边放.

注意：

特性：

• 支持下标随机访问
• 支持高效头插/头删，尾插/尾删.

优势：

• 相比vector，头插/头删效率很高，即使是扩容，也不需要移动大量数据.
• 相比list，底层申请的是一段连续的空间，空间利用率高.

缺陷：

• 不适合遍历，遍历时，迭代器需要频繁地检查是否移动到_buff数组的边界，效率低下.
• 中间插入/删除效率极低

栈

定义：

特性：

• 栈中存储的元素满足"后进先出"原则.

入栈/出栈演示:

在STL中栈使用的容器默认是双端队列;
既然栈是一端插入/删除的线性结构，那么vector和list同样可以作为底层容器，为什么默认使用双端队列呢？
和vector相比，虽然随机访问差了一点，但是当插入数据时，deque扩容的代价比vector（移动大量数据）小；
和list相比，deque每次开的是一段连续空间，空间利用率高于list.
而栈又不需要遍历（即没有迭代器），deque发挥了长处，又避开了短处.

栈适配器模拟实现：

#pragma once
#include<iostream>
#include<deque>
using namespace std;
namespace my_room
{
	template<class T,class Container = deque<T>>
	class Stack
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()const
		{
			return _con.back();
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

应用场景：

• 回溯法
• 递归
• 深度优先搜索
• 括号匹配

队列

定义：

特性：

• 栈中存储的元素满足"先进先出"原则.

入队/出队演示：


在STL中队列使用的容器默认也是双端队列;
队列是一端删除、另一端插入数据的线性结构；
对于vector来说，头插/头删的效率低下，不推荐;
对于list来说，插入删除效率高效，但是如果频繁入队/出队容易生成内存碎片.
对于deque来讲头部/尾部插入删除效率高，内存利用率也高，故使用deque.

队列适配器模拟实现：

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

namespace my_room
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		T& front()
		{
			return _con.front();
		}
		const T& front()const
		{
			return _con.front();
		}
		T& back()
		{
			return _con.back();
		}
		const T& back()const
		{
			return _con.back();
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

应用场景：

• 广度优先遍历
• 缓冲区管理
• 任务调度
• 消息队列

优先级队列

定义：

特性：

• 结构中的元素会按照用户所期望的重要程度依次出队.
• 优先级队列的逻辑结构是堆，可以使用仿函数控制是大堆还是小堆，默认是大堆.

入队/出队演示：

STL中优先级队列默认使用vector，由于要支持向下调整算法，需要随机访问，所以不考虑list,
虽然vector扩容代价高于deque，但是该结构随机访问较频繁，相比于deque，vector随机访问弥补了扩容的短板，故默认使用vector做容器.

优先级队列适配器模拟实现：

#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace my_room
{

	template<class T>
	class Lessfunc
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
	template<class T>
	class Greaterfunc
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	template<class T, class Container = vector<T>, class cmpare = Lessfunc<T>>
	class priority_queue
	{
		void adjustdown(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && cmpare()(_con[child], _con[child + 1]))
				{
					child++;
				}
				if (cmpare()(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void adjustup(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0 && cmpare()(_con[parent], _con[child]))
			{
				std::swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
		}
	public:

		priority_queue()
		{}
		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: _con(first, last)
		{
			//调成堆结构
			for (int i = (_con.size() - 2) / 2; i >= 0; i--)
			{
				adjustdown(i);
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);

			adjustup(_con.size()-1);

		}
		void pop()
		{
			std::swap(_con.front(), _con.back());
			_con.pop_back();
			adjustdown(0);
		}

		const T& top()const
		{
			return _con.front();
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

注意：

应用场景：

• 操作系统的任务调度
• 贪心算法

希望本片文章对您有帮助，请点赞支持一下吧😘💕