一步步看懂STL源码（4）--priority_queue

priority_queue概述

priority_queue带有权值的概念，给其中的元素提供了一种按优先级的操作顺序，和插入顺序无关，能做到每次取出的都是权值是最高的。缺省情况下是一个大根堆，且底层用vector来实现。

priority_queue定义

由于priority_queue完全以底部容器来实现，并且用heap的操作来进行规范操作处理，这类完全嫁接与别的容器的容器，称为配接器(adapter)，下面是完整的代码描述。

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() {}
    priority_queue(const Compare& x) : c(), comp(x) {}
    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) {
        c.push_back(x);
        push_heap(c.begin(), c.end(), comp);
    }
    void pop() {
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }
};

测试

int ia[9] = {0,1,2,3,4,8,9,3,5};
priority_queue<int> que(ia, ia + 9);
while (!que.empty())
{
    cout << que.top() << " ";
    que.pop();
}
// 输出:9 8 5 4 3 3 2 1 0