STL源碼學習系列十二： 容器配接器( Priority_queue）

容器配接器( Priority_queue）

概述

priority_queue是擁有優先級的queue，不過它容器内的元素并不是根據加入順序排列，而是根據使用者定義的優先級進行排列。priority_queue隻能在隊列尾部加入元素，在頭部取出元素。不能周遊容器，是以不需要自己設定疊代器。在SGI STL的源碼<stl_queue.h>的class priority_queue設計中，它是基于某種容器作為底部結構的，預設容器是vector容器，使用者也可以自己指定容器的類型。

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 < 2)  retur n;
    const _DistanceType __len = __last - __first;
    _DistanceType __parent = (__len - 2) / 2;
    while (true)
     {
          ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
          std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
          if (__parent == 0)
            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 - 1) / 2)
        {
          __secondChild = 2 * (__secondChild + 1);
          if (__comp(*(__first + __secondChild),
                     *(__first + (__secondChild - 1))))
            __secondChild--;
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
          __holeIndex = __secondChild;
        }
      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
        {
          __secondChild = 2 * (__secondChild + 1);
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
                                                     + (__secondChild - 1)));
          __holeIndex = __secondChild - 1;
        }
      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 - 1) / 2;
      while (__holeIndex > __topIndex && *(__first + __parent) < __value)
        {
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
          __holeIndex = __parent;
          __parent = (__holeIndex - 1) / 2;
        }
      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
    }
           

pop操作移除堆頂元素

void pop()
{
    std::pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
}
           

由于使用的是vector，如果移除第一個元素再make_heap的話代價會很大。這裡先将第一個元素和最後一個元素交換，删除最後一個元素，再從第一個元素做一次下溯過程，就建成了新的最大堆。

End