文章目录C优先级队列和仿函数优先级队列的介绍和使用优先级队列的介绍优先级队列的使用仿函数什么是仿函数仿函数是函数吗仿函数的作用模拟实现优先级队列C优先级队列和仿函数优先级队列的介绍和使用优先级队列的介绍本质priority_queue是一种容器适配器底层通过封装其他容器默认vector并使用堆算法实现。数据结构逻辑上是一个堆默认是大堆最大元素在堆顶。操作特性插入元素push(x)时间复杂度 O(log n)删除堆顶pop()时间复杂度 O(log n)获取堆顶top()时间复杂度 O(1)只能访问堆顶元素不能遍历。默认行为使用lessT比较构造大堆即top()返回最大元素。底层容器要求支持随机访问迭代器如vector、deque。默认vector优先级队列的使用priority_queue定义在queue头文件中使用前需要包含queue。它有三个模板参数元素类型、底层容器类型和比较器类型。当只指定元素类型时底层容器默认为vectorT比较器默认为lessT因此默认建立的是大堆最大堆top()返回最大元素。若要建立小堆最小堆必须显式写出底层容器并将比较器指定为greaterTpriority_queueint,vectorint,greaterintpq;// 小堆也就是说建小堆时不能只写元素类型通常需要把第二、第三两个模板参数都写出来。函数说明priority_queue()构造空优先级队列priority_queue(first, last)用迭代器区间构造并建堆empty()判空size()返回元素个数top()返回堆顶元素 (最大/最小)push(x)插入元素 xpop()删除堆顶元素#includeiostream#includevector#includequeue#includefunctionalusingnamespacestd;voidtest1(){priority_queueintpq;// 默认大堆vectorintv{1,2,3,4,5};priority_queueint,vectorint,greaterintpq2(v.begin(),v.end());// 小堆pq.push(1);pq.push(2);coutpq.size: pq.size()endl;while(!pq.empty()){coutpq.top() ;pq.pop();}coutendl;cout小堆 pq2 输出: ;while(!pq2.empty()){coutpq2.top() ;pq2.pop();}coutendl;}在模拟优先级队列之前我们还得先搞明白一件事priority_queue 的第三个模板参数到底是怎么决定它建大堆还是小堆的这就绕不开 C STL 的仿函数了。仿函数什么是仿函数仿函数Functor也叫函数对象Function Object是 C 中一种特殊的类或结构体它重载了operator()使得这个类的对象可以像函数一样被调用。structAdd{intoperator()(inta,intb)const{returnab;}};intmain(){Add add;// add 是一个对象intradd(3,5);// 调用 add.operator()(3, 5)r 8}add是一个对象但写add(3, 5)看起来就像在调用函数。这就是“仿函数”名字的由来——模仿函数。仿函数是函数吗上面我们了解到仿函数的名字由来模仿函数那么我们就能够明确仿函数不是函数通过上述代码我们也能明确仿函数是一个可调用对象因为重载了operator()所以可以像函数一样被调用。那么为什么我们不直接去使用函数呢还要去搞一个仿函数我们的生活常识就告诉我们仿品没有真品好那么是不是说明仿函数就是C委员会那一群人拍着脑袋决定的呢为什么不直接使用函数呢因为普通函数没办法保存额外的信息除非使用全局变量或静态变量这就十分不灵活仿函数就是为了解决上述普通函数这一痛点下的产物所以这个是经过C委员会的委员们深思熟虑下才决定下来的。仿函数的作用可以携带状态普通函数无法保存额外的信息除非用全局变量或静态变量不灵活。仿函数可以在对象中保存成员变量每次调用时使用这些状态。可以作为模板参数实现策略模式例如priority_queue的第三个模板参数就是仿函数决定大堆还是小堆。性能更好易于内联仿函数的operator()通常定义在类内编译器容易内联比函数指针调用更快。类型安全可重载一个仿函数类可以有多个operator()重载适应不同参数。与 STL 无缝配合STL 中大量使用仿函数如less、greater、plus、minus等都是标准仿函数。模拟实现优先级队列经过上述对仿函数的了解现在我们就可以来模拟实现一个自己的priority_queue了。#pragmaonce#includevector#includecassert#includealgorithmusingstd::vector;usingstd::swap;namespacexhs{templatetypenameTstructLess{booloperator()(constTa,constTb)const{returnab;}};templatetypenameTstructGreater{booloperator()(constTa,constTb)const{returnab;}};templateclassT,classConvectorT,classComLessTclasspriority_queue{public:priority_queue():_con(),_com(){}templatetypenameInputIteratorpriority_queue(InputIterator first,InputIterator last):_con(first,last),_com(){intnstatic_castint(_con.size());for(inti(n-2)/2;i0;--i){AdjustDown(i);}}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}constTtop()const{assert(!_con.empty());return_con.front();}voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}voidpop(){assert(!_con.empty());swap(_con.front(),_con.back());_con.pop_back();AdjustDown(0);}private:// 向上调整voidAdjustUp(size_t child){size_t parent(child-1)/2;while(child0){// 如果父节点优先级低于子节点则交换if(_com(_con[parent],_con[child])){swap(_con[parent],_con[child]);childparent;parent(child-1)/2;}else{break;}}}// 向下调整voidAdjustDown(size_t parent){size_t childparent*21;size_t n_con.size();while(childn){// 找优先级更高的孩子默认 Less 下找较大的孩子if(child1n_com(_con[child],_con[child1])){child;}// 如果父节点优先级低于孩子则交换if(_com(_con[parent],_con[child])){swap(_con[parent],_con[child]);parentchild;childparent*21;}else{break;}}}private:Con _con;Com _com;};}完