- priority_queue是一個擁有權重概念的queue，允許底部加入新的元素，頭部刪除舊的元素，以及審視元素數值的操作
- priority_queue帶有權重的概念，即元素按照權重進行排列，而不是按照插入隊列的順序進行排序。要求權值高者在前
- 缺省情況下，priority_queue使用max_heap完成，而max_heap物理層面是基于vector邏輯層面表現像complate binary tree；max_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::vector<T>,class Compare = std::less<typename 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//指代比較器template<class InputIterator>priority_queue(InputIterator first, InputIterator last,const Compare& x):c(first,last),comp(x){std::make_heap(c.begin(),c.end(),comp);}//沒有指代比較器template<class InputIterator>priority_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::vector<T>,class Compare = std::less<typename 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//指代比較器template<class InputIterator>priority_queue(InputIterator first, InputIterator last,const Compare& x):c(first,last),comp(x){std::make_heap(c.begin(),c.end(),comp);}//沒有指代比較器template<class InputIterator>priority_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_queue<int>iqp(ia,ia+9);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 - 博客園
