适配器模式--实现queue、stack、priority
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
先了解一下设计模式设计模式是程序员在软件开发过程中面临一般问题的解决方案。【类似于兵法】
如适配器模式本质是进行转换用现有的转换出用户想要的东西迭代器模式不暴露底层细节封装后提供统一的方式访问容器。
栈和队列就是通过适配器模式实现。栈或队列均可以用vector数组或者list链表来转换。故栈和队列虽然归类在容器但更适合叫容器适配器。
适配器模式
用list实现队列queue
//队列底层更适合用链表结构所以默认模板参数给list
template<class T, class Container = list<int>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.erase(_con.begin());
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
用vector实现栈stack
//stack可以用vector/list实现即底层可以为数组栈或者链表栈
//stack<int, vector<int>>;
//stack<int, list<int>>;
template<class T, class Container = vector<int>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
用deque实现栈stack/queue
stl库中stack和list是用双端队列deque来实现。因为vector和list都有各自的优缺点vector存在扩容的问题对于队列的头插头删操作效率低list不支持随机访问cpu高速缓存命中率低。而deque融合了上述两个容器的优点。
deque是个容器虽然名字叫做双端队列但它不是队列不需要符合先进先出。
它的底层为了避免扩容是由多个buffer数组构成统一由中控数组指针数组来管理可以实现头插尾插。
deque的缺点它的下标访问有一定的消耗没有vector效率高【deque要先找到在第几个buffer再算在这个buffer的第几个vector可以直接根据下标访问】中间插入删除没有list效率高【中间插入删除要进行数据挪动】。
但是用来做栈尾插尾删或者队列尾插头删的默认容器是不错的因为不用中间插入删除大量的头尾插入删除偶尔下标随机访问。
namespace yyq
{
#include<deque>
template<class T, class Con = deque<T>>
class stack
{
public:
stack()
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_back();
}
T& top()
{
return _c.back();
}
const T& top() const
{
return _c.back();
}
size_t size() const
{
return _c.size();
}
bool empty() const
{
return _c.empty();
}
private:
Con _c;
};
template<class T, class Con = deque<T>>
class queue
{
public:
queue()
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_front();
}
T& back()
{
return _c.back();
}
const T& back() const
{
return _c.back();
}
T& front()
{
return _c.front();
}
const T& front() const
{
return _c.front();
}
size_t size() const
{
return _c.size();
}
bool empty() const
{
return _c.empty();
}
private:
Con _c;
};
};
用vector实现priority_queue
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;
优先队列是一种容器适配器是用vector来适配的。实质上less是大堆greater是小堆根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。文档的位置是在queue这个容器下的。
仿函数函数对象
泛型编程的一种函数类模板它的对象是函数。需要重载函数调用运算符即operator()。
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
仿函数大小是1字节所以在传仿函数时加不加引用都可以
template<class T, class Compare>
//void BubbleSort(T* a, int n, const Compare& com)
void BubbleSort(T* a, int n, Compare com)//仿函数传不传引用都可以
{
for (int j = 0; j < n; ++j)
{
int exchange = 0;
for (int i = 1; i < n - j; ++i)
{
//if (a[i] < a[i - 1])
if (com(a[i], a[i - 1]))//less排升序greater排降序
{
swap(a[i - 1], a[i]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
}
在调用时传有名对象或者匿名对象都可以
yyq::less<int> lessFun;
int a[] = { 2, 3, 4, 5, 6, 1, 2, 4, 9 };
BubbleSort(a, sizeof(a) / sizeof(int), lessFunc);//有名对象
BubbleSort(a, sizeof(a) / sizeof(int), yyq::less<int>());//匿名对象
练习题 数组中的第K个最大元素
//方法1
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//优先级队列默认是大堆
//topK问题可以采用N大堆K小堆来解决
//此处采用N大堆
priority_queue<int> pq(nums.begin(), nums.end());
while(--k)
{
pq.pop();//走k-1次取到第k个
}
return pq.top();
}
};
//方法2
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//优先级队列默认是less->大堆,greater->小堆
//topK问题可以采用N大堆K小堆来解决
//此处采用K小堆
priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);//因为vector的迭代器是支持+的
for(size_t i = k; i < nums.size(); ++i)
{
if(pq.top() < nums[i])
{
//大于堆顶元素就先删除堆顶元素再插入
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}
};
模拟实现
初级-不带仿函数
#include <vector>
namespace yyq
{
template<class T, class Container = vector<T>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
//建堆 -- 向下调整
for (size_t i = ((_con.size() - 1) - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
//当孩子大于父亲交换两者位置
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
//如果孩子比父亲小就结束循环
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;//假设左孩子比右孩子大
while (child < _con.size())
{
//在右孩子存在的情况下如果右孩子比左孩子大就用右孩子
if (child + 1 < _con.size() && _con[child + 1] > _con[child])
{
++child;
}
//如果 孩子>父亲就交换
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
//插入数据是向上调整
adjust_up(_con.size() - 1);
}
void pop()
{
//不能直接删掉堆顶元素这样会破坏 堆的结构
//正确做法把堆顶元素和堆底元素进行交换然后pop
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);//要用向下调整
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
T& top()
{
return _con[0];
}
const T& top() const
{
return _con[0];
}
private:
Container _con;
};
}
带仿函数
<–大堆>–小堆
#include <vector>
namespace yyq
{
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
//建堆 -- 向下调整
for (size_t i = ((_con.size() - 1) - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
void adjust_up(size_t child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//当孩子大于父亲交换两者位置-->要写成小于号的逻辑 父亲<孩子
//if (_con[parent] < _con[child]))
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
//如果孩子比父亲小就结束循环
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
Compare com;
size_t child = parent * 2 + 1;//假设左孩子比右孩子大
while (child < _con.size())
{
//在右孩子存在的情况下如果右孩子比左孩子大就用右孩子
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
++child;
}
//如果 孩子 > 父亲就交换
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
//插入数据是向上调整
adjust_up(_con.size() - 1);
}
void pop()
{
//不能直接删掉堆顶元素这样会破坏 堆的结构
//正确做法把堆顶元素和堆底元素进行交换然后pop
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);//要用向下调整
}
const T& top() const
{
return _con[0];
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}
注意自定义类型若要调用仿函数less和greater时就要自己写好自定义类型的 <、> 等运算符重载。
用iterator实现reverse_iterator
rbegin相当于正向迭代器的end()rend相当于反向迭代器的begin()。反向迭代器++就是往前走正向迭代器的–反向迭代器–就是往后走正向迭代器的++。
#pragma once
template<class Iterator, class Ref, class Ptr>
class Reverse_iterator
{
public:
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(const Self& s) const
{
return _it != s._it;
}
private:
Iterator _it;
};
在vector和list模拟实现的代码中再添加上反向迭代器相关代码即可如下所示
template<class T>
class list
{
public:
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;//反向迭代器
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//反向const迭代器
//反向迭代器
reverse_iterator rbegin()
{
return iterator(end());//用匿名对象返回
}
reverse_iterator rend()
{
return iterator(begin());//用匿名对象返回
}
//反向const迭代器
const_reverse_iterator rbegin() const
{
return const_iterator(end());
}
const_reverse_iterator rend() const
{
return const_iterator(begin());
}
};