济南高新区建设局网站,做公司网站 找谁做,如何计算网站pv,网站建设公司河南STL中的容器适配器 一、容器适配器1、什么是容器适配器2、STL标准库中的容器适配器 二、stack的模拟实现1、stack的简单介绍2、栈的模拟实现 三、queue的模拟实现1、queue的简单介绍2、queue的模拟实现 四、priority_queue的模拟实现1、priority_queue的简单介绍2、priority_qu… STL中的容器适配器 一、容器适配器1、什么是容器适配器2、STL标准库中的容器适配器 二、stack的模拟实现1、stack的简单介绍2、栈的模拟实现 三、queue的模拟实现1、queue的简单介绍2、queue的模拟实现 四、priority_queue的模拟实现1、priority_queue的简单介绍2、priority_queue的模拟实现 一、容器适配器
1、什么是容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。
例如我们常见的充电器就是一种适配器它将我们常用的220V交流电压转化为45V (或者其他更高的电压) 的直流电压来给我们的电子设备进行充电。
2、STL标准库中的容器适配器
虽然stack和queue priority_queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配
器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用dequepriority_queue默认使用了vector。 二、stack的模拟实现
1、stack的简单介绍
相关文档 stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类但这些容器类应该支持以下操作
empty判空操作back获取尾部元素操作push_back尾部插入元素操作pop_back尾部删除元素操作
标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器默认情况下使用deque。
2、栈的模拟实现
为了栈的通用性这里我们使用模板来进行模拟栈关于栈的底层容器这里我们选择vector来进行模拟实现。
templateclass T, class Container vectorT
class stack
{
public://栈的插入void push(const T val){//使用底层容器中尾插函数进行插入,栈只能进行栈顶插入和删除_con.push_back(val);}//栈的删除void pop(){//使用底层容器中尾删函数进行插入,栈只能进行栈顶插入和删除_con.pop_back();}//获取栈顶元素T top(){//返回底层容器中最后一个数据return _con.back();}//const 版本const T top() const{return _con.back();}//获取数据个数size_t size() const{//返回底层容器中数据的个数return _con.size();}//判空函数bool empty() const{//对底层容器进行判空return _con.empty();}
private://成员变量是一个容器创建的对象Container _con;
};三、queue的模拟实现
1、queue的简单介绍
相关文档 queue底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty检测队列是否为空size返回队列中有效元素的个数front返回队头元素的引用back返回队尾元素的引用push_back在队列尾部入队列pop_front在队列头部出队列
标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。
2、queue的模拟实现
为了queue的通用性这里我们使用模板来进行模拟queue关于queue的底层容器这里我们选择list来进行模拟实现。
templateclass T, class Container listT
class queue
{
public://队列的插入void push(const T val){//使用底层容器中尾插函数进行插入,队列只能进行队尾插入_com.push_back(val);}//队列的删除void pop(){//使用底层容器中头删函数进行删除,队列只能进行队头删除_com.pop_front();}//获取队头数据T front(){//返回底层容器中第一个数据return _com.front();}//const版本const T front() const{return _com.front();}//获取队尾数据T back(){//返回底层容器中最后一个数据return _com.back();}//const版本const T back() const{return _com.back();}//获取数据个数size_t size() const{//返回底层容器中数据的个数return _com.size();}//判空函数bool empty() const{//对底层容器进行判空return _com.empty();}
private://成员变量是一个容器创建的对象Container _com;
};四、priority_queue的模拟实现
1、priority_queue的简单介绍
相关文档 优先队列是一种容器适配器它其实就是我们数据结构中的堆,默认情况下priority_queue是大堆。
priority_queue底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作
empty检测容器是否为空size返回容器中有效元素个数front返回容器中第一个元素的引用push_back在容器尾部插入元素pop_back删除容器尾部元素
标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。
2、priority_queue的模拟实现
与前面的栈与队列一样priority_queue前两个模板参数都类似,但是priority_queue要有第三个模板参数这个参数表示按照什么方式进行比较即建立大堆还是小堆。
//第三个参数是比较方式需要传递一个仿函数来确定比较方式,默认传递的是lessT,表示建大堆
templateclass T, class Container vectorT, class Comper lessT
class priority_queue
{
public://获取堆顶数据const T top() const{//返回底层容器的第一个数据return _con.front();}//获取数据个数size_t size() const{//返回底层容器的数据个数return _con.size();}//判空函数bool empty() const{//判断底层容器是否为空return _con.empty();}//堆的插入void push(const T val){//从尾部插入_con.push_back(val);int child _con.size() - 1;//向上调整重新建堆AdjustUp(child);}//堆的删除void pop(){//检查堆是否为空assert(!_con.empty());//交换堆顶与最后一个数据swap(_con.front(), _con.back());//删除最后一个数据_con.pop_back();//从堆顶进行向下调整重新建堆AdjustDown(0);}private://向上调整算法void AdjustUp(int child){Comper com;int parent (child - 1) / 2;while (child 0){//这里使用了仿函数来判断建立什么堆//比较的位置_con[parent], _con[child]是不能换的if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}//向下调整算法void AdjustDown(int parent){Comper com;//默认左孩子更符合建堆的要求int child parent *2 1;while (child _con.size()){if (child 1 _con.size() Comper()(_con[child], _con[child 1])){child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}//成员变量是一个容器创建的对象Container _con;
};
