概述
顾名思义，
priority_queue是一个拥有权值观念的queue，它允许加入新元素，移除旧元素、审视元素值等功能
priority_queue带有权值观念，其内的元素并非是依照被推入的次序排列，而是自动依照元素的权值排列。权值最高者，排在前面。
实现
缺省情况下
priority_queue是利用一个max-heap完成，max-heap是一个vector表示的完全二叉树。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
template <class T,class Sequence = Vector<T>,class Compare = 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() {} // template <class InputIterator> priority_queue(InputIterator first,InputIterator last,const Compare& x) : c(first,last),comp(x) { make_heap(c.begin(),c.end(),comp); } template <class InputIterator> priority_queue(InputIterator first,InputIterator last) : c(first,last) { 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 { c.push_back(x); push_heap(c.begin(),c.end(),comp); } __STL_UNWIND(c.clear()); } void pop() { __STL_TRY { pop_heap(c.begin(),c.end(),comp); c.pop_back(); } __STL_UNWIND(c.clear()); } }; |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ C++_成员访问权限06/20
- ♥ Photoshop CEP扩展和插件开发04/27
- ♥ STL_了解05/02
- ♥ SOUI源码：log4z06/24
- ♥ Boost 程序库完全开发指南：容器算法数学文件08/24
- ♥ C++标准库_cfenv02/14