C++ Primer 學習筆記_55_STL剖析（十）：容器適配器（stack、 queue 、priority_queue）源碼淺析與使用示例

七種基本容器：vector、deque、list、set、multiset、map、multimap

一、容器適配器
stack
queue
priority_queue

stack、queue、priority_queue 都不支持任一種迭代器，它們都是容器適配器類型，stack是用vector/deque/list對象創建了一個先進後出容器；queue是用deque或list對象創建了一個先進先出容器；priority_queue是用vector/deque創建了一個排序隊列，內部用二叉堆實現。

二、stack

1、示例

#include <iostream>
#include <vector>
#include <list>
#include <stack>

using namespace std;

int main(void)
{
    stack<int, int=""> > s;  //set則出錯
    for (int i = 0; i < 5; i++)
    {
        s.push(i);
    }

    //for (size_t i=0; i<s.size(); cout="" pre="" return="" while=""><p>
</p><div>運行結果：</div><div>4 3 2 1 0</div><div>
</div><p>
2、源碼分析</p><p>
</p><pre class="brush:java;">// TEMPLATE CLASS stack
template < class _Ty,
         class _Container = deque<_Ty> >
class stack
{
    // LIFO queue implemented with a container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    stack()
        : c()
    {
        // construct with empty container
    }

    explicit stack(const _Container &_Cont)
        : c(_Cont)
    {
        // construct by copying specified container
    }

    bool empty() const
    {
        // test if stack is empty
        return (c.empty());
    }

    size_type size() const
    {
        // test length of stack
        return (c.size());
    }

    reference top()
    {
        // return last element of mutable stack
        return (c.back());
    }

    const_reference top() const
    {
        // return last element of nonmutable stack
        return (c.back());
    }

    void push(const value_type &_Val)
    {
        // insert element at end
        c.push_back(_Val);
    }

    void pop()
    {
        // erase last element
        c.pop_back();
    }

    const _Container &_Get_container() const
    {
        // get reference to container
        return (c);
    }

protected:
    _Container c; // the underlying container
};</pre><p>
</p><div>即有一個_Container 成員，默認是deque<_Ty> ，當然也可以傳遞vector, list 進去，只要支持push_back，pop_back 等接口。內部的函數實現都借助了容器的函數。</div><p>
</p><p>
</p><p>
</p><p>三、queue</p><p>1、示例</p><p>
</p><pre class="brush:java;">#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

int main(void)
{
    //int a[] = {1, 2, 3, 4, 5};
    //vector<int> v(a, a+5);  
    //queue<int> q(a, a+5)  //出錯，不能這麼初始化
 
    queue<int, int=""> > q;  //vector出錯，必須要支持pop的函數的才行
    for (int i = 0; i < 5; i++)
    {
        q.push(i);
    }

    while (!q.empty())
    {
        cout << q.front() << ' ';
        q.pop();
    }

    cout << endl;

    return 0;
}</int,></int></int></queue></stack></list></vector></iostream></pre><p>
</p><div>運行結果：</div><div>0 1 2 3 4</div><div>
</div><div>
</div><p>2、源碼分析</p><p>
</p><pre class="brush:java;">// TEMPLATE CLASS queue
template < class _Ty,
         class _Container = deque<_Ty> >
class queue
{
    // FIFO queue implemented with a container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    queue()
        : c()
    {
        // construct with empty container
    }

    explicit queue(const _Container &_Cont)
        : c(_Cont)
    {
        // construct by copying specified container
    }

    bool empty() const
    {
        // test if queue is empty
        return (c.empty());
    }

    size_type size() const
    {
        // return length of queue
        return (c.size());
    }

    reference front()
    {
        // return first element of mutable queue
        return (c.front());
    }

    const_reference front() const
    {
        // return first element of nonmutable queue
        return (c.front());
    }

    reference back()
    {
        // return last element of mutable queue
        return (c.back());
    }

    const_reference back() const
    {
        // return last element of nonmutable queue
        return (c.back());
    }

    void push(const value_type &_Val)
    {
        // insert element at beginning
        c.push_back(_Val);
    }

    void pop()
    {
        // erase element at end
        c.pop_front();
    }

    const _Container &_Get_container() const
    {
        // get reference to container
        return (c);
    }

protected:
    _Container c; // the underlying container
};</pre><p>
</p><div>實現跟stack 是很類似的，只是queue不能用vector 實現，因為沒有pop_front 接口。</div><p>
</p><p>
</p><p>
</p><p>四、priority_queue</p><p>1、示例</p><p>
</p><pre class="brush:java;">#include <iostream>
#include <functional>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

int main(void)
{
    int a[] = {5, 1, 2, 4, 3};
    priority_queue<int, int="">, greater<int> > q(a, a + 5);  //默認從大到小，必須有三個參數才能調用greater<int>
    //priority_queue<int, int="">, less<int> > q(a, a + 5);

    while (!q.empty())
    {
        cout << q.top() << ' ';
        q.pop();
    }

    cout << endl;

    return 0;
}</int></int,></int></int></int,></queue></stack></list></vector></functional></iostream></pre><p>
</p><div>運行結果：</div><div>1 2 3 4 5</div><div>
</div><div>
</div><p>2、源碼分析</p><p>
</p><pre class="brush:java;">// TEMPLATE CLASS priority_queue
template < class _Ty,
         class _Container = vector<_Ty>,
         class _Pr = less<typename _container::value_type=""> >
class priority_queue
{
    // priority queue implemented with a _Container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    priority_queue()
        : c(), comp()
    {
        // construct with empty container, default comparator
    }

    explicit priority_queue(const _Pr &_Pred)
        : c(), comp(_Pred)
    {
        // construct with empty container, specified comparator
    }

    priority_queue(const _Pr &_Pred,const _Container &_Cont)
        : c(_Cont), comp(_Pred)
    {
        // construct by copying specified container, comparator
        make_heap(c.begin(), c.end(), comp);
    }

    template<class_iter>
    priority_queue(_Iter _First, _Iter _Last)
        : c(_First, _Last), comp()
    {
        // construct by copying [_First, _Last), default comparator
        make_heap(c.begin(), c.end(), comp);
    }

    template<class_iter>
    priority_queue(_Iter _First, _Iter _Last, const _Pr &_Pred)
        : c(_First, _Last), comp(_Pred)
    {
        // construct by copying [_First, _Last), specified comparator
        make_heap(c.begin(), c.end(), comp);
    }

    template<class_iter>
    priority_queue(_Iter _First, _Iter _Last, const _Pr &_Pred,
                  const _Container &_Cont)
        : c(_Cont), comp(_Pred)
    {
        // construct by copying [_First, _Last), container, and comparator
        c.insert(c.end(), _First, _Last);
        make_heap(c.begin(), c.end(), comp);
    }

    bool empty() const
    {
        // test if queue is empty
        return (c.empty());
    }

    size_type size() const
    {
        // return length of queue
        return (c.size());
    }

    const_reference top() const
    {
        // return highest-priority element
        return (c.front());
    }

    reference top()
    {
        // return mutable highest-priority element (retained)
        return (c.front());
    }

    void push(const value_type &_Pred)
    {
        // insert value in priority order
        c.push_back(_Pred);
        push_heap(c.begin(), c.end(), comp);
    }

    void pop()
    {
        // erase highest-priority element
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }

protected:
    _Container c; // the underlying container
    _Pr comp;   // the comparator functor
};
</class_iter></class_iter></class_iter></typename></pre><p>
</p><p>priority_queue 的實現稍微復雜一點，可以傳遞3個參數，而且有兩個成員，comp 即自定義比較邏輯，默認是less<value_type>，在構造函數中調用make_heap函數構造二叉堆，comp 主要是用於構造二叉堆時的判別，如果是less 則構造大堆，如果傳遞greater 則構造小堆.</value_type></p><p>注意，priority_queue 不能用list 實現，因為list 只支持雙向迭代器，而不支持隨機迭代器。</p><p>
</p><p>
</p><p>下面舉個例子說明make_heap 函數的用法(構造一個二叉堆)：</p><p>
</p><pre class="brush:java;">#include <iostream>
#include <functional>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <iterator>

using namespace std;

int main(void)
{
    int a[] = {5, 1, 2, 4, 3};
    make_heap(a, a + 5, less<int>());

    copy(a, a + 5, ostream_iterator<int>(cout, " "));
    cout << endl;

    sort(a, a + 5);
    //sort_heap(a, a+5, less<int>()); //對應於make_heap的less
    copy(a, a + 5, ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}</int></int></int></int></iterator></queue></stack></list></vector></functional></iostream></pre><p>
</p><div>輸出：</div><p>5 4 2 1 3</p><p>1 2 3 4 5</p><p>make_heap() 將容器的元素構造成二叉堆，傳遞的是less，即構造的是大堆，把大堆層序遍歷的結果存入數組，再調用sort() 進行排序，內部調用的實際算法不一定，可以是堆排序、插入排序、選擇排序等等，跟蹤進去發現調用的是插入排序；當然也可以直接指定使用堆排序 sort_heap（調用者必須已經是堆了，也就是前面已經先調用了make_heap，而且大小堆類型得匹配），與make_heap 一樣，第三個參數傳遞的都是函數對象的用法。sort 和 sort_heap 默認都是從小到大排序，除非重載的版本傳遞了第三個參數，如下，第三個參數可以是函數指針，也可以是函數對象：</p><p>
</p><pre class="brush:java;">// order heap by repeatedly popping, using operator<
template<class _ranit=""> inline
void sort_heap(_RanIt _First, _RanIt _Last);

// order heap by repeatedly popping, using _Pred
template < class _RanIt,
         class _Pr > inline
void sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred);</class></pre><p>
</p><div>傳遞greater 構造的是小堆，如下圖所示：</div><p><img alt="" data-cke-saved-src=/uploadfile/2016/0220/20160220104305113.png" src=/uploadfile/2016/0220/20160220104305113.png"></p><p>
</p><p>
</p><p>
</p><p>參考：</p><p>C++ primer 第四版
Effective C++ 3rd
C++編程規范</p><div>
</div></s.size();></int,></stack></list></vector></iostream>