STL學習——Priority_queue篇

• 概述

  priority_queue是一個擁有權值觀念的queue，它允許加入新元素，移除舊元素，審視元素值等功能。因為它是queue，故隻允許底端加入元素，頂端取出元素。priorit_queue内元素并非依照被推入的次序排列，而是依照元素權值排列。權值最高者，排在最前面。

• 實作

  priority_queue利用max_heap和vector表現的完全二叉樹實作。它的實作完全以底部容器為根據，并使用heap處理規則，故實作簡單。預設情況，使用vector為底部容器。由于它有“修改某物接口，形成另一風貌”性質，為擴充卡，被稱為容器擴充卡。它不提供疊代器，也不提供周遊操作。其實作元素如下：

  // priority_queue類定義
  template <class _Tp, 
            class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),
            class _Compare
            __STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>) >
  class priority_queue {
  ...
  public:
    typedef typename _Sequence::value_type      value_type;
    typedef typename _Sequence::size_type       size_type;
    typedef          _Sequence                  container_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) {}
    // 以下用到的make_heap()，push_heap()，pop_heap()都是泛型算法
    // 注意，任一個構造函數都立刻位于底層容器内産生一個implicit represention heap
    priority_queue(const _Compare& __x, const _Sequence& __s) 
      : c(__s), comp(__x) 
      { make_heap(c.begin(), c.end(), comp); }
  
  #ifdef __STL_MEMBER_TEMPLATES
    template <class _InputIterator>
    priority_queue(_InputIterator __first, _InputIterator __last) 
      : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
  
    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,
                   const _Compare& __x, const _Sequence& __s)
    : c(__s), comp(__x)
    { 
      c.insert(c.end(), __first, __last);
      make_heap(c.begin(), c.end(), comp);
    }
  
  #else /* __STL_MEMBER_TEMPLATES */
    priority_queue(const value_type* __first, const value_type* __last) 
      : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
  
    priority_queue(const value_type* __first, const value_type* __last, 
                   const _Compare& __x) 
      : c(__first, __last), comp(__x)
      { make_heap(c.begin(), c.end(), comp); }
  
    priority_queue(const value_type* __first, const value_type* __last, 
                   const _Compare& __x, const _Sequence& __c)
      : c(__c), comp(__x) 
    { 
      c.insert(c.end(), __first, __last);
      make_heap(c.begin(), c.end(), comp);
    }
  #endif /* __STL_MEMBER_TEMPLATES */
    // 判斷priority_queue是否為空
    bool empty() const { return c.empty(); }
    // 傳回priority_queue大小
    size_type size() const { return c.size(); }
    // 傳回priority_queue隊首元素
    const_reference top() const { return c.front(); }
    // priority入隊操作
    void push(const value_type& __x) {
      __STL_TRY {
        // push_heap是泛型算法，先利用底層容器的push_back()将新元素推入末端，再重排heap。
        c.push_back(__x); 
        push_heap(c.begin(), c.end(), comp);   // push_heap是泛型算法
      }
      __STL_UNWIND(c.clear());
    }
    // priority_queue出隊操作
    void pop() {
      __STL_TRY {
        // pop_heap是泛型算法，從heap内取出一個元素。他并不是真正将元素彈出，而是重排heap，然後在以底層容器的pop_heap()取得被彈出的元素
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
      }
      __STL_UNWIND(c.clear());
    }
  };
  ...
             

• 參考文獻

  STL源碼剖析——侯捷

  STL源碼