C++入门篇(14)之适配器,仿函数 并简单实现队列和栈
文章目录
前言
在前面的几个章节中,博主陆陆续续地介绍了模板,以及
STL容器中的string和vector的线性物理结构使用,list的离散物理结构使用,并且从其底层原理进行了简单实现.
文章链接如下:
| 模板基础 | string的使用 | string的实现 |
|---|---|---|
| vector的使用 | vector的实现 | list的使用 |
| list的实现 |
而今天我们介绍什么呢?答曰:适配器,伪函数,stack的实现,queue的实现,以及priority_queue的实现,读者可能感到好奇了,为什么今天博主直接就开始讲解他们的实现而不是先讲解其使用呢?
我们先大致看看栈,队列和优先级队列的封装方法吧:
有没有发现什么?没错,这些方法博主在前面讲解其他容器时候,已经重复叙述过三遍,并且还进行了实现,所以博主这里就不再进行讲解怎么使用,而是主要讲讲怎么进行实现.
适配器
生活中我们也经常用到适配器(说的直白点就是一个插头),起着一个转换作用,即通过一定作用,把不适合的变成我们适合的.
百度百科定义为:适配器是一个接口转换器，它可以是一个独立的硬件接口设备，允许硬件或电子接口与其它硬件或电子接口相连，也可以是信息接口。比如：电源适配器、三角架基座转接部件、USB与串口的转接设备等
咦~,奇怪了,我们不是在讲解C++吗?怎么扯到了生活中的适配器了.博主这里首先介绍生活中的适配器,就是为了让大家知道,适配器的作用就是进行一个转换.
说完生活中的适配器,我们就讲讲C++的适配器吧,什么是c++的适配器呢?我们先看看其文档如何定义stack和queue的吧:
stack:
template <class T, class Container = deque<T> > class stack;
queue:
template <class T, class Container = deque<T> > class queue;
可以清晰看到,文档使用了两个模板参数,一个是T,一个是Container,其中Container默认是一个deque(既双端队列:支持首尾删插,效率达到O(1)).其封装的方法和前面我们讲解的首尾删插一模一样.
说到这里,读者们有没有已经猜到这个Container是干嘛的吗?如果还没有想到.博主这里再给大家一个小小的提示:
博主从最开始的数据结构的讲解,到后面容器的讲解,以至于到后面的手动实现,博主强调过一个概念,程序最好可以支持复用.什么意思呢?
比如链表阶段的insert()和erase();只要实现了它 ,那么后面的push_back(),pop_back(),push_front()和pop_front()就完全可以调用insert和erase;
再比如我们讲解类和对象之实现日期类的时候,只要实现了>和=重载,其他的任何比较操作都可以调用这两个进行实现,也就是说我们完全节约了代码,并且达到预期效率.
都提示到这里来了,还猜不到Container是用来干嘛的吗?哦?猜到了呀,哈哈,没错,Container就是我们用来进行复用的一个容器,也就是适配器.
stack的实现
在上面,博主讲解了Container**(适配器)**的作用,现在我们就实现stack吧.
①结构搭建
template <class T,class Container = deque<T> >
class stack
{
public:
private:
Container _con; //定义一个Container
};
②push数据
博主上面才讲解,Container的作用是为了干嘛?没错,复用!!!
void push(const T& x)
{
_con.push_back(x); //也就是我们直接调用Container的push_back方法
}
③pop数据
按照上面push的套路,我们如法炮制:
void pop(const T& x)
{
_con.pop_back(x); //也就是我们直接调用Container的pop_back方法
}
④size返回大小
size_t size()
{
return _con.size();
}
⑤empty判空
bool empty()
{
return _con.empty();
}
⑥top获取栈顶
const T& top()
{
return _con.back();
}
⑦总览结构
template<class T, class Container = deque<T>>
class stack
{
//Container 尾认为是栈顶
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
到此,一个可以满足栈的数据先入后出的特性的简单结构大致实现完成
队列的实现
何为队列:即满足数据特性为先入先出的结构.
现在我们同样利用适配器进行实现队列吧
①结构搭建
template <class T,class Container = deque<T> >
class queue
{
public:
private:
Container _con; //定义一个Container
};
②push数据
void push(const T& x)
{
_con.push_back(x); //也就是我们直接调用Container的push_back方法
}
③pop数据
按照上面push的套路,我们如法炮制:
void pop(const T& x)
{
_con.pop_front(x); //注意哦,这里我们用的是front了,因为这样才满足队列特性
}
④size返回大小
size_t size()
{
return _con.size();
}
⑤empty判空
bool empty()
{
return _con.empty();
}
⑥front获取队头
const T& front()
{
return _con.front();
}
⑦总览结构
template<class T, class Container = std::deque<T>>
class queue
{
//Container 尾认为是队尾 头认为是队头
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
stack和queue适配器注意事项
在上面,大家可能已经注意到了,在底层实现的时候,Container是直接调用头尾删插四个接口;
有小伙伴可能会问:因为我们默认给的是deque作为适配器,如果我们给其他容器呢,然后其他容器并不支持该接口怎么办?
答曰:**不支持就会报错!**因此,我们所给的适配器一定要保证有该接口;
那么哪些容器适合呢?vector和list以及deque,不过deque集合了vector和list两者的有点,所以我们一般用deque进行作为适配器.
伪函数
通过其名字,我们可以知道,这一定不是函数,但是又一定和函数有关系.那么我们便看看什么是伪函数吧.
在文档的定义中,伪函数本质其实是一个类模板,只不过在该类里面重载了操作符(),以致于在使用伪函数对象时候,看起来就像函数调用
比如我们定义一个less伪函数
template <class T>
struct less
{
bool operator()(const T& x,const T& y)
{
return x<y;
}
};
现在我们进行调用
int x = 10;
int y = 20;
less<int> Less;
if(Less(x,y)) cout<<"yes!";
else cout<<"No!!";
可以知道,其结果为
Yes;
现在知道了伪函数是什么,我们就开始实现堆结构(即优先级队列)了
优先级队列
何为优先级队列?其实本质上就是一个堆,在数据结构章节,博主在堆的定义与实现----堆结构以及排序其中讲解过.
而我们看看文档对优先级队列的定义:
template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> >
class priority_queue;
有没有发现什么?没错,优先级队列相当于栈和队列来说,其模板又多了一个参数ComPare,而后面的typename Container::value_type>其实就是类型T;也就是说,priority_queue多了一个仿函数,其作用就是用来建立堆的时候确认是大堆还是小堆.
建堆时候(一般用数组),主要有两个方法,分别是:向上调整和向下调整.现在我们开始实现堆结构;
优先级队列的实现
①结构搭建
其底层本质上是一个数组,因此只需要给一个vector就行;
但是值得注意的是,C++这里有个小缺陷,就是传入的仿函数如果是less,说明是大堆,如果是grater,说明是小堆.
template <class T, class Container = vector<T>,class Compare = less<T> >
class priority_queue
{
public:
private:
Container _con;
};
②向上调整法
之前已经介绍过,不再多说
void adjustup(size_t child)
{
less<T> L;
while(L(_con[(child-1)/2],_con[child]))
{
swap(_con[(child-1)/2],_con[child]);
child = (child-1)/2;
}
}
③push数据
堆的push数据,便需要用到上面的向上调整算法:
void push(const T& x)
{
_con.push_back(x);
adjustup(_con.size()-1); //传入插入数据的位置索引,方便调整数据
}
④向下调整
同样的,这里不再细说,直接上代码:
void adjustdown(size_t parent)
{
int child = parent*2+1;
less<T> L;
while(child<_con.size())
{
if(child+1 < _con.size() && L(_con[child],_con[child+1])) child++;
if(L(_con[parent],_con[child]))
{
swap(_con[parent],_con[child]);
parent = child;
child = paparent*2+1;
}
else break;
}
}
⑤pop数据
对于pop数据来说,也就是删除堆顶的元素(即第一个元素),按照堆的逻辑,与最后一个交换,然后删除最后一个元素即,最后对堆顶元素向下调整
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjustdwon(0);
}
⑥获取堆顶
const T& top() const
{
return _con[0];
}
⑦获取数量
size_t size()
{
return _con.size();
}
⑧判空
bool empty()
{
return _con.empty();
}
⑨总览结构
template <class T, class Container = vector<T>,class Compare = less<T> >
class priority_queue
{
public:
void adjustup(size_t child)
{
less<T> L;
while(L(_con[(child-1)/2],_con[child]))
{
swap(_con[(child-1)/2],_con[child]);
child = (child-1)/2;
}
}
void push(const T& x)
{
_con.push_back(x);
adjustup(_con.size()-1); //传入插入数据的位置索引,方便调整数据
}
void adjustdown(size_t parent)
{
int child = parent*2+1;
less<T> L;
while(child<_con.size())
{
if(child+1 < _con.size() && L(_con[child],_con[child+1])) child++;
if(L(_con[parent],_con[child]))
{
swap(_con[parent],_con[child]);
parent = child;
child = paparent*2+1;
}
else break;
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjustdwon(0);
}
const T& top() const
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
总结
到此,这篇文章大抵叙述结束,而主要讲解了适配器和伪函数是个怎么回事,以及并运用了一下.希望成功为大家解惑