网站开发费用属无形资产吗,word做网站框架,个人如何申请网站,四川专业网站建设费用###
容器适配器是将容器转换到其他容器自身不方便使用的地方#xff0c;但是就容器适配器其本身还是包装的容器#xff0c;所以这个类模板中各个接口的实现都是调用的容器的接口#xff0c;因为容器适配器可能适配多个容器#xff0c;所以这个类模板的模板参数中有一个参数…###
容器适配器是将容器转换到其他容器自身不方便使用的地方但是就容器适配器其本身还是包装的容器所以这个类模板中各个接口的实现都是调用的容器的接口因为容器适配器可能适配多个容器所以这个类模板的模板参数中有一个参数是代表容器类型的方便传参过来能及时改变
一、stack的模拟 这是这个类模板的模板那么我们也模拟这样实现首先解读T是stack里面存放的数据类型Container是stack里面包装的容器的类型默认是deque这是因为deque这个容器不仅兼顾了vector和list的基本接口并且deque相比于vector不需要浪费过多空间、头删头插的效率高相比于list的缓存利用率更高这个和deque的底层结构有关
###stack实现的代码
#pragma once
#includedeque
#includelist
#includevector
using namespace std;
namespace S
{templateclass T,class Container dequeTclass Stack{public:Stack()//调用Container的默认构造函数{}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}const T top()const{return _con.back();}void push(const T val T()){_con.push_back(val);}void pop(){_con.pop_back();}private:Container _con;};
}
首先stack对于vector、list、deque都能作为它们的适配器所以头文件包含了这几个容器
其次看到这个模板类的成员变量是一个Container代表容器类型这个容器类型默认为deque用这个类型去定义一个容器作为stack这个适配器的成员变量那么在实现stack的接口时就直接调用容器_con的接口
###测试
void test1()
{Stackint st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout 数据个数 st.size() endl;cout 是否为空 st.empty() endl;cout 栈顶数据 st.top() endl;st.pop();cout 数据个数 st.size() endl;cout 栈顶数据 st.top() endl;
}
注意在源文件中测试时要包含实现stack的头文件并且展开命名空间
###运行结果 二、queue的模拟
和stack大差不差注意它不能作为vector的适配器队列queue的头删出队列的接口要调用pop_front,而vector没有这个接口所以不能
###代码
namespace Q
{templateclass T ,class Container dequeTclass Queue{public:Queue(){}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}const T front()const{return _con.front();}const T back()const{return _con.back();}void push(const T valT()){_con.push_back(val);}void pop(){_con.pop_front();}private:Container _con;};
} ###测试
void test2()
{Queueint q;for (int i 1; i 5; i){q.push(i);}cout 是否为空 q.empty() endl;cout 数据个数 q.size() endl;cout 队头数据 q.front() endl;cout 队尾数据 q.back() endl;q.pop();//删除队头数据cout 队头数据 q.front() endl;
}
注意Queueint q可以显示传它的容器类型,stack也是一样
###运行结果 三、priority_queue的模拟
这个是优先级队列它的其他地方和queue一样就是队头的元素一直是最大的或者是最小的它的底层实现有堆的部分大堆的堆顶也就是最大的小堆的相反所以在实现时涉及到堆的向上和向下调正的方法
另外我们要写一份类模板这个类模板要求可以通过接收不同的模板参数来调正这个优先级队列是通过大堆实现的还是通过小堆实现的 这也是库里面的实现方法也就是说这个适配器的模板参数中要包含一个类型这个类型实例化出来的对象作为适配器的成员变量和_con类似,并且这个对象可以调用自己的函数来实现更大或者更小的比较这里需要使用仿函数
所谓的仿函数就是重载()的函数
直接看实现的代码来解读
###代码实现
namespace Q
{
//仿函数重载()templateclass Tclass Less{public:bool operator()(T x, T y){return x y;}};templateclass Tclass Greater{public:bool operator()(T x, T y){return x y;}};templateclass T,class Container vectorT,class Compare LessTclass Priority_Queue{public:Priority_Queue(){}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}const T top()const{return _con[0];}void AdjustUp(){int child _con.size() - 1;int parent (child - 1) / 2;while (child 0){if(_com(_con[parent],_con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void push(const T val T()){_con.push_back(val);AdjustUp();//向上调正建堆}void AdjustDown(){int parent 0;int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _com(_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;}}}void pop(){assert(_con.size());swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown();}private:Container _con;Compare _com;//调用仿函数就直接_com()相当于_com.operator();};}
第二个模板参数是vector这是因为里面有top的接口而vector也有
首先看到类Less和Greater里面有成员函数都是重载的的函数也就是仿函数包装成一个类是因为类可以作为类型传到模板参数中
看到优先级队列的类模板的实现第三个模板参数就是上面封装的类这个默认是Less在看到优先级队列的成员变量除了我们已近知道的_con,还有一个_com,这是通过Less实例化出来的对象这个对象可以直接在后面加上()来调用它自己的成员函数那么就可以来进行比较了
其他的接口很平常看到push和pop的接口首先push要进行向上调整里面使用_com()就是比较父节点和子节点父节点更小就和子节点交换实现大堆pop删除是先交换队头和队尾的数据再pop_back(),相当于删除了队头的节点之后再进行向下调整把次大的换到根节点处
只有涉及到父节点和子节点比较大小时才用到_com()这是因为这个函数的比较决定了是大堆还是小堆当传LessT时就是大堆传Greater时就是小堆(把更大的换到了子节点)
###测试
void test3()
{Priority_Queue int,vectorint pq;pq.push(1);pq.push(2);pq.push(3);pq.push(4);pq.push(5);pq.pop();cout 是否为空 pq.empty() endl;cout 数据个数 pq.size() endl;cout 队头数据 pq.top() endl;//也是堆顶数据
}
###运行结果 push走完 pop走完 可以观察到这就是按照堆的规则调整的
