前言

? ? ? ? 我們知道，stl中的vector對應數據結構中的順序表，string類對應字符串，而今天要講的list類對應帶頭雙向鏈表，并不是對應單鏈表，帶頭雙向鏈表的基本操作在數據結構課程中已經學過，所以今天即將要講的常見接口并不是重點，重點是list的迭代器的實現。

????????我們也知道，string、vector的迭代器就是原生指針，如果使用原生指針可以實現list的迭代器嗎？答案是不行，因為list的數據并不是一塊連續的存儲空間，無法像指針那樣取訪問元素，但是為了保持所有容器迭代器的使用一致，我們如何實現list的迭代器才能像原生指針那樣通過++、--去控制，這里就體現出了封裝的重要性，快往下看看吧！

重要接口實現

框架

? ? ? ? 通過下方代碼可以看出，實現了一個節點類模板存儲節點，一個鏈表類模板存儲鏈表，

①使用類模板是因為存儲元素可以自由指定，不是像以前一樣通過typedef固定了每個鏈表的元素類型；

②節點類模板使用struct，而不使用class，是因為struct的默認權限是public，鏈表類模板可以自由訪問其成員變量，而class默認權限是private，當然用class指定public權限也可以，

節點類模板中通過構造函數初始化元素，鏈表類模板成員是一個節點指針，可以在構造函數中申請一個節點充當頭節點。

代碼：

template <class T>
struct ListNode
{//構造函數用來創節點ListNode(const T& x = T()):_data(x), _prev(nullptr), _next(nullptr){}T _data;ListNode<T>* _prev;ListNode<T>* _next;
};template <class T>
class List
{typedef ListNode<T> Lnode;  //作用：下面寫ListNode<T>較麻煩，typedef一下，使用Lnode較方便public://...private:Lnode* _head;
};

默認成員函數

? ? ? ? 因為在所有構造函數前都需要先初始化成員變量（為頭節點申請空間并將左右指針置空），所以封裝了一個函數empty_init在每個構造函數前直接調用，

? ? ? ? 所有默認成員函數的實現與string、vector中的如出一轍，不太理解的可以參考一下之前的文章，不是重點這里不再贅述。

代碼：

	//創建并初始化頭節點，放于構造函數的最前面void empty_init(){_head = new Lnode();_head->_next = _head->_prev = _head;}//構造函數List(){empty_init();}//普通拷貝構造函數List(const List& L)   //注意：類外必須是List<類型名>，類里可以是List，但建議List<T>{empty_init();auto it = L.begin();while (it != L.end()){push_back(*it);it++;}}void swap(List<T>& L){std::swap(_head, L._head);}//傳迭代器區間構造函數template <class InputIterator>  List(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}//拷貝構造函數//現代寫法List(const List<T>& L){empty_init();List<T> tmp(L.begin(), L.end());swap(tmp);}//賦值運算符重載//現代寫法List<T>& operator=(const List<T>& L){List<T> tmp(L.begin(), L.end());swap(tmp);return *this;}//更狠的現代寫法List<T>& operator=(List<T> L)   //直接傳一個拷貝過來，相當于上面的tmp，函數結束自動釋放{swap(L);return *this;}//清除除了頭節點之外所有的節點void clear(){auto it = begin();while (it != end()){it = erase(it);}}//析構函數~List(){clear();_head->_next = _head->_prev = nullptr;delete _head;_head = nullptr;}

迭代器（重點）

1.引言

? ? ? ? 還記得vector、string的迭代器實現嗎？typedef T* iterator;? ?typedef const T* const_iterator;? ?，只是原生指針對不對，然后typedef一下，就可以使用了，因為指針可以在一塊連續的地址空間++或--訪問元素，但是鏈表中的節點指針++、--訪問元素可以嗎，答案是不可以，但為了保持迭代器使用一致，就應該遇到鏈表的迭代器使用++、--也可以達到一樣的效果，因此就想到了操作符重載，將++、--、*? 重載成我們希望達到的效果，而實現操作符重載就必須將其封裝成一個類。

? ? ? ? 從引言中就可以看出list與之前學過的容器迭代器實現的不同之處，list迭代器是通過封裝成類實現，但迭代器有兩種（暫時先不提反向迭代器），一種普通迭代器，一種const迭代器，兩種迭代器的實現應該大致內容都一樣，小部分不一樣（比如，const迭代器的解引用應該返回const不可類型的變量），那我們應該先寫好普通迭代器的實現，再復制粘貼成const迭代器然后修修改改嗎？漏！大漏特漏！接觸過模板這個概念之后，應該可以想到這里用到模板。

2.list迭代器類實現?

1）框架?

? ? ? ? 見下方代碼，?實現list的迭代器這個__list_iterator類模板，參數列表中的T、Ref、Ptr分別是數據類型、此類型的引用、此類型的指針（比如，T是int，Ref就是int&，Ptr就是int*）（為什么需要指針參數在操作符->重載處有說明），填入的參數不同就是不同的類，這里list的迭代器需要兩個類，一個普通迭代器的類，一個const迭代器的類，在list類實現中去定義即可。

? ? ? ? 針對list迭代器類模板的實現，成員變量是節點的指針，而構造函數則是傳入一個節點指針可初始化一個list迭代器，不需要自己提供析構函數。

代碼：

template <class T, class Ref, class Ptr>
struct __list_iterator
{//注意：這兩個typedef只是因為ListNode<T>、__list_iterator<T, Ref, Ptr>很麻煩寫，所以簡化一下，也方便理解typedef ListNode<T> Lnode;typedef __list_iterator<T, Ref, Ptr> iterator;//構造函數__list_iterator(Lnode* p):_node(p){}//...Lnode* _node;   //鏈表中的迭代器表示節點的指針
};

2）?關系運算符重載

? ? ? ? 判斷兩個迭代器相不相等即判斷作為成員變量的結點指針是不是同一個指針變量，很容易理解，加上const是無論普通list對象還是const?list對象都可以調用。

代碼：

    bool operator==(const iterator& it) const{return _node == it._node;}bool operator!=(const iterator& it) const{return !(*this == it);}

?3）運算符++、--重載

? ? ? ? 針對list類，迭代器的++就是訪問下一個節點的迭代器，--是訪問上一個節點的迭代器，再注意好前置與后置的實現即可，不是很難。

代碼：

    iterator& operator++(){_node = _node->_next;return *this;}iterator operator++(int){iterator tmp(_node);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator tmp(_node);_node = _node->_prev;return tmp;}

4）操作符*重載

? ? ? ? list類中的迭代器解引用就是訪問此節點的數據，并且返回引用類型，即可操作其中的值，普通迭代器的Ref是普通引用類型，即可讀可寫，const迭代器的Ref是const引用類型，只可讀不可寫。

? ? ? ? 注意：不需要將此成員函數設置成const類型，就像本作者初學時所疑惑的，如果Ref是const T&,不應該對應const成員函數（Ref operator*() const）嗎？其實不然，list類的迭代器使用了類模板，參數不同就是不同的類，直接將兩種迭代器分開了，如果是普通迭代器，Ref就會傳進來T&，調用解引用重載時返回引用，可讀可寫，如果是const迭代器，Ref就會傳進來const T&，調用解引用重載時返回const引用，只可讀不可寫。

代碼：

	Ref operator*(){return _node->_data;}

?5）操作符->重載

? ? ? ? 正常情況下，操作符->可以解引用結構體指針再取其成員，那對于底層是節點指針的list迭代器，->就是對迭代器解引用再取其成員，所以針對_data如果是個自定義類型，那么->就可以取其成員，比如，_data是個自定義類型POS，有兩個成員，一個x，一個y，那么it->x,it->y表示迭代器取的POS中的x、y，如下圖測試，

????????仔細觀察->操作符重載的實現，it->x應該寫成it->->x才是對的，因為it->返回自定義類型指針，再->x返回其成員，這里其實編譯器做了處理，省略了一個->，提高了可讀性。

? ? ? ? 這里的Ptr就是數據類型的指針變量，將其地址返回，與引用形式一樣，需要從類模板參數列表輸入。

代碼：

    Ptr operator->(){return &(_node->_data);}

?測試：

3.list類中調用實現?

? ? ? ? 在實現完__list_iterator這個list類迭代器類模板之后，通過在list類中輸入不同的模板參數定義不同的類，這里需要普通迭代器類和const迭代器類，如下代碼，begin()是返回首元節點的迭代器，而end()是返回最后一個元素節點的下一個位置迭代器，即頭節點迭代器。

?代碼：

    typedef __list_iterator<T, T&, T*> iterator;  //普通迭代器類typedef __list_iterator<T, const T&, const T*> const_iterator;   //const迭代器類iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}

增刪查改

? ? ? ? 在理解了list的迭代器實現之后，對list的增刪改查想必是游刃有余，這里實現一下基本的插入刪除操作，結合之前在數據結構中的知識，insert、erase的實現應該可以很快寫出，值得注意的是，insert返回新插入節點的迭代器，erase返回所刪節點的下一位置的迭代器，而尾插、尾刪、頭插、頭刪直接復用即可。

代碼：

	iterator insert(iterator pos, const T& x){Lnode* newNode = new Lnode(x);pos._node->_prev->_next = newNode;newNode->_prev = pos._node->_prev;newNode->_next = pos._node;pos._node->_prev = newNode;return iterator(newNode);  //返回插入位置的迭代器}//尾插void push_back(const T& x){insert(end(), x);}//頭插void push_front(const T& x){insert(begin(), x);}iterator erase(iterator pos){assert(pos != end());Lnode* tmp = pos._node->_next;pos._node->_prev->_next = pos._node->_next;pos._node->_next->_prev = pos._node->_prev;delete pos._node;return iterator(tmp);}//尾刪void pop_back(){erase(--end());}//頭刪void pop_front(){erase(begin());}