当前位置：首页 > article >正文

STL序列式容器之priority_queue

article 2024/11/18 20:48:16

priority_queue概述

顾名思义，priority是一个拥有优先级概念的queue，它允许插入新元素，删除旧元素，比较元素值等功能。因为是基于权值的优先级进行内部排序，所有插入元素，不会是基于内部迭代器进行插入，插入完成后，内部会对位置进行调整；所以其插入接口push的参数只包含元素本身，而没有迭代器；也没有形如push_front,push_back等接口；

priority可以以任意顺序进行push，但pop则会以权值的逆序方式依次进行推出。缺省情况下priority利用max-heap完成。max-heap可以满足priority所需的依权值高低方式依次推出的特性。

priority_queue定义完整列表

由于priority_queue完全以底部容器为根据，再加上heap处理机制，所以其实现非常简单。缺省情况下是以vector为底层容器。源代码很简短，此处完整列出。

queue以底部容器完成所有工作。具有这种“修改某物接口，形成另一种风貌”之性质者，成为adapter（适配器），因此，STL priority_queue往往不被归类为container(容器),而被归类为container 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() {}
    explicit 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) {
        __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());

    }

};

从以上代码中可以看出调用了push_heap函数；但是细心的读者会发现，此处的push_heap会和max-heap中介绍的push_heap略有差异；此处多出了参数comp；这个差异在函数实现上，应该是将代码中的默认运算符<，修改为comp调用即可；（作者为什么不直接在heap中对push_heap(RandomAccessIterator,RandomAccessIterator , const Compare &)进行说明，待进一步阅读源码后进行补充）