做异地送花网站,网站建设常用单词,直通车优化推广,最近大事件新闻目录
介绍#xff1a;
一#xff0c;queue结构的设计
二#xff0c;priority_queue结构设计
三#xff0c;stack结构设计 介绍#xff1a;
适配器 适配器是一种设计模式#xff0c;而设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计的总结
一queue结构的设计
二priority_queue结构设计
三stack结构设计 介绍
适配器 适配器是一种设计模式而设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计的总结该模式是将一个类的接口转换成另一个类的接口。比如我们常用的交流适配器、电源插口适配器等如下图 容器模板 模板的使用可以帮助我们接收万能类型平常我们最多用的也就是普通类型的使用其实模板也可接收容器类型并像函数缺省参数一样进行缺省参数的使用即函数参数传递的是对象而模板传递的是类型使用如下 template class T int, class Container vectorT //第一个匹配普通类型默然类型为int第二个为容器类型默认类型为vectorT//......... 这里省略了具体的类模板或函数模板 在C标准库中有一些常用的容器适配器。容器适配器是将容器经过特定的设计完成特定的功能如queue队列结构、stack栈结构、priority_queue优先队列结构等。这里都需要传入特定的容器将其接口经过特定的修改使其具有独特的功能。 这里需注重强调一下容器适配器不是容器因此它没有迭代器只有容器才有迭代器。因此容器适配器不支持范围for等底层用迭代器实现的语法结构。 一queue结构的设计 我们先来观察queue的底层实现结构如下图 这里我们实现队列机制很简单这里我们直接用Container容器接口功能即可在编译阶段时对其进行实例化具体逻辑解说请看下面 //封装容器类型Container可以使用容器内的所有接口功能这里我们不用容器类型的管底层是如何实现的 templateclass T int, class Container std::dequeT//模板缺省值的使用跟函数缺省值一样 class queue { public: //下面直接使用容器中的接口功能即可唯一要注意的是容器类型中必须存在此接口 void push(const T x T()) { con.push_back(x); } void pop() { con.pop_front(); } const T front() { return con.front(); } const T back() { return con.back(); } const size_t size() { return con.size(); } bool empty() { return con.empty(); } private: Container con; //在编译阶段对其进行实例化调用时会调用其的构造函数 }; 二priority_queue结构设计 priority_queue底层用堆数据结构实现我们先观察以下类型接口 上图中第一个参数T表示数据类型第二个参数表示容器类型不说明时默认为vectorT类型第三个参数用来说明建大堆还是小堆不说明时默认为lessT类(默认 “ ”第一个参数小于第二个参数)建大堆要想建小堆需要“ 大于 ”即greaterT类 (默认 “ ”第一个参数大于第二个参数)。 这里的第三个参数跟sort排序算法的第三个参数效果相同都是用来控制功能效果。不同的是这里传递的是类less或greater的类类型即greaterT或lessT而sort的第三个参数是类less或greater的函数对象即greaterT()或lessT()。 在设计这方面的结构前我们先了解以下仿函数。仿函数其实就是在类中重载一个“ () ” 的函数此函数通常也叫函数对象即仿函数或函数对象是一个定义了含有 operator() 成员函数的类且该函数可以像普通函数一样被调用。 这里需说明的是从本质上来讲仿函数其实是一个类而不是一个函数。它是一种行为类似函数的对象可以像普通函数那样调用有参数、有返回值。以下代码设计了一个仿函数
#include iostream
using namespace std;
class A
{
public:bool operator()(int a, int b) {return a b;}
private:int a;int b;
};
int main()
{A X;cout X(5, 6) endl; //直接使用类对象调用//等效于以下代码cout X.operator()(5, 6) endl;return 0;
} 实现此适配器跟实现堆结构一样这里唯一要注意的是要运用第三个参数控制大堆结构和小堆结构默认情况传递less建大堆。具体的代码细节和相关注意点如下 template class T class less { public: bool operator()(const T x, const T y) { return x y; } }; template class T class greater { public: bool operator()(const T x, const T y) { return x y; } }; template class T int, class Container std::vectorT, class Compare lessT class priority_queue { public: void Adjustup(Container c) //向上调整算法建堆 { int child c.size() - 1; int parent (child - 1) / 2; //注意: 这里不能使用Container::iterator it;这里使用模板类的成员必须指定具体类型才可使用编译器识别不了具体指类型还是静态变量 //编译器这里是分开编译的先编译模板后编译实例化然后两个地方合在一起 //当编译到模板这块还不知道Container是什么具体类型无法使用迭代器模板都存在这个问题 //这里可以使用template来说明是其类型进行推演等到实例化然后再去里面取 //不用template可用auto直接万能接收类型等编译到实例化时进行确定 auto it c.begin(); //这里不用函数和类因此不能使用模板直接auto识别即可 //例如: typedef std::vectorT::iterator iterator; 错误编译器识别不出,一样的原理 while (parent 0 comp(*(it parent), *(it child))) { std::swap(*(it child), *(it parent)); child parent; parent (child - 1) / 2; } } void Adjustdown(Container c) { //向下调整算法建堆 int parent 0; int child parent * 2 1; auto it c.begin(); while (child c.size()) { if (child 1 c.size() comp(*(it child), *(it child 1))) { child; } if (comp(*(it parent), *(it child))) { std::swap(*(it child), *(it parent)); parent child; child parent * 2 1; } else { break; } } } priority_queue() { } template class InputIterator//与上同理直接使用万能推演编译到这块时会根据后面进行推演 priority_queue(InputIterator first, InputIterator last) :c(first, last) { for (int i (c.size() - 1) / 2; i 0; i--) { Adjustdown(c); } } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } const T top() const { return c.front(); } void push(const T x) { c.push_back(x); Adjustup(c); } void pop() { std::swap(c.front(), c.back()); c.pop_back(); Adjustdown(c); } private: Container c; Compare comp; }; 三stack结构设计 这里的stack实现机制与queue结构逻辑一样直接套用容器类型模板运用其接口功能实现专门结构的功能即可。代码如下 templateclass T, class Container std::dequeT class stack { public: void push(const T x T()) { con.push_back(x); } void pop() { con.pop_back(); } const T top() { return con.back(); } const size_t size() { return con.size(); } bool empty() { return con.empty(); } private: Container con; };
