STL容器适配器

欢迎来到本期节目- - -

STL容器适配器

适配器模式：

在C++中，适配器是一种设计模式，有时也称包装样式；

通过将类自己的接口包裹在一个已存在的类中，使得因接口不兼容而不能在一起工作的类能在一起工作；

也就是将一个类的接口转换成用户期望的.

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

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

deque定义:

双端队列是限定在两端插入/删除的线性表;

同时是一种具有栈和队列性质的抽象数据类型；

可以在任意一端出队/入队；

deque底层结构：
这里我把存放有效数据的数组空间简称_buff数组；
_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;};
}