北京制作网站报价,建自己的零售网站,企业内部管理系统网站建设,安徽建设工程建设信息网站priority_queue是一个拥有权重概念的queue#xff0c;允许底部加入新的元素#xff0c;头部删除旧的元素#xff0c;以及审视元素数值的操作priority_queue带有权重的概念#xff0c;即元素按照权重进行排列#xff0c;而不是按照插入队列的顺序进行排序。要求权值高者在前…priority_queue是一个拥有权重概念的queue允许底部加入新的元素头部删除旧的元素以及审视元素数值的操作priority_queue带有权重的概念即元素按照权重进行排列而不是按照插入队列的顺序进行排序。要求权值高者在前缺省情况下priority_queue使用max_heap完成而max_heap物理层面是基于vector逻辑层面表现像complate binary treemax_tree用于实现priority_queue的按照权值高低自动递增排序的特性priority_queue定义完整列表
priority_queue底层使用vector在加上堆的处理规则priority_queue不被归纳为容器 而是容器适配器
#include iostream
#include vector#ifdef __STL_USE_EXCEPTIONS
#define __STL_TRY try
#define __STL_UNWIND(action) catch(...) { action; throw; }
#else
#define __STL_TRY
#define __STL_UNWIND(action)
#endiftemplate class T,class Sequence std::vectorT,class Compare std::lesstypename Sequence::value_type
class priority_queue{
public:typedef typename Sequence::valuetype value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;
protected:Sequence c; //底层容器Compare comp; //元素大小的比较标准
public:priority_queue() : c (){}explicit priority_queue(const Compare x) : c() ,comp(x){}//以下使用的make_heap()、push_heap()、pop_heap()都是泛型算法//注意 任意一个构造函数都立刻在底层容器内产生一个implicit representation heap//指代比较器templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last,const Compare x):c(first,last),comp(x){std::make_heap(c.begin(),c.end(),comp);}//没有指代比较器templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last):c(first,last){std::make_heap(c.begin(),c.end(),comp);}bool empty()const{return c.empty();}size_type size() const{return c.size();}const_reference top()const{return c.front();}void push(const value_type x){__STL_TRY{//push_heap 是泛型算法先利用底层的push_back()将新的元素推入末端再重新排列heapc.push_back(x);//push_heap 是泛型算法std::push_heap(c.begin(),c.end(),comp);}__STL_UNWIND(c.clear());}void pop(){__STL_TRY{//pop_heap是泛型算法从heap中取出一个元素并不是整整将这个元素弹出而是重排heap//需要使用底层vector的pop_back()取得被弹出的元素std::pop_heap(c.begin(),c.end(),comp);c.pop_back();}__STL_UNWIND(c.clear());}};
priority_queue没有迭代器
priority_queue的所有元素进出是有规则限制的只有queue的顶端元素(权值最高者)才可以被外界使用priority_queue不提供遍历的功能因此无迭代器
测试用例
#include iostream
#include vector#ifdef __STL_USE_EXCEPTIONS
#define __STL_TRY try
#define __STL_UNWIND(action) catch(...) { action; throw; }
#else
#define __STL_TRY
#define __STL_UNWIND(action)
#endiftemplate class T,class Sequence std::vectorT,class Compare std::lesstypename Sequence::value_type
class priority_queue{
public:typedef typename Sequence::value_type value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;
protected:Sequence c; //底层容器Compare comp; //元素大小的比较标准
public:priority_queue() : c (){}explicit priority_queue(const Compare x) : c() ,comp(x){}//以下使用的make_heap()、push_heap()、pop_heap()都是泛型算法//注意 任意一个构造函数都立刻在底层容器内产生一个implicit representation heap//指代比较器templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last,const Compare x):c(first,last),comp(x){std::make_heap(c.begin(),c.end(),comp);}//没有指代比较器templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last):c(first,last){std::make_heap(c.begin(),c.end(),comp);}bool empty()const{return c.empty();}size_type size() const{return c.size();}const_reference top()const{return c.front();}void push(const value_type x){__STL_TRY{//push_heap 是泛型算法先利用底层的push_back()将新的元素推入末端再重新排列heapc.push_back(x);//push_heap 是泛型算法std::push_heap(c.begin(),c.end(),comp);}__STL_UNWIND(c.clear());}void pop(){__STL_TRY{//pop_heap是泛型算法从heap中取出一个元素并不是整整将这个元素弹出而是重排heap//需要使用底层vector的pop_back()取得被弹出的元素std::pop_heap(c.begin(),c.end(),comp);c.pop_back();}__STL_UNWIND(c.clear());}
};int main(){int ia[9] {0,1,2,3,4,8,9,3,5};priority_queueintiqp(ia,ia9);std::cout iqp.size() std::endl; //9for (int i 0; i iqp.size(); i) {std::cout iqp.top() ; //9 9 9 9 9 9 9 9 9}std::cout std::endl;while(!iqp.empty()){std::cout iqp.top() ; //9 8 5 4 3 3 2 1 0iqp.pop();}std::cout std::endl;
}
参考链接
__STL_TRY和__STL_UNWIND这两个宏的意思 - Superpig0501 - 博客园
