合肥做网站推荐 晨飞网络,郑州网站开发公司名称大全,网站后台密码忘记了怎么办 ftp进不去,建公司网站建设明细报价表文章目录 一、什么是优先级队列二、什么是容器适配器三、模拟实现优先级队列四、仿函数仿函数的优点 一、什么是优先级队列
优先级队列是一种容器适配器#xff0c;根据某种严格的弱排序标准#xff0c;它的第一个元素总是它所包含的元素中最大的。 优先级队列是作为容器适配… 文章目录 一、什么是优先级队列二、什么是容器适配器三、模拟实现优先级队列四、仿函数仿函数的优点 一、什么是优先级队列
优先级队列是一种容器适配器根据某种严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。 优先级队列是作为容器适配器实现的这些适配器是使用特定容器类的封装对象作为其底层容器的类提供一组特定的成员函数来访问其元素。元素从特定容器的“后面”弹出这被称为优先级队列的顶部。 其实优先级队列本质上就是数据结构中的堆在堆中可以随时插入元素并且只能检索最大的堆元素(优先级队列中位于顶部的元素)。
二、什么是容器适配器
容器适配器是一种可以对序列容器或关联容器的接口进行限制或扩展的类模板它可以提供一些不同于一般容器的功能。容器适配器本身不直接保存元素而是调用另一种容器来实现可以把容器适配器看作“它保存一个容器这个容器再保存所有元素”。容器适配器有三种stack栈queue队列和priority_queue优先队列。它们分别实现了后进先出LIFO先进先出FIFO和最大元素优先的逻辑。容器适配器的优点是可以简化和统一公共接口提高代码的可读性和可重用性。
三、模拟实现优先级队列
先看看类模板参数
template class T, class Container vectorT,class Compare lesstypename Container::value_type class priority_queue;这里默认容器是vectorCompare是仿函数这里的意思是默认构建大堆后面具体介绍。 templateclass T, class Container vectorT, class Compare LessTclass priority_queue{public:priority_queue(){}template class InputIteratorpriority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i (_con.size()-2)/2; i0; --i){adjust_down(i);}}void adjust_up(int child){Compare com;int parent (child - 1) / 2;while (child 0){if(com(_con[parent], _con[child]))//if (_con[parent] _con[child]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;size_t child parent * 2 1;while (child _con.size()){//if (child 1 _con.size() // // _con[child] _con[child 1])if (child 1 _con.size() com(_con[child], _con[child 1])){child;}//if (_con[parent] _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}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);}const T top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};这里默认是构造的大堆那我们怎么改成小堆这里就需要仿函数class Compare lesstypename Container::value_type 了。
四、仿函数 C仿函数是一种可以像函数一样被调用的对象也称为函数对象。它们的优点是可以保存状态支持多态以及提高效率。 仿函数的本质就是重载了()这个运算符的类。类名后面加上括号即可调用这个函数形式上和函数调用差不多但本质山任然是一个类所以称之为仿函数。 // 定义一个仿函数类
class Add {
public:// 重载()运算符int operator()(int a, int b) {return a b;}
};// 创建一个仿函数对象
Add add;
// 调用仿函数对象
int result add(3, 4); // result 7让我们回到优先级队列现在大家知道了less的意思了吧。 因为要把大堆修改成小堆只需要把向上调整和向下调整比较大小的左右参数互换一下位置不过在这些库都是封装好的情况下肯定不是我们想改就能改的所以我们可以在类外面自己定义一个比较方式传过去选择构建大堆还是小堆有点像C语言里的qsort()函数。
templateclass T
class Less
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
};
只要我们在实例化类的时候多加上一个Greatertypename Container::value_type即可。 例如priority_queueint, vectorint, greaterint q这里实例化了一个类对象q构造的即是小堆。
仿函数的优点
仿函数的优点主要还在在于它替换了C语言的函数指针我们不用在写繁杂的函数指针参数去使用回调函数不仅难写而且易错而是利用仿函数调用即可其实本质上仿函数和回调函数的用处一样的但是仿函数更加好用和简单。 此外仿函数本质上还是一个类通过模板可以使仿函数的使用更加多样化。
