初識STL 剖析list部分源碼

1、STL

  庫函數的設計第一位是通用性，模板為其提供了可能；標準模板庫中的所有算法和容器都是通過模板實現的。

  STL(標準模板庫)是 C++最有特色，最實用的部分之一。

STL整個架構模型如下：

2、list(雙向循環鏈表)

  調用STL系統的#include<list>,用系統的雙向循環鏈表結構處理：

#include<iostream>
#include<list> //調用系統的list,雙向循環鏈表結構
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<<"-->"; //打印內部數字
        ++it;   //每次往后移一個
    }
    cout<<"NULL"<<endl;
}

3、list部分源碼實現剖析

list模型如下：

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

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

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

template<class _Ty> //此處先不涉及空間置配器
class list{    //list類
public:
    struct _Node;
    typedef struct _Node* _Nodeptr;  //指向節點的指針類型
    struct _Node{   //_Node這個是節點類型
        _Nodeptr _Prev;    //前驅節點
        _Nodeptr _Next;    //后繼節點
        _Ty      _Value;   //模板數據類型
    };
    struct _Acc{  //定義_Acc這個類型
        typedef struct _Node*& _Nodepref;  //指向節點類型指針的引用
        typedef _Ty&           _Vref;      //這個數據類型的引用
        static _Nodepref _Next(_Nodeptr _P)//靜態方法， 返回值是節點指針的引用 ，參數是指向節點的指針
        {return ((_Nodepref)(*_P)._Next);}//：*_P得到這個節點，()強制類型轉換的優先級沒有.高，所以此時先取_Next，在進行強制類型轉換的工作，返回一個指向節點指針的引用。
        static _Nodepref _Prev(_Nodeptr _P)
        {return ((_Nodepref)(*_P)._Prev);}
        static _Vref _Value(_Nodeptr _P)
        {return ((_Vref)(*_P)._Value);} 
    };
public:  //以下的類型是_A這個類下面的類型，_A這個類在空間置配器中定義
    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;  //這個類型其實就是size_t

private:
    _Nodeptr  _Head;   //指向頭結點的指針
    size_type _Size;   //有幾個節點個數
};

#endif

以上代碼主要是struct  _Acc這個類的理解好至關重要！！！

下面就是構造函數和析構函數了

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

接下來寫迭代器：

public:
    class iterator{   //迭代器也是一個類，是list的內部類；
    public:
        iterator()
        {}
        iterator(_Nodeptr _P):_Ptr(_P)
        {}
    public:
        iterator& operator++(){  // ++it,前++的運算符重載
            _Ptr=_Ptr->_Next; //因為是鏈表結構，內部實現迭代器的++,是進行了++的重載；使其指針的移動到下一個節點；
            return *this;   //返回的是這個節點的引用。
        }
        iterator operator++(int)// it++
        {
            _It it(_Ptr);  //先保存原先節點
            _Ptr = _Ptr->_Next; //移到下一個節點
            return it;  //返回原先的；
        }
        iterator operator--(int); //類似
        iterator& operator--();
        reference_type operator*()const //對*的重載
        {return _Ptr->_Value;}   //返回這個節點的_Value值
        pointer_type operator->()const //對->的重載
        //{return &_Ptr->_Value;}  自己實現的，->的優先級高于&，所以將_Value的地址返回
        {return (&**this);}  //系統中的，this是迭代器的地址，*this是迭代器對象，再來一個*時，調用上面的(對*的重載)，此時還是返回_Value的地址。
    public:
        bool operator!=(const iterator &it)const  //迭代器對象的比較
        {return _Ptr!=it._Ptr;}  //比的是指向節點的指針；
    public:
        _Nodeptr _Mynode()const //得到當前節點的地址；
        {return _Ptr;}
    protected:
        _Nodeptr _Ptr;   //迭代器的數據成員是一個指向節點的指針。
    };
    typedef iterator _It;  //_It 就是迭代器類型
public:
    iterator begin(){return iterator(_Acc::_Next(_Head));}  //begin()函數得到頭結點的后繼(第一個有效節點的地址)
    iterator begin()const;
    iterator end(){return iterator(_Head);}  //end()函數得到的是頭結點(也就是最后一個節點的后繼地址);
public:                        //前面的已經講的很清楚了，后面的都是調用即可；
    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();  //得到節點地址
        _Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));  //下面的三句調用前面的函數_Buynode()實現了插入功能;
        _S = _Acc::_Prev(_S);
        _Acc::_Next(_Acc::_Prev(_S)) = _S;
        ++_Size;  //個數加1
        return iterator(_S);
    }
    void insert(iterator _P, size_type _M, const _Ty &_X) //插入個數_M個，以下幾個調用前面函數；
    {
        for(; 0<_M; --_M)
            insert(_P,_X);
    }
    void insert(iterator _P, const _Ty *_F, const _Ty *_L) //區間的插入
    {
        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)); //實現插入功能
        _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;  //個數減少1個
        return _P;
    }
    iterator erase(iterator _F, iterator _L) //調用函數，刪除區間
    {
        while(_F != _L)
            erase(_F++);
        return _F;
    }
    void clear() //清除所有空間
    {erase(begin(), end());}

#endif

4、總結：

  (1)、迭代器的本質有了了解，是一個內部類，它將是一個對象，內部數據成員是一個指向節點的指針；

  (2)、迭代器對->的重載返回的是節點內部數據的地址，而不是節點的地址；

  (3)、迭代器對每種數據結構的實現均不相同，(Stack, queue, list...........)

  (4)、空間配置器：對所有的數據結構而言，只有一份，

  作用：申請，釋放空間，構造，析構對象；