STL源码：priority_queue

缺乏、安全感 2022-08-07 08:42 149阅读 0赞

优先队列完全以底部容器为依据，加上heap处理规则，实现很简单。缺省下**以vector为底部容器，利用大根堆**。它是一个有权值概念的queue（头出尾进，无其他存取元素的途径）。

和queue、stack一样，是容器适配器，[详见queue][queue]

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
    template <class T, class Sequence = vector<T>,
    class Compare = less<typename Sequence::value_type> >
    #else
    template <class T, class Sequence, class Compare>
    #endif
    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) {}
    
    	// 使用[first, last)区间构造priority_queue，构造函数产生二叉堆
    #ifdef __STL_MEMBER_TEMPLATES
    	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); }
    #else /* __STL_MEMBER_TEMPLATES */
    	priority_queue(const value_type* first, const value_type* last,
    		const Compare& x) : c(first, last), comp(x) {
    			make_heap(c.begin(), c.end(), comp);
    	}
    	priority_queue(const value_type* first, const value_type* last)
    		: c(first, last) { make_heap(c.begin(), c.end(), comp); }
    #endif /* __STL_MEMBER_TEMPLATES */
    
    	// STL priority_queue标准接口
    	bool empty() const { return c.empty(); }
    	size_type size() const { return c.size(); }
    
    	// 返回优先级最高的元素
    	const_reference top() const { return c.front(); }
    
    	// 插入元素, 并调整heap
    	void push(const value_type& x)
    	{
    		__STL_TRY {
    			c.push_back(x); //利用底层元素将元素插入
    			// 详细分析见<stl_heap.h>，重新堆排序
    			push_heap(c.begin(), c.end(), comp);
    		}
    		__STL_UNWIND(c.clear());
    	}
    
    	// 弹出优先级最高的元素
    	void pop() {
    		__STL_TRY {
    			// 详细分析见<stl_heap.h>
    			pop_heap(c.begin(), c.end(), comp);
    			c.pop_back();
    		}
    		__STL_UNWIND(c.clear());
    	}
    };
    
    // 不提供比较操作
    
    __STL_END_NAMESPACE
    
    #endif /* __SGI_STL_INTERNAL_QUEUE_H */

[queue]: http://blog.csdn.net/u013074465/article/details/44623029