stack适配器转换
template<class T ,class container = vector<int>>//container设置缺省值
class stack
{
public:void push(const T & x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;
};这里就实现了一个简单的迭代器 这里我们都是不手动写功能 而是依靠container容器库中自带的函数功能去实现
void test1()
{bit::stack<int, vector<int>> s;s.push(1);s.push(12);s.push(14);s.push(16);s.push(5);s.push(9);while (!s.empty()){int a = s.top();cout << a << " ";s.pop();}cout << endl;
}void test1()
{bit::stack<int, list<int>> s;s.push(1);s.push(12);s.push(14);s.push(16);s.push(5);s.push(9);while (!s.empty()){int a = s.top();cout << a << " ";s.pop();}cout << endl;
}这里一个两个栈的结果都一样
都是后进先出 但是底层却已经天差地别了
设计模式 是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结
以上的适配器就是一种设计模式 适配器模式的核心是转换
此外还有迭代器模式
如果没有迭代器的概念 以前数据结构的访问和修改方式由于各种数据结构的底层不同 结构也不同 所以想要访问 就要先了解其底层的结构设计 之后按照不同的底层来设计不同的访问方式
而迭代器 则提供了同一的访问方式 这样用起来学起来都很简单其次封装屏蔽了底层实现的细节
迭代器模式的核心是封装
我们这里所讲的栈和队列等适配器都是不提供迭代器 如果提供迭代器就会破坏这里的访问特性 如栈的后进先出 先进后出的特性
stack和queue 他们的默认适配容器是deque
接下来介绍模拟队列 和deque的结构
queue的适配容器与stack有差别 stack都可以用 但是我们的queue只能用list和deque
使用vector适配会报错 因为队列是队尾插入队头删除 而我们的vector在库中是不支持头删的 如果想要使用vector适配需要手动更改pop_front 为erase 这样就可以支持vector 但是效率会变低
template<class T, class container = deque<int>>
class queue//先进先出 且这里只能用deque和list 而stack都可以用
{
public:void push(const T& x){_con.push_back(x);}void pop()//vector不支持头删 只是没有直接支持头删 想要vector头删可以使用vector的erase 但是效率会变低{_con.pop_front();}const T& front(){return _con.front();//取尾 }const T& back(){return _con.back();//取尾}bool empty(){return _con.empty();}size_t size(){_con.size();}
private:container _con;
};这里相较于之前的stack模版没有了top函数 通过front 和back函数 返回队头 和队尾元素引用 并且使用的pop复用的是头删
测试
void queue1()//底层虽然改变 但是上层依旧变化不大
{bit::queue<int > q;q.push(1);q.push(3);q.push(5);q.push(7);q.push(9);q.push(10);while (!q.empty()){ cout << q.front() << " ";q.pop();}cout << endl;
}
deque介绍 双端队列
是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和 删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比 较高。deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组
deque在功能上来说 是一个vector和list的结合体
上图中可以看出vector和list各有长短 而且互补 所以就有人想要创建出一个结合体结构deque
deque的缺陷
如果在数组中间位置进行插入该如何插入
为了保证每个buff数组大小相同 所以也是需要挪动数据 这里的insert 和erase的速度是非常慢的 且[]访问的效率也不够高
[]访问偶尔还可以使用 大量的访问效率不高
但是deque的头尾删除很不错
deque的迭代器比普通迭代器更加复杂
这里deque一共有两个迭代器 start和finish 两者分别指向一段buff的开始和结束
start指向第一段buff的第一个位置 finish指向最后一段buff的最后一个位置 其中的cur正在指向那个位置 而node只想对应buff的中控数组位置 first和last则分别指向对应buff数组的开始和结束
在遍历时解引用就是*cur
而++就相当于++cur 在遍历当前buff数组 而当cur==last时
这时node就要起作用了 node走下一个为buff数组 同时跟新cur的位置等于first
deque头插：第一次头插时需要新开一个buff数组 
这里的-1不是指插入开头 而是插入到新开数组的结尾 这样start迭代器的位置也要进行改变
也就是说deque的第一个元素不一定buff数组的开头位置
因为第一个元素不一定是在满的buff数组 所以访问时不能简单的使用除和模
这里为了防止第一个在不满的buff数组 所以需要把第一个buff当作慢的去进行计算
接下来介绍优先级队列容器适配器 堆
他的默认适配容器是vector
void priority_queue1()//priority_queue 在默认情况下是大堆 大的优先出栈
{vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> pq;for (auto& e : v)pq.push(e);while (!pq.empty()){cout << pq.top() <<" ";pq.pop();}cout << endl;
}
除了vector容器 其他容器的内容也可以直接插入
void priority_queue1()//priority_queue 在默认情况下是大堆 大的优先出栈
{int v[] = {3,2,7,6,0,4,1,9,8,5};//这里数组也可以直接通过优先队列来初始化 也是对数组进行排序priority_queue<int>pq(v,v+sizeof(v)/sizeof(int));while (!pq.empty()){cout << pq.top() <<" ";pq.pop();}cout << endl;
}
这里默认都是大堆那么如何实现小堆的呢
要用小堆就要写第二个参数和第三个参数
void priority_queue1()//priority_queue 在默认情况下是大堆 大的优先出栈
{int v[] = {3,2,7,6,0,4,1,9,8,5};//那么如何实现小堆呢//这里比较怪 小堆使用的是greater<int>priority_queue<int,vector<int>, greater<int>>pq(v, v + sizeof(v) / sizeof(int));while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}这里使用的是仿函数 而且使用的是greater来使得大堆变为小堆
接下来实现priority_queue的模拟实现
首先实现push
template <class T,class container>//这里通过类模版可以同时比较多种类型的大小
class priority_queue
{
public:void adjust_up(int child){}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}private:container _con;
};在插入一个元素后 就要在这个元素的位置开始进行向上调整法 向上调整首先要确定父节点位置
且已知子节点位置 我们的逻辑上是一个二叉树 物理上是一个数组
不会的话可以那个值套一下 这里是parent = （child-1）/2 默认大堆 小于实现大堆
比较父节点与子节点的值 如果子节点的值比较大（这里实现的是大堆）那么交换父节点和子节点 之后 之后从子节点更新到父节点的位置 再次计算新的父节点位置再次进行比较大小 如果父节点大于孩子 则结束或者一直调整到根节点
template <class T,class container>//这里通过类模版可以同时比较多种类型的大小
class priority_queue
{
public:void adjust_up(int child)//堆的插入 物理上是一个数组 逻辑上是一个二叉树
{//这是一个向上调整法int parent = (child - 1) / 2;while (child > 0){if (_con[parent]< _con[child])//这里使用仿函数比较大小 这里是大堆 如果写小堆 就不用再改代码 直接传一个每一个mygreater就可以解决{swap(_con[parent], _con[child]);//这里孩子的值大于当前父亲的值 所以要进行交换调整child = parent;//之后再次进行判断 看是否符合父亲大于孩子parent = (child - 1) / 2;}else{break;}}
}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}private:container _con;
};这样就实现了堆的插入
接下来实现堆的删除
template <class T,class container>//这里通过类模版可以同时比较多种类型的大小
class priority_queue
{
public:void adjust_up(int child)//堆的插入 物理上是一个数组 逻辑上是一个二叉树{//这是一个向上调整法compare comfunc;int parent = (child - 1) / 2;while (child > 0){if (comfunc(_con[parent], _con[child]))//这里使用仿函数比较大小 这里是大堆 如果写小堆 就不用再改代码 直接传一个每一个mygreater就可以解决{swap(_con[parent], _con[child]);//这里孩子的值大于当前父亲的值 所以要进行交换调整child = parent;//之后再次进行判断 看是否符合父亲大于孩子parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}void adjust_down(int parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}if (_con[parent]< _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}private:container _con;
};这里首先通过已知的父节点来确定左子节点 如果右节点存在 那么比较左右节点大小确定最大节点
之后最大子节点与父节点进行比较 如果子节点更大那么交换位置 更新父节点位置 并确定新的左子节点位置并且重新比较 如果父节点大于子节点(建立大堆) 那么就可以停止 或者走到叶子节点也可以停止了 注意这里向下调整法中使用的类型是无符号类型
这些都是比较常规的成员函数
const T& top()
{return _con[0];
}size_t size()
{return _con.size();
}bool empty()
{return _con.empty();
}还有迭代区间去构造
template <class InputIterator>
priority_queue(InputIterator first , InputIterator last)
{while(first != last){_con.push_back(*first);++first;}//建堆//从倒数的第一个非叶子结点开始建堆for (int i = (_con.size()-1-1)/2 ; i >= 0 ;i--){adjust_down(i);}
}建堆法 是通过从第一个倒数的非叶子节点开始不断进行向下调整法建堆
接下来我们介绍仿函数
我们以前想要控制大堆变为小堆是通过改变大于小于号实现的 这里我们就需要仿函数 函数对象：重载了operator的类
这里看似是一个函数 但实际上是调用了operator（）（）的类
通过模版类 仿函数可以比较多种类型的大小
template <class T>//这里通过类模版可以同时比较多种类型的大小
class myless
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
int main()
{func f1;f1(10); //看起来是一个函数 但是本质上是一个对象myless<int> lessfunc;cout << lessfunc(12, 2) << endl;priority_queue1();return 0;
}这里我们来改造一下我们的类
template <class T>//这里通过类模版可以同时比较多种类型的大小
class myless
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
template <class T>//这里通过类模版可以同时比较多种类型的大小
class mygreater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};template<class T, class container = vector<T>,class compare = myless<T>>
class priority_queue
void adjust_down(int parent)
{compare comfunc;size_t child = parent * 2 + 1;while (child < _con.size()){if (child+1 < _con.size() && comfunc(_con[child] , _con[child + 1])){++child;}if (comfunc(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}void adjust_down(int parent)
{compare comfunc;size_t child = parent * 2 + 1;while (child < _con.size()){if (child+1 < _con.size() && comfunc(_con[child] , _con[child + 1])){++child;}if (comfunc(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}如果在仿函数比较中放的是指针类型 那么他们就会比较指针地址大小而不会直接比较指向内容的大小 这是我们不想看见的
这里可以再写一个特别的仿函数用来专门对指正类型的参数进行解引用比较 这样就可以达到效果了