1、STL

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站制作、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)阜康,10余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792

 庫(kù)函數(shù)的設(shè)計(jì)第一位是通用性，模板為其提供了可能；標(biāo)準(zhǔn)模板庫(kù)中的所有算法和容器都是通過模板實(shí)現(xiàn)的。

 STL(標(biāo)準(zhǔn)模板庫(kù))是 C++最有特色，最實(shí)用的部分之一。

STL整個(gè)架構(gòu)模型如下：

2、list(雙向循環(huán)鏈表)

 調(diào)用STL系統(tǒng)的#include<list>,用系統(tǒng)的雙向循環(huán)鏈表結(jié)構(gòu)處理：

#include<iostream>
#include<list> //調(diào)用系統(tǒng)的list,雙向循環(huán)鏈表結(jié)構(gòu)
using namespace std;

int main(void){
     
    list<int> mylist;
    for(int i = 1; i <= 10; i++){
        mylist.push_back(i);  //接口，末尾增加
    }
    list<int>::iterator it = mylist.begin(); //迭代器，
    while(it != mylist.end()){
        cout<<*it<<"-->"; //打印內(nèi)部數(shù)字
        ++it;   //每次往后移一個(gè)
    }
    cout<<"NULL"<<endl;
}

3、list部分源碼實(shí)現(xiàn)剖析

list模型如下：

閱讀其源代碼，分析了部分的功能：

#ifndef _LIST_H   //條件宏編譯，避免重復(fù)定義
#define _LIST_H

#include<assert.h>   //斷言引入的頭文件
#include<malloc.h>   //申請(qǐng)空間所引入的頭文件

template<class _Ty> //此處先不涉及空間置配器
class list{    //list類
public:
    struct _Node;
    typedef struct _Node* _Nodeptr;  //指向節(jié)點(diǎn)的指針類型
    struct _Node{   //_Node這個(gè)是節(jié)點(diǎn)類型
        _Nodeptr _Prev;    //前驅(qū)節(jié)點(diǎn)
        _Nodeptr _Next;    //后繼節(jié)點(diǎn)
        _Ty      _Value;   //模板數(shù)據(jù)類型
    };
    struct _Acc{  //定義_Acc這個(gè)類型
        typedef struct _Node*& _Nodepref;  //指向節(jié)點(diǎn)類型指針的引用
        typedef _Ty&           _Vref;      //這個(gè)數(shù)據(jù)類型的引用
        static _Nodepref _Next(_Nodeptr _P)//靜態(tài)方法， 返回值是節(jié)點(diǎn)指針的引用 ，參數(shù)是指向節(jié)點(diǎn)的指針
        {return ((_Nodepref)(*_P)._Next);}//：*_P得到這個(gè)節(jié)點(diǎn)，()強(qiáng)制類型轉(zhuǎn)換的優(yōu)先級(jí)沒有.高，所以此時(shí)先取_Next，在進(jìn)行強(qiáng)制類型轉(zhuǎn)換的工作，返回一個(gè)指向節(jié)點(diǎn)指針的引用。
        static _Nodepref _Prev(_Nodeptr _P)
        {return ((_Nodepref)(*_P)._Prev);}
        static _Vref _Value(_Nodeptr _P)
        {return ((_Vref)(*_P)._Value);} 
    };
public:  //以下的類型是_A這個(gè)類下面的類型，_A這個(gè)類在空間置配器中定義
    typedef typename _A::value_type           value_type;
    typedef typename _A::pointer_type         pointer_type;
    typedef typename _A::const_pointer_type   const_pointer_type;
    typedef typename _A::reference_type       reference_type;
    typedef typename _A::const_reference_type const_reference_type;
    typedef typename _A::size_type            size_type;  //這個(gè)類型其實(shí)就是size_t

private:
    _Nodeptr  _Head;   //指向頭結(jié)點(diǎn)的指針
    size_type _Size;   //有幾個(gè)節(jié)點(diǎn)個(gè)數(shù)
};

#endif

以上代碼主要是struct _Acc這個(gè)類的理解好至關(guān)重要！??！

下面就是構(gòu)造函數(shù)和析構(gòu)函數(shù)了

public:
    explicit list():_Head(_Buynode()),_Size(0)  //explicit顯示調(diào)用此構(gòu)造函數(shù)，給頭一個(gè)指向，剛開始0個(gè)
    {}
    ~list()
    {     //釋放空間和空間配置器有關(guān)，在現(xiàn)階段先不關(guān)心。
        erase(begin(), end());  //調(diào)用開始，結(jié)束函數(shù)釋放空間；
        _Freenode(_Head);       //釋放頭；
        _Head = 0, _Size = 0;   //都賦空；
    }
    ..................................................
protected:
    _Nodeptr _Buynode(_Nodeptr _Narg=0, _Nodeptr _Parg=0)  // 返回值為節(jié)點(diǎn)指針類型，參數(shù)都為節(jié)點(diǎn)指針類型，傳的應(yīng)該是后繼和前驅(qū)指針，默認(rèn)都為0；
    {
        _Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node));//申請(qǐng)一個(gè)節(jié)點(diǎn)空間，把地址給了_S;
        
        assert(_S != NULL);  //所申請(qǐng)的空間存在的話
        _Acc::_Next(_S) = _Narg!=0 ? _Narg : _S; //給新生成的節(jié)點(diǎn)的_Next賦值
        _Acc::_Prev(_S) = _Parg!=0 ? _Parg : _S; //給新生成的節(jié)點(diǎn)的_Prev賦值
        return _S; //返回這個(gè)新生成節(jié)點(diǎn)的地址
    }
//這個(gè)_Buynode函數(shù)的意思是：當(dāng)創(chuàng)建的是第一個(gè)節(jié)點(diǎn)時(shí)，自己一個(gè)節(jié)點(diǎn)連向自己，構(gòu)成雙向循環(huán)鏈表，其他的情況則是插入到兩個(gè)節(jié)點(diǎn)之間！?。?........................................................

接下來寫迭代器：

public:
    class iterator{   //迭代器也是一個(gè)類，是list的內(nèi)部類；
    public:
        iterator()
        {}
        iterator(_Nodeptr _P):_Ptr(_P)
        {}
    public:
        iterator& operator++(){  // ++it,前++的運(yùn)算符重載
            _Ptr=_Ptr->_Next; //因?yàn)槭擎湵斫Y(jié)構(gòu)，內(nèi)部實(shí)現(xiàn)迭代器的++,是進(jìn)行了++的重載；使其指針的移動(dòng)到下一個(gè)節(jié)點(diǎn)；
            return *this;   //返回的是這個(gè)節(jié)點(diǎn)的引用。
        }
        iterator operator++(int)// it++
        {
            _It it(_Ptr);  //先保存原先節(jié)點(diǎn)
            _Ptr = _Ptr->_Next; //移到下一個(gè)節(jié)點(diǎn)
            return it;  //返回原先的；
        }
        iterator operator--(int); //類似
        iterator& operator--();
        reference_type operator*()const //對(duì)*的重載
        {return _Ptr->_Value;}   //返回這個(gè)節(jié)點(diǎn)的_Value值
        pointer_type operator->()const //對(duì)->的重載
        //{return &_Ptr->_Value;}  自己實(shí)現(xiàn)的，->的優(yōu)先級(jí)高于&，所以將_Value的地址返回
        {return (&**this);}  //系統(tǒng)中的，this是迭代器的地址，*this是迭代器對(duì)象，再來一個(gè)*時(shí)，調(diào)用上面的(對(duì)*的重載)，此時(shí)還是返回_Value的地址。
    public:
        bool operator!=(const iterator &it)const  //迭代器對(duì)象的比較
        {return _Ptr!=it._Ptr;}  //比的是指向節(jié)點(diǎn)的指針；
    public:
        _Nodeptr _Mynode()const //得到當(dāng)前節(jié)點(diǎn)的地址；
        {return _Ptr;}
    protected:
        _Nodeptr _Ptr;   //迭代器的數(shù)據(jù)成員是一個(gè)指向節(jié)點(diǎn)的指針。
    };
    typedef iterator _It;  //_It 就是迭代器類型
public:
    iterator begin(){return iterator(_Acc::_Next(_Head));}  //begin()函數(shù)得到頭結(jié)點(diǎn)的后繼(第一個(gè)有效節(jié)點(diǎn)的地址)
    iterator begin()const;
    iterator end(){return iterator(_Head);}  //end()函數(shù)得到的是頭結(jié)點(diǎn)(也就是最后一個(gè)節(jié)點(diǎn)的后繼地址);
public:                        //前面的已經(jīng)講的很清楚了，后面的都是調(diào)用即可；
    void push_back(const _Ty &x)  
    {insert(end(),x);}
    void push_front(const _Ty &x)
    {insert(begin(),x);}
public:
    iterator insert(iterator _P, const _Ty &_X=_Ty())
    {
        _Nodeptr _S = _P._Mynode();  //得到節(jié)點(diǎn)地址
        _Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));  //下面的三句調(diào)用前面的函數(shù)_Buynode()實(shí)現(xiàn)了插入功能;
        _S = _Acc::_Prev(_S);
        _Acc::_Next(_Acc::_Prev(_S)) = _S;
        ++_Size;  //個(gè)數(shù)加1
        return iterator(_S);
    }
    void insert(iterator _P, size_type _M, const _Ty &_X) //插入個(gè)數(shù)_M個(gè)，以下幾個(gè)調(diào)用前面函數(shù)；
    {
        for(; 0<_M; --_M)
            insert(_P,_X);
    }
    void insert(iterator _P, const _Ty *_F, const _Ty *_L) //區(qū)間的插入
    {
        for(; _F!=_L; ++_F)
            insert(_P, *_F);
    }
    void insert(iterator _P, _It _F, _It _L)  //迭代器的插入
    {
        for(; _F!=_L; ++_F)
            insert(_P, *_F);
    }
    /*
    void push_back(const _Ty &x)  //尾隨增加最后
    {
        _Nodeptr _S = _Buynode(_Head, _Acc::_Prev(_Head)); //實(shí)現(xiàn)插入功能
        _Acc::_Value(_S) = x;
        _Acc::_Next(_Acc::_Prev(_Head)) = _S;
        _Acc::_Prev(_Head) = _S;
        _Size++;  //最后加1
    }

    iterator erase(iterator _P)// 刪除空間
    {
        _Nodeptr _S = (_P++)._Mynode();
        _Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
        _Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
 
        --_Size;  //個(gè)數(shù)減少1個(gè)
        return _P;
    }
    iterator erase(iterator _F, iterator _L) //調(diào)用函數(shù)，刪除區(qū)間
    {
        while(_F != _L)
            erase(_F++);
        return _F;
    }
    void clear() //清除所有空間
    {erase(begin(), end());}

#endif

4、總結(jié)：

 (1)、迭代器的本質(zhì)有了了解，是一個(gè)內(nèi)部類，它將是一個(gè)對(duì)象，內(nèi)部數(shù)據(jù)成員是一個(gè)指向節(jié)點(diǎn)的指針；

 (2)、迭代器對(duì)->的重載返回的是節(jié)點(diǎn)內(nèi)部數(shù)據(jù)的地址，而不是節(jié)點(diǎn)的地址；

 (3)、迭代器對(duì)每種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)均不相同，(Stack, queue, list...........)

 (4)、空間配置器：對(duì)所有的數(shù)據(jù)結(jié)構(gòu)而言，只有一份，

 作用：申請(qǐng)，釋放空間，構(gòu)造，析構(gòu)對(duì)象；

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章名稱：初識(shí)STL剖析list部分源碼-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://www.rwnh.cn/article24/dhhcje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、網(wǎng)站策劃、網(wǎng)站營(yíng)銷、網(wǎng)站內(nèi)鏈、響應(yīng)式網(wǎng)站、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)