晋城市住建设局网站,wordpress去除评论表单,响应式网页模版,莱芜论坛莱芜都市网priority_queue priority_queue 简单介绍priority_queue 使用内置类型测试自定义类型测试 priority_queue 模拟实现仿函数#xff08;less、greater#xff09; priority_queue 简单介绍
优先级队列是一种容器适配器。类似于堆#xff0c;可以随时插入元素#xff0c;只能… priority_queue priority_queue 简单介绍priority_queue 使用内置类型测试自定义类型测试 priority_queue 模拟实现仿函数less、greater priority_queue 简单介绍
优先级队列是一种容器适配器。类似于堆可以随时插入元素只能检索优先级队列中位于顶部的元素。
priority_queue是作为容器适配器实现的容器适配器是对特定容器类封装作为其底层的容器。vector、deque符合priority_queue需求如果没有指定特定的底层容器默认使用vector。需要支持随机访问迭代器以便内部保持堆结构。
priority_queue 使用
在默认底层容器vector中使用堆算法将vector中的元素构成堆的结构所以priority_queue就是堆。 使用场景在需要用到堆的位置。priority_queue默认是大堆。
函数接口说明priority_queue()构造空的优先级队列priority_queue(first, last)迭代器范围构造优先级队列empty()判断优先级队列是否为空top()返回堆顶元素的const引用push(val)将val插入优先级队列中pop()删除堆顶元素
内置类型测试
void test_priority_queue()
{//默认是大堆 -- less less在sort中对应的是升序但是在priority_queue中建的大堆//priority_queueint pq;//仿函数greater控制建小堆priority_queueint, vectorint, greaterint pq;pq.push(5);pq.push(10);pq.push(3);pq.push(1);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;
}test2:
void test_priority_queue()
{vectorint v{ 3,2,7,6,0,4,1,9,8,5 };//默认大堆priority_queueint pq;for (auto e : v){pq.push(e);}cout pq.top() endl;//创建小堆priority_queueint, vectorint, greaterint pq1(v.begin(), v.end());cout pq1.top() endl;
}自定义类型测试
如果是自定义类型的数据用户需要提供大于或者小于的重载
class Date
{friend ostream operator(ostream _cout, const Date d);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);}private:int _year;int _month;int _day;
};ostream operator(ostream _cout, const Date d)
{_cout d._year - d._month - d._day;return _cout;
}void test_priority_queue()
{// 大堆需要用户在自定义类型中提供的重载priority_queueDate pq1;pq1.push(Date(2023, 8, 6));pq1.push(Date(2023, 7, 6));pq1.push(Date(2023, 6, 6));cout pq1.top() endl;// 如果要创建小堆需要用户提供的重载priority_queueDate, vectorDate, greaterDate pq2;pq2.push(Date(2023, 8, 6));pq2.push(Date(2023, 7, 6));pq2.push(Date(2023, 6, 6));cout pq2.top() endl;
}注意 如果自定义类型没有重载用于比较的符号 则程序运行错误。
priority_queue 模拟实现
priority_queue类模板实现借用了一个容器vector和两个仿函数less、greater。如果想进一步观察priority_queue的逻辑结构请点击该链接堆的实现
#include vector
#include assert.h// priority_queue---堆
namespace kpl
{templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}};templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}};templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue{public:// 创造空的优先级队列priority_queue(){}/*templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){ //这里可以不使用初始化列表//数据存入while (first ! last){_con.push_back(*first);first;}//向下调整建堆for (size_t i (_con.size() - 1 - 1) / 2; i 0; --i){AdjustDown(i);}}*/templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last): _con(first, last){// 将_con中的元素调整成堆的结构//向下调整建堆for (size_t i (_con.size() - 1 - 1) / 2; i 0; --i){AdjustDown(i);}}void push(const T data){_con.push_back(data);AdjustUP(_con.size() - 1);}void pop(){assert(!_con.empty());swap(_con.front(), _con.back());_con.pop_back();AdjustDown(0);}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}// 堆顶元素不允许修改因为堆顶元素修改可以会破坏堆的特性const T top()const{return _con.front();}private:// 向上调整void AdjustUP(int child){int parent (child - 1) / 2;while (child){if (_com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}// 向下调整void AdjustDown(int parent){size_t child parent * 2 1;while (child _con.size()){// 找以parent为根的较大的孩子if (child 1 _con.size() _com(_con[child], _con[child 1]))child 1;// 检测双亲是否满足情况if (_com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}private:Container _con;Compare _com;};
}仿函数less、greater 仿函数functor是一个能行使函数功能的类或结构体。它实际上是一个可调用的对象可以像调用函数一样来使用它传入参数并获得返回值。与普通函数不同的是仿函数可以保存状态信息并且可以被其他函数调用。为了成为一个仿函数类或结构体必须重载 operator() 运算符。在C中仿函数通常用于STL算法中的自定义排序、查找、过滤等操作。 test1:
//仿函数/函数对象
templateclass T
struct less
{bool operator()(const T left, const T right){return left right;}
};templateclass T
struct greater
{bool operator()(const T left, const T right){return left right;}
};int main()
{lessint lessFunc;cout lessFunc(1, 2) endl;cout lessFunc.operator()(1, 2) endl;cout lessint()(1, 2) endl;
}test2: 仿函数的匿名对象使用
int main()
{greaterint g;vectorint v{ 1,3,4,1,0 };sort(v.begin(), v.end(), g);//sort(v.begin(), v.end(), greaterint());//greaterint() -- 匿名对象for (auto e : v){cout e ;}cout endl;cout greaterint()(1, 2) endl;cout g(1, 2) endl;
}
