1.前提準備

(1) list 的底層結構一般是帶頭雙向循環鏈表

(1)為避免命名沖突，需要創建一個命名空間來存放模擬實現的 list

(2)下面模擬實現list時，聲明和定義不分離(具體原因后續講解)

2.完整實現

2.1 鏈表節點

template<class T>//節點寫成類模板，適合不同的數據類型
struct __list_node//帶頭雙向循環鏈表的節點，因為下面會使用，用struct
{typedef __list_node<T> Node;//起個別名，謹防忘記實例化(即指定參數)Node* _next;Node* _prev;T _val;__list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}
};

(1)將鏈表節點寫成一個類模板，將數據類型指定為模板參數T，以支持不同類型的數據

(2)使用 struct 定義節點類，原因有二

1.后續所實現的鏈表,迭代器需要用到節點，使用 struct 方便暴露節點成員

2.用戶使用鏈表時，并不知曉節點的名稱等消息，強行使用而出錯的鍋不用實現者背

(3)不要將類模板名直接寫為node，因為后續還有樹等數據結構也有節點，

所以命名時通常加 list 前綴來區分

(1)節點包含指向前后的兩個指針，指針類型是節點類型，注意

類模板中，__list_node是類模板名，__list_node<T>是類型

謹防忘記，為類型起個別名

typedef __list_node<T> Node;//起個別名，謹防忘記實例化(即指定參數)Node* _next;Node* _prev;

(2)節點初始化，將指針置空，數據依用戶傳遞為主，缺省值為輔

__list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}

(1)后續實現鏈表時才會在堆上申請節點

節點內部并沒有申請其他資源，就沒必要在節點中寫析構函數等其他默認成員函數

等鏈表使用完畢，再在鏈表中進行資源釋放即可

2.2 鏈表中的迭代器

迭代器可以被理解為 抽象化的指針，它模擬指針的行為(遍歷和操作元素)，

使用方式與指針一致，但它的適用范圍更廣

(1)vector是動態順序表，內存連續分布，指針可以遍歷和操作元素

所以在vector中，指針就是一種迭代器

但是 list 的內存分布一般不連續，節點指針不可以遍歷和操作元素，

所以，我們定義一個迭代器類來封裝節點指針，通過運算符重載來模擬指針的行為，

此時，該迭代器類的對象就是鏈表的迭代器

	template<class T, class Ref, class Ptr>//節點指針類型是__list_node<T>*struct __list_iterator//list中需要使用迭代器，使用struct供下面使用{typedef __list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> Self;Node* _node;//用節點指針構造迭代器__list_iterator(Node* node):_node(node){}//it1 != it2bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}//*Ref operator*()const//Ref是引用的意思，用來控制普通迭代器與const迭代器{return _node->_val;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){iterator temp(*this);_node = _node->_next;return temp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self temp(*this);_node = _node->_prev;return temp;}Ptr operator->()const{return &(_node->_val);}};

2.2.1 迭代器的細節點

迭代器類的成員變量就是節點指針

(1)節點類型為：__list_node<類型>，為了支持不同類型的數據，將類型指定為參數T，

同時為了簡便，為節點起個別名 Node?

typedef __list_node<T> Node;

所以指針類型就是 Node*，

Node* _node;//用節點指針構造迭代器

(1)使用 struct 定義迭代器類，原因有二

1.后續所實現的鏈表中的常用接口需要用到迭代器，使用struct暴露成員直接供其使用

2.用戶使用鏈表時，并未知曉迭代器的完整信息，強行使用而導致出錯的鍋不用實現者背

(2)命名迭代器類時通常加 list 前綴來區分

(3)迭代器對象名字太長，起個別名Self，self 就是 自己的意思

typedef __list_iterator<T, Ref, Ptr> Self;

2.2.2 迭代器的構造函數

__list_iterator(Node* node):_node(node)
{}

(1)后續實現鏈表時，顯示傳遞一個節點指針以構造一個迭代器

(2)迭代器內部并沒有申請其他資源，就沒必要在迭代器類中寫析構函數等其他默認成員函數

2.2.3 迭代器間的比較

bool operator!=(const Self& it)
{return _node != it._node;
}bool operator==(const Self& it)
{return _node == it._node;
}

(1)迭代器之間的比較實際上就是 節點指針之間的比較，運算符重載即可

2.2.4 迭代器訪問數據

Ref operator*()//Ref是引用的意思，用來控制普通迭代器與const迭代器
{return _node->_val;
}

(1)指針解引用可以訪問到它所指向的數據，迭代器模擬指針

通過運算符重載，使得解引用迭代器就是 獲取 節點指針指向的數據

(2)Ref是引用的意思，用來控制普通迭代器與const迭代器,下面來仔細講解

2.2.5 普通迭代器與const迭代器的主要區別

不加const修飾的鏈表包含的是 普通迭代器，const 修飾的鏈表包含的是 const迭代器。

不加const修飾的鏈表中，節點的數據可以被修改，const 修飾的鏈表則相反

所以普通迭代器與const迭代器的主要區別就是，二者訪問數據的權限間的區別

普通迭代器 可讀可修改數據， const 迭代器 只可讀 數據

Ref operator*()//Ref是引用的意思，用來控制普通迭代器與const迭代器
{return _node->_val;
}

所以，將解引用返回值類型指定為模板參數

后續通過顯示傳遞不同解引用返回值類型(T&, const T&)(T為數據類型)，

就可以實現普通迭代器和const迭代器

2.2.6 迭代器的遍歷

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

(1)前置++，重載運算符，讓節點指針指向后一個節點，同時返回自己的引用即可

(2)后置++，重載運算符，讓節點指針指向后一個節點，同時返回自己的拷貝即可

(1)前置--，重載運算符，讓節點指針指向前一個節點，同時返回自己的引用即可

(2)后置--，重載運算符，讓節點指針指向前一個節點，同時返回自己的拷貝即可

2.2.7 重載 -> 運算符

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

struct A
{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}
};
void test_list2()
{list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << ' ' << (*it)._a2 << endl;cout << it->_a1 << ' ' << it->_a2 << endl;//it->->_a1有省略++it;}cout << endl;
}

當節點存儲的是一個自定義類型的數據的時候，想要訪問自定義類型的數據有兩個方法

//cout << (*it)._a1 << ' ' << (*it)._a2 << endl;
cout << it->_a1 << ' ' << it->_a2 << endl;//it->->_a1有省略

(1)解引用迭代器：(*it)._a1，通過?operator*?獲取對象，再用?.?操作符訪問成員。

(2)調用?operator->：it->_a1，通過?operator->?獲取對象的指針（或類指針對象），

再用?->?訪問成員

cout << it->_a1 << ' ' << it->_a2 << endl;//it->->_a1有省略

雖然訪問數據時省略了一個 ->

但是這行代碼是能正常運行并訪問數據的，實際上，為了簡潔，迭代器訪問自定義類型的數據時，只需要一個->即可，你可以認為編譯器能夠自動識別并補充這里的省略

重載->運算符返回的是自定義類型對象的地址(用指針接收)，

將指針類型指定為模板參數Ptr，

后續通過顯示傳遞不同解引用返回值類型(T*, const T*)(T為數據類型)，

就可以實現普通迭代器和const迭代器

2.3 鏈表中的常見接口

	template<class T>class list{typedef __list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;//迭代器需要放到外面使用，所以別名也要在public中typedef __list_iterator<T, const T&, const T*> const_iterator;//迭代器需要放到外面使用，所以別名也要在public中iterator begin(){return _head->_next;//單參數返回，調用構造函數生成臨時對象}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}//構造函數void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//lt(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//lt1 = lt2void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}//析構函數~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}_size = 0;}//尾插void push_back(const T& val){先找尾//Node* tail = _head->_prev;創造尾插節點//Node* newnode = new Node(val);_head tail newnode//_head->_prev = newnode;//newnode->_next = _head;//tail->_next = newnode;//newnode->_prev = tail;insert(end(), val);}void push_front(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}//insert\eraseiterator insert(iterator pos, const T& val){//創建新節點Node* newnode = new Node(val);//使用結點指針而不是迭代器進行鏈接Node* cur = pos._node;//prev newnode curNode* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;//prev cur nextNode* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;--_size;return prev;}size_t size()const{return _size;}private:Node* _head;size_t _size;};

2.3.1 鏈表中的細節點

(1)鏈表同樣是一個類模板，模板參數就是節點數據類型

(2)成員變量包含 哨兵位節點的指針_head 和 鏈表的大小_size (不包含頭節點的節點個數)

(1)使用 class 定義 list

不同于上述的節點和迭代器， list 需要實現封裝，只提供相應接口供外部使用

(1)節點類型為：__list_node<類型>，為了支持不同類型的數據，將類型指定為參數T，

同時為了簡便，為節點起個別名 Node?

typedef __list_node<T> Node;

注意，為了防止外部使用 Node, 需要將這行代碼寫在訪問限定符private的作用域之內

(2)迭代器對象名字太長，為符合日常使用習慣起別名如下：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

基于上述"普通迭代器與const迭代器的區別"，指定相應參數即可達到

注意，為了外部可以使用迭代器iterator,?

所以需要將這行代碼寫在訪問限定符public的作用域之內

2.3.2 鏈表中迭代器的接口

		iterator begin(){return _head->_next;//單參數返回，調用構造函數生成臨時對象}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}

(1)begin函數返回的是指向第一個有效節點(哨兵位的下一個位置)的迭代器

函數內部直接返回相應指針即可，

因為迭代器的構造函數是單參數類型，編譯器會用該指針構造出相應迭代器

(2)其他函數按要求返回相應指針即可

(3)注意，const迭代器相關函數只有const對象才能調用，所用需要用const修飾

2.3.3 鏈表的構造函數

		//構造函數void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}

(1)初始化一個鏈表就是創建一個頭節點，使其前后指針指向自己(起到雙向循環的作用)，

并把鏈表的大小置為0的過程，將這個過程抽象為一個函數，以供后續拷貝構造函數的使用

2.3.4 insert、erase函數

		iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;}

insert 通常是指 在 pos位置之前插入

(1)只實現的單元素的插入，插入位置 pos 的類型是迭代器，返回的是新插入節點的位置

(2)插入時只需要注意 插入節點，插入節點前一個節點與新節點之間的關系

因為迭代器改變指向有點麻煩，使用節點指針完成上述關系的鏈接

因為鏈表由哨兵位節點，不用考慮頭插為空

(3)插入一個節點，_size++

iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}

(1)不能刪除哨兵位節點，同時注意 _size--

(1)erase函數存在迭代器失效問題，返回被刪除節點的下一個節點的迭代器

(2)刪除時注意提前保存上一個節點和下一個節點即可

2.3.5 尾插尾刪頭插頭刪?

實現好了insert、erase函數以及迭代器的接口之后，

直接調用函數即可

		void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}

2.3.6 clear 與 析構函數?

        void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~list(){clear();delete _head;_head = nullptr;}	

?(1)clear函數的作用是清理有效節點，不包含哨兵位，

直接迭代器遍歷鏈表并刪除節點即可，注意將_size 置空

(2)析構函數就是在 clear 之后， 清理頭節點

2.3.7 拷貝構造函數

		list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}

拷貝構造一個鏈表，被構造對象首先需要進行初始化，

然后遍歷鏈表進行尾插即可

2.3.8 賦值重載函數

		void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//lt1 = lt2list<T>& operator=(list<T> lt){swap(lt);return *this;}

現代寫法，不用自己開空間，直接傳值傳參，

lt 是 lt2 的深拷貝(拷貝構造實現的是深拷貝)，然后交換兩個鏈表，傳引用返回

2.3.9 size函數

		size_t size(){return _size;}

前面的insert 、erase、clear函數已經對_size變量進行了相應操作

這里直接返回即可