程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> stl源碼分析之priority queue，stlqueue

stl源碼分析之priority queue，stlqueue

編輯：C++入門知識

stl源碼分析之priority queue，stlqueue

前面兩篇介紹了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 < 2)
        return;
      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的話代價會很大。這裡先將第一個元素和最後一個元素交換，刪除最後一個元素，再從第一個元素做一次下溯過程，就建成了新的最大堆。

C++ stl中priority_queue與algotithm中的heap中哪個效率高

各有各的優點和缺點，具體看應用的場合。
細節可以參考《The Standard C++ Library》或者侯捷的《STL源碼剖析》

STL priority_queue怎輸出容器中優先級最高與最低的元素

首先，獲取優先級最高的元素用top函數，移出它用pop函數

關於優先級最低的那個元素，理論上優先隊列應該只讓你獲得最高優先的那個元素，因為這是優先隊列邏輯上的定義。就像棧這種結構不應該讓你獲取到棧底的元素一樣。

但是有些實現（尤其是以STL模板形式存在的那些）或多或少會暴露一些內部實現。這樣你就可以利用到，從而實現，例如以下代碼：

template <typename T>
class my_priority_queue : public priority_queue<T> {
public:
T& least_priority() {
return *(c.rbegin());
}
};

這個是我繼承標准庫的優先隊列，利用到它底層是一個線性表，而線性表的最後一個元素就是隊列優先級最低的元素。

但是話要說回來，這個實現依賴於底層的實現，不具有可移植性。
這體現在以上代碼在VS中可以編譯，在gcc中則不可以。同時，即便是VS，下一個版本的STL可能就不能編譯。

想要移除最低級別的元素，你可以用我上述繼承的類實現，同樣是將remove函數代理給底層的線性表實現。

最後說一句，無論什麼時候，你都可以重新創建一個優先隊列，並且使用與原來隊列相反比較器的方式，來獲取優先級最低的元素。這種方式將不會有移植性問題，但會有效率問題。