stl源码分析之priority queue

前面两篇介绍了gcc4.8的vector和list的源码实现，这是stl最常用了两种序列式容器。除了容器之外，stl还提供了一种借助容器实现特殊操作的组件，谓之适配器，比如stack，queue，priority queue等，本文就介绍gcc4.8的priority queue的源码实现。

顾名思义，priority queue是带有优先级的队列，所以元素必须提供<操作符，与vector和list不同，priority queue允许加入元素，但是取出时只能取出优先级最高的元素。

一、 priority queue定义

priority queue没有基类

template<typename _Tp, typename _Sequence = vector<_Tp>,

   typename _Compare  = less<typename _Sequence::value_type> >

class priority_queue

 {

    public:

      typedef typename _Sequence::value_type                value_type;

      typedef typename _Sequence::reference                 reference;

      typedef typename _Sequence::const_reference           const_reference;

      typedef typename _Sequence::size_type                 size_type;

      typedef          _Sequence                            container_type;

    protected:

      _Sequence  c;

      _Compare   comp;

…...

priority queue底层默认使用vector，含有两个成员，vector c存储数据，comp是一个仿函数，用来比较数据大小。

二、 priority queue构造方式

可以用vector直接初始化priority queue，也可以任意迭代器或者数组指针初始化。

explicit

      priority_queue(const _Compare& __x,

                     const _Sequence& __s)

      : c(__s), comp(__x)

      { std::make_heap(c.begin(), c.end(), comp); }

      explicit

      priority_queue(const _Compare& __x = _Compare(),

                     _Sequence&& __s = _Sequence())

      : c(std::move(__s)), comp(__x)

      { std::make_heap(c.begin(), c.end(), comp); }

   template<typename _InputIterator>

        priority_queue(_InputIterator __first, _InputIterator __last,

                       const _Compare& __x,

                       const _Sequence& __s)

        : c(__s), comp(__x)

        {

          __glibcxx_requires_valid_range(__first, __last);

          c.insert(c.end(), __first, __last);

          std::make_heap(c.begin(), c.end(), comp);

        }

 template<typename _InputIterator>

        priority_queue(_InputIterator __first, _InputIterator __last,

                       const _Compare& __x = _Compare(),

                       _Sequence&& __s = _Sequence())

        : c(std::move(__s)), comp(__x)

        {

          __glibcxx_requires_valid_range(__first, __last);

          c.insert(c.end(), __first, __last);

          std::make_heap(c.begin(), c.end(), comp);

        }

将元素全部插入priority queue后，使用 make_heap将其建成最大堆，

template<typename _RandomAccessIterator>

    void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

    { typedef typename iterator_traits<_RandomAccessIterator>::value_type

          _ValueType;

      typedef typename iterator_traits<_RandomAccessIterator>::difference_type

          _DistanceType;

      if (__last - __first < )

        return;

      const _DistanceType __len = __last - __first;

      _DistanceType __parent = (__len - ) / ;

      while (true)

        {

          _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));

          std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));

          if (__parent == )

            return;

          __parent--;

        }

    }

__adjust_heap是一个下溯过程，从最后一个非叶子节点往前一个个执行下溯过程，使得以其为根节点的子树是一个最大堆。

template<typename _RandomAccessIterator, typename _Distance,

           typename _Tp, typename _Compare>

    void  __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,

                  _Distance __len, _Tp __value, _Compare __comp)

    {

      const _Distance __topIndex = __holeIndex;

      _Distance __secondChild = __holeIndex;

      while (__secondChild < (__len - ) / )

        {

          __secondChild =  * (__secondChild + );

          if (__comp(*(__first + __secondChild),

                     *(__first + (__secondChild - ))))

            __secondChild--;

          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));

          __holeIndex = __secondChild;

        }

      if ((__len & ) ==  && __secondChild == (__len - ) / )

        {

          __secondChild =  * (__secondChild + );

          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first

                                                     + (__secondChild - )));

          __holeIndex = __secondChild - ;

        }

      std::__push_heap(__first, __holeIndex, __topIndex,

                       _GLIBCXX_MOVE(__value), __comp);

    }

三、 priority queue的元素操作

priority queue只有push和pop两个主要操作，push增加新的元素，

void push(const value_type& __x)

      {

        c.push_back(__x);

        std::push_heap(c.begin(), c.end(), comp);

      }

先放到最后一个位置，再使用 push_heap执行一个上溯操作，将插入元素移动到合适位置，保证整个queue仍然是个最大堆。

template<typename _RandomAccessIterator, typename _Distance, typename _Tp>

    void

    __push_heap(_RandomAccessIterator __first,

                _Distance __holeIndex, _Distance __topIndex, _Tp __value)

    {

      _Distance __parent = (__holeIndex - ) / ;

      while (__holeIndex > __topIndex && *(__first + __parent) < __value)

        {

          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));

          __holeIndex = __parent;

          __parent = (__holeIndex - ) / ;

        }

      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);

    }

pop操作移除堆顶元素，

void pop()

{

std::pop_heap(c.begin(), c.end(), comp);

c.pop_back();

}

由于使用的是vector，如果移除第一个元素再make_heap的话代价会很大。这里先将第一个元素和最后一个元素交换，删除最后一个元素，再从第一个元素做一次下溯过程，就建成了新的最大堆。

巴特西

stl源码分析之priority queue

最新文章

热门文章