网站开发讲座,保险网站哪个好,小内存wordpress,网站开发强制开启浏览器极速模式priority_queue priority_queue介绍逻辑实现框架调整算法adjust_up()adjust_down() 仿函数/比较函数仿函数特性 构造函数迭代器区间构造 完整优先级队列代码 priority_queue介绍
pri_que是一个容器适配器#xff0c;它的底层是其他容器#xff0c;并由这些容器再封装而来。类… priority_queue priority_queue介绍逻辑实现框架调整算法adjust_up()adjust_down() 仿函数/比较函数仿函数特性 构造函数迭代器区间构造 完整优先级队列代码 priority_queue介绍
pri_que是一个容器适配器它的底层是其他容器并由这些容器再封装而来。类似于heap的结构。默认为大堆。
逻辑实现
框架
namespace xty
{templateclass T, class Container vectorT, class Compare lessTclass priority_queue{bool empty(){return _con.empty();}size_t size(){return _con.size();}const T top(){return _con.front();}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}private:Container _con;};
}调整算法
因为优先级队列是以堆为结构实现的因此插入删除要保持堆的结构需要adjust_up()和adjust_down()两个算法。 建堆算法详细参考
adjust_up()
向上调整由堆底一直调整到堆顶。 void adjust_up(int child){int parent (child - 1) / 2;while (child 0){if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}adjust_down()
向下调整由堆顶一直向下调整直到叶子。 void adjust_down(int parent){size_t child 2 * parent 1;while (child _con.size()){if (child 1 _con.size() _con[child 1] _con[child]){child;}if (_con[child] _con[parent]){swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}else{break;}}}仿函数/比较函数
我们观察到库的模板参数给了三个其中第一个参数是数据类型第二个参数是模板容器第三个参数就是仿函数用户可以自己制定比较规则默认为大堆less。
templateclass T, class Container vectorT, class Compare lessT接下来我们实现一个比较类 templateclass Tstruct less{bool operator() (const T x, const T y){return x y;}};templateclass Tstruct grater{bool operator() (const T x, const T y){return x y;}};然后我们微调调整函数的逻辑将if的内容改成比较函数 因为使用方法酷似函数因此它叫仿函数 void adjust_up(int child){Compare com; //实例化比较函数int parent (child - 1) / 2;while (child 0){if (com(_con[child], _con[parent]))/*if (_con[child] _con[parent])*/{swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com; //实例化比较函数size_t child 2 * parent 1;while (child _con.size()){if (child 1 _con.size() com(_con[child 1], _con[child])){child;}if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}else{break;}}}仿函数特性
有了仿函数的功能后我们可以自己定义比较类型使程序设计更加灵活。
看下面一段代码 class Date{public:Date(int year 1900, int month 1, int day 1): _year(year), _month(month), _day(day){}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}friend ostream operator(ostream _cout, const Date d){_cout d._year - d._month - d._day;return _cout;}private:int _year;int _month;int _day;};void test_priority_queue2(){// 大堆需要用户在自定义类型中提供的重载//priority_queueDate q1;priority_queueDate, vectorDate, greaterDate q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 30));q1.push(Date(2018, 10, 28));cout q1.top() endl;}首先这段测试代码结果是唯一的 而如果我们增加另一种格式的代码呢 class PDateLess{public:bool operator()(const Date* p1, const Date* p2){return *p1 *p2;}};class PDateGreater{public:bool operator()(const Date* p1, const Date* p2){return *p1 *p2;}};void test_priority_queue2(){//priority_queueDate*, vectorDate*, PDateLess q2;priority_queueDate*, vectorDate*, PDateGreater q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 30));q2.push(new Date(2018, 10, 28));cout *(q2.top()) endl;}这段代码如果不写仿函数结果是不唯一的因为比较的是指针重写仿函数后答案就唯一了可以看见仿函数可以使我们比较数据更加灵活
构造函数
显然我们没有写构造函数程序并没有报错是因为
我们不写构造函数编译器会默认生成一个。而成员函数是自定义类型会调用自定义类型的构造函数所以程序没有问题运行。当我们写了构造函数之后编译器就不会再默认生成了需要我们自己写。
迭代器区间构造
因为自己显示写了构造函数编译器不再默认生成默认构造函数需要自己再显示补一个默认构造 //默认构造priority_queue(){}templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){Container _con;while (first! last){push(*first);first;}}完整优先级队列代码
namespace xty
{templateclass Tstruct less{bool operator() (const T x, const T y){return x y;}};templateclass Tstruct grater{bool operator() (const T x, const T y){return x y;}};templateclass T, class Container vectorT, class Compare lessTclass priority_queue{public:void adjust_up(int child){Compare com; //实例化比较函数int parent (child - 1) / 2;while (child 0){if (com(_con[child], _con[parent]))/*if (_con[child] _con[parent])*/{swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com; //实例化比较函数size_t child 2 * parent 1;while (child _con.size()){if (child 1 _con.size() com(_con[child 1], _con[child])){child;}if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}else{break;}}}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T top(){return _con.front();}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}priority_queue(){}templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){Container _con;while (first! last){push(*first);first;}}private:Container _con;};
}
