作者今天上午模拟实现了Cstl的queue晚上实现priority_queue后写下了这篇博客prority_queue也是一个容器适配器不过它的底层是用数组来实现的即默认为vector容器它还多了第三个模板参数一个用于改变比较方式的类通过设置不同的类能实现大根堆或者小根堆1. 仿函数的使用12345678templateclassTstructless{booloperator()(constT x,constT y)const{returnx y;}};1234templateclassT,classContainer std::vectorT,classCompare lessTclassMyPriorityQueue{public:比如这样实例化一个对象MyPriorityQueueint q; 第二个和第三个模板参数以及默认给出那么q对象中有一个成员Compare _com的类型就为lessT类型_com是一个lessT类型的对象比较两个int类型的变量时直接_com(a, b)就会调用运算符重载函数去比较2. 向上调整算法时父节点左右孩子也作比较123456789101112131415161718intchild parent * 2 1;while(child n){if(child 1 n _com(_con[child], _con[child 1])){child;}if(_com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}以大根堆为例首先要保证堆的父结点大于子结点作者先对两个子节点进行比较挑出一个更大的这样保证了在父子结点交换后被交换上去的子节点一定比另一个子节点大3. 为什么仿函数的运算符重载函数要设置为const成员函数12345678templateclassTstructless{booloperator()(constT x,constT y)const{returnx y;}};比如实例化一个const MyPriorityQueueint q;对象那么q对象的成员变量不能被修改即Compare _com其实是const Compare _com那么一个const对象在调用它的成员函数时无法调用非const成员函数而operator本身作为比较逻辑是不会修改对象的所以要加上const修饰this指针4. top()和pop()需要对元素个数做检查1234567891011121314151617181920voidpop(){assert(size() 0);std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();if(size() 1){AdjustDown(_con.size(), 0);}}T top(){assert(size() 0);return_con[0];}constT top()const{assert(size() 0);return_con[0];}为了防止删除空vector或者获取空vector里的数据从而造成非法访问需要严格保证进行top获取堆顶元素或者删除堆顶元素的时候保证堆非空5. explicit关键字 修饰函数的作用1234explicitMyPriorityQueue(constCompare com Compare()): _com(com){}explicit防止了实参的隐式类型转换因为隐式类型转换会带来代码可读性的问题以及误写出代码时不好排查6. MyPriorityQueue仿函数类对象 构造函数存在的意义1234explicitMyPriorityQueue(constCompare com Compare()): _com(com){}用仿函数类对象 来构造 MyPriorityQueue是为了适配各种仿函数类因为除了作者写的greaterint和lessint以外还会有带状态变量的仿函数类123456789101112131415templateclassTstructMyComp{intflag;// 构造时传入 flagMyComp(intf) : flag(f) {}booloperator()(constT a,constT b)const{if(flag 1)returna b;// 大堆elsereturna b;// 小堆}};比如MyPriorityQueueint, std::vectorint, MyComp q1(MyComp(1));q1是大根堆因为构造MyComp时状态为1比较时会走flag1的逻辑MyPriorityQueueint, std::vectorint, MyComp q2(MyComp(2));q2是小根堆因为构造MyComp时状态不为1比较时会走else的逻辑7. 命名空间防止与stl里面的函数或类发生冲突自定义的less模板类与std库里面的less模板类同名了所以为了解决同名冲突给lessgreaterMyPriorityQueue 放在一个命名空间中那么可以用 命名空间名::来指定less或者其它同名变量、类、函数等是哪个命名空间里的防止命名冲突的发生总体实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110#pragma once#include vector#include cassertnamespaceMyPriorityQueueModule{templateclassTstructless{booloperator()(constT x,constT y)const{returnx y;}};templateclassTstructgreater{booloperator()(constT x,constT y)const{returnx y;}};templateclassT,classContainer std::vectorT,classCompare lessTclassMyPriorityQueue{public:// 为了支持带状态的比较器explicitMyPriorityQueue(constCompare com Compare()): _com(com){}voidAdjustUp(intchild){intparent (child - 1) / 2;while(child 0){if(_com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}voidpush(constT x){_con.push_back(x);AdjustUp(_con.size() - 1);}voidAdjustDown(intn,intparent){intchild parent * 2 1;while(child n){if(child 1 n _com(_con[child], _con[child 1])){child;}if(_com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}voidpop(){assert(size() 0);std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();if(size() 1){AdjustDown(_con.size(), 0);}}T top(){assert(size() 0);return_con[0];}constT top()const{assert(size() 0);return_con[0];}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;Compare _com;};}测试代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include iostream#include vector#include MyPriorityQueue.hpp// 不写 using namespace// 带状态比较器structMyComp{intflag;MyComp(intf) : flag(f) {}booloperator()(inta,intb)const{if(flag 1)returna b;elsereturna b;}};intmain(){// 大根堆明确写MyPriorityQueueModule::std::cout 大根堆;MyPriorityQueueModule::MyPriorityQueueint q1;q1.push(3);q1.push(1);q1.push(5);q1.push(2);q1.push(4);while(!q1.empty()) {std::cout q1.top() ;q1.pop();}std::cout std::endl;// 小根堆std::cout 小根堆;MyPriorityQueueModule::MyPriorityQueueint, std::vectorint, MyPriorityQueueModule::greaterint q2;q2.push(3);q2.push(1);q2.push(5);q2.push(2);q2.push(4);while(!q2.empty()) {std::cout q2.top() ;q2.pop();}std::cout std::endl;return0;}测试结果./test大根堆5 4 3 2 1小根堆1 2 3 4 5到此这篇关于C中priority_queue模拟实现的文章就介绍到这了