首页 > 代码库 > STL之容器适配器stack的实现框架
STL之容器适配器stack的实现框架
说明:本文仅供学习交流,转载请标明出处,欢迎转载!
一提到适配器(adapter)。我们就想到了早期用电话线上网所用的调制解调器,俗称“猫”。“猫”的作用是实现数模转化和模数转化,在client,它能够将电话的模拟信息转化为我们计算机能够接收的数字信息,所以猫相当于一个转换器。再举个更加好理解的样例来说明"适配器“的含义。相信在我们每一个人的家里都有插排,如果就这么一种情况。如今我们家里的墙壁上仅仅有一个三角的插口,而我们的电视却是两个口,怎么办?毫无疑问。我们能够接一个新的插排,该插排至少有两个孔,一个是用于连接墙壁上的三角的插口,一个则是提供给电视剧用的两口的插口。这样,我们就能够将新增加的中间用于转换的插排是一个适配器。
从上面的样例我们可以非常easy的得出:适配器可以对原始事物进行一次封装与修饰。并提供第二种接口。该接口可以更好地满足用户的需求。具有一定的专用性。
这样。我们就行介绍下stack这一容器适配器了。
之前我们已经介绍过三种主要的顺序容器,各自是vector、list和deque,这三种顺序容器的设计都会设计到迭代器的概念。STL要求不论什么一种容器都必须内置一个迭代器,假设连迭代器都没有内置,就谈不上”容器“的定义了。所以。stack仅仅是一个容器适配器,并非一个容器,由于stack不提供迭代器,所以在元素不弹出的前提下不可以遍历内部全部的元素。
学习过”数据结构“的人都知道栈,栈是一种后进先出或者说先进后出的数据结构,一个栈的插入和删除操和取值都仅仅能在栈顶进行。依据栈的性质,栈顶元素必定是最后一个进入的元素。依据这点,我们可以非常easy地得出一个结论:不论什么提供末端插入(push_back函数)、删除(pop_back函数)、訪问(back函数)都可以被stack容器封装与修饰。这里的封装指的是通过stack对象,你不能直接訪问被封装的底层容器了,所谓的修饰指的是stack在对底层容器做封装的同一时候。还提供了必要的接口。以满足用户的须要。
我们将被适配器封装的底层容器称为基础容器。
在我们所学过的顺序容器中,仅仅要能够提供末端的插入、删除和訪问操作。都能够作为stack适配器的基础容器。所以vector、list和deque都能够作为stack的基础容器,而stack默认的基础容器为deque容器。
对于一个stack,我们通常须要提供这几个接口函数:
(1)获取栈内当前元素的个数:size_type size();
(2)取栈顶元素(但并不弹出):T top();
(3)入栈:void push(const T &t);
(4)出栈:void pop();
(5)推断是否栈空:bool empty()。
假设想使用STL定义的容器适配器stack,须要引用stack头文件,即#include<stack>
以下给出stack适配器的实现代码:
#include<iostream> #include<deque> using namespace std;
/*******************stack适配器的定义**************/ template<class T,class Sequence=deque<T> > class stack { friend bool operator==(const stack&,const stack&);//friend函数是全局函数,不受private的限制 friend bool operator<(const stack&,const stack&);//类内声明。类外定义,定义是不加friend public: typedef typename Sequence::value_type value_type;//typename类型声明,元素类型 typedef typename Sequence::size_type size_type;//大小类型 typedef typename Sequence::reference reference;//引用声明 typedef typename Sequence::const_reference const_reference;//常引用声明 protected: Sequence c;//基础的底层容器 public: bool empty()const;//是否为空 size_type size()const;//大小 reference top();//取顶部元素 const_reference top()const; void push(const value_type &x);//压栈 void pop();//出栈 };
/******************各个函数接口的类外实现**********************/ template<class T,class Sequence> bool operator==(const stack<T,Sequence> &x, const stack<T,Sequence> &y)//推断两个适配器是否相等 { return x.c==y.c; } template<class T,class Sequence> bool operator<(const stack<T,Sequence>& x,const stack<T,Sequence>& y)//推断适配器x是否小于适配器y { return x.c<y.c; } template<class T,class Sequence> bool stack<T,Sequence>::empty()const//常成员函数类外定义须要加constkeyword { return c.empty(); } template<class T,class Sequence>//类外无需加默认形參 //假设写成size_type stack<T,Sequence>::size()const是错误的,由于size_type是在类内定义的,且typename最好也加上 typename stack<T,Sequence>::size_type stack<T,Sequence>::size()const { return c.size(); } template<class T,class Sequence> typename stack<T,Sequence>::reference stack<T,Sequence>::top()//底层实现是返回最后一个容器的元素 { return c.back(); } template<class T,class Sequence> typename stack<T,Sequence>::const_reference stack<T,Sequence>::top()const//top函数的重载 { return c.pop_back(); } template<class T,class Sequence> void stack<T,Sequence>::push(const value_type & x)//底层实现是向基础容器的尾部加入元素 { c.push_back(x); } template<class T,class Sequence> void stack<T,Sequence>::pop()//底层实现是将基础容器的尾部元素弹出 { c.pop_back(); }
參考资料:
[1]《STL源代码剖析 侯捷》
[2]《C++ primer 第4版》
STL之容器适配器stack的实现框架