程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++ Primer 學習筆記_55_STL剖析(十):容器適配器(stack、 queue 、priority_queue)源碼淺析與使用示例

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

編輯:關於C++

七種基本容器: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>
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved