温州网站关键词,好用的种子搜索引擎,中国建设银行个人网站登录,成都wap网站建设文章目录 使用方法Compare仿函数一些场景模板参数和函数参数 本篇总结优先级队列
使用方法
首先在官网查看它的一些用法
template class T, class Container vectorT,class Compare lesstypename Container::value_type class priority_queue;从… 文章目录 使用方法Compare仿函数一些场景模板参数和函数参数 本篇总结优先级队列
使用方法
首先在官网查看它的一些用法
template class T, class Container vectorT,class Compare lesstypename Container::value_type class priority_queue;从它的介绍可以看出也是一个用到了容器适配器的容器这里不同于stack和queue的适配器这里使用的是vector作为它的适配器也是用了模板来实例化但是多了一个Compare的概念关于Compare后面来引入
具体用法
Priority queue Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.
This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).
Priority queues are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are popped from the “back” of the specific container, which is known as the top of the priority queue.
The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall be accessible through random access iterators and support the following
从上面的英文中可以很明显的获取到信息它的用法和堆非常类似因此对应的接口设计也很像下面用实验来简单使用一下
#include iostream
#include queue
using namespace std;int main()
{priority_queueint pq;pq.push(3);pq.push(2);pq.push(1);pq.push(4);while (!pq.empty()){cout pq.top() ;pq.pop();}return 0;
}上面是对优先级队列的简单使用从中可以看出在队列中添加了3,2,1,4四个元素但是最后输出的确实4,3,2,1证明它确实是和堆是一样的那么基于这个原理就可以对它进行模拟实现了具体实现如下
// Version1--初级版本
#include iostream
#include vector
using namespace std;namespace my_priority_queue
{templateclass T, class Container vectorintclass priority_queue{public:bool empty(){return _con.empty();}size_t size(){return _con.size();}const T top(){return _con.front();}void adjust_up(int child){int parent (child - 1) / 2;while (child 0){if (_con[parent] _con[child]){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child 1] _con[child]){child;}if (_con[parent] _con[child]){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}private:Container _con;};
}整体来说实现难度不大只是需要对于向上和向下调整算法要熟悉有了这两个算法解决问题并不难但是这样的实现虽然可以适配前面的测试用例但是并不是库内实现的方法库内的实现还有一个Compare的概念
Compare仿函数
对于库内的函数只能实现降序排序很明显库内不可能只支持降序输出那么如何控制降序输出
库中定义的仿函数默认是less与之对应的还有greater如果使用greater就将是升序输出
int main()
{priority_queueint,vectorint,lessint pq1;pq1.push(3);pq1.push(2);pq1.push(1);pq1.push(4);cout 降序排列: endl;while (!pq1.empty()){cout pq1.top() ;pq1.pop();}cout endl;priority_queueint, vectorint, greaterint pq2;pq2.push(3);pq2.push(2);pq2.push(1);pq2.push(4);cout 升序排列: endl;while (!pq2.empty()){cout pq2.top() ;pq2.pop();}cout endl;return 0;
}// 输出结果
降序排列:
4 3 2 1
升序排列:
1 2 3 4那么这个less和greater到底是什么由此引出下面仿函数的概念
在前面实现的Version1的实现中并没有实现这个功能这是由于在建堆的时候建立的是大堆还是小堆已经限定了但是在实际的应用中这里不应该被限定应该根据实际情况创建对应的堆但是代码逻辑只能根据大于和小于来判断由此引出可以使用仿函数来实现这个功能
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;}
};上面就是对于仿函数的定义其实从中可以看出仿函数其实就是一个只有一个函数的类里面定义了运算符重载而当程序执行到需要进行比大小的时候就可以借助这个运算符重载得出结论进而执行这样就实现了改变大小于关系的函数
根据这个原理就可以实现下面的过程
// Version2
// 头文件
#include iostream
#include vector
using namespace std;namespace my_priority_queue
{templateclass T, class Container vectorint, class Compare Lessclass T class priority_queue{public:bool empty(){return _con.empty();}size_t size(){return _con.size();}const T top(){return _con.front();}void adjust_up(int child){Compare com;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 x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){Compare com;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(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}private:Container _con;};
}// main.c文件
#include iostream
#include queue
#include priority_queue.h
using namespace std;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;}
};void test1()
{my_priority_queue::priority_queueint, vectorint, Lessint pq1;pq1.push(3);pq1.push(2);pq1.push(1);pq1.push(4);cout 降序排列: endl;while (!pq1.empty()){cout pq1.top() ;pq1.pop();}cout endl;my_priority_queue::priority_queueint, vectorint, Greaterint pq2;pq2.push(3);pq2.push(2);pq2.push(1);pq2.push(4);cout 升序排列: endl;while (!pq2.empty()){cout pq2.top() ;pq2.pop();}cout endl;
}int main()
{test1();return 0;
}具体的指向演示如下 一些场景
其实仿函数的应用场景很多这里说比较基础的场景
例如算法库中存在的sort排序函数其实也是有仿函数的存在的
template class RandomAccessIteratorvoid sort (RandomAccessIterator first, RandomAccessIterator last);template class RandomAccessIterator, class Comparevoid sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);于是可以利用这些函数实现效果
void test2()
{Lessint com;int arr[] { 7,6,5,4,3,9,8,6 };int sz sizeof(arr) / sizeof(arr[0]);sort(arr, arr sz, com);for (auto ch : arr){cout ch ;}cout endl;Greaterint comp;sort(arr, arr sz, comp);for (auto ch : arr){cout ch ;}cout endl;
}模板参数和函数参数
对比模板参数和函数参数
// 模板参数
templateclass T, class Container vectorint, class Compare Lessclass T
my_priority_queue::priority_queueint, vectorint, Greaterint pq;// 函数参数
sort(arr, arr sz, Lessint());对于这里需要注意的是模板参数内传的是类的名字而函数传参传的是对象因此上面的写法其实是匿名对象的写法
