一、list 的介紹

1. list 是可以在常數范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
2. list 的底層是雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和后一個元素。
3. list 與 forward_list 非常相似：最主要的不同在于 forward_list 是單鏈表，只能朝前迭代，已讓其更簡單高效。
4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執行效率更好。
5. 與其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問 list 的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list 還需要一些額外的空間，以保存每個節點的相關聯信息(對于存儲類型較小元素的大 list 來說這可能是一個重要的因素)。

二、list 的模擬實現

list 學習時也要學會查看文檔：list 文檔介紹，在實際中我們熟悉常見的接口就可以，下面我們直接開始模擬實現，在模擬實現中我們實現的是常見的接口，并且會在實現中講解它們的使用以及注意事項。

首先跟以往不一樣的是，list 是一個個節點連接起來的，所以它不是連續的物理空間，這也就意味著，它不用擴容，每次插入的時候只需要申請一個節點，然后連接起來即可；

其次，list 底層的迭代器實現也跟 string和 vector 不一樣，它們兩個的迭代器可以說是原生指針，但是 list 的迭代器是要讓節點指向下一個節點，所以底層實現也不一樣；例如我們想讓迭代器 it，往后迭代，就是 ++it，但是底層的實現卻不是真的讓節點++，因為它們的空間不是連續的，所以我們要把 list 迭代器封裝成一個類。

首先我們先創建一個自己的命名空間，把 list 節點的類，list 迭代器的類，list 類都放進去；

1. list 節點類

list 節點類如下，因為是雙向鏈表，所以應該有一個數據，兩個指針；

		namespace Young{// list 節點類template <class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}};}

2. list 迭代器類

首先我們先定義一個類模板，其參數有三個，分別是類型、類型的引用(const 和 非const) 、類型的指針(const 和 非const) ；

為什么要定義三個模板參數呢，因為考慮到 const 迭代器，const 迭代器和普通迭代器不是同一個類，不能直接在 iterator 前直接加 const，如 const iterator ，這不是 const 迭代器，因為這里的 const 修飾的是迭代器本身，就是迭代器本身不能修改，但是我們期望的是迭代器本身可以被修改，如 it++、++it，只是期望迭代器指向的內容不能被修改，如 *it = 10、it->10 ；

這就類比 const T* 和 T* const ， const T* 中 const 是修飾指向的內容不能被修改，而 T* const 中 const 修飾的是指針本身不能被修改；而我們需要實現的 const 迭代器 是要滿足第一種的，所以 list 中普通迭代器和 const 迭代器 是兩個完全不一樣的類，應該寫成兩個類，但是我們可以通過增加兩個模板參數 類型的引用(const 和 非const) 、類型的指針(const 和 非const) 來復用普通迭代器，具體實現如下：

		// list 迭代器類template <class T,class Ref,class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;// 迭代器構造函數__list_iterator(Node* node):_node(node){}}

首先我們先將節點類起別名為 Node，再將自己的類起別名為 self；迭代器本身也是一個指針，只是它內部實現不一樣，所以我們需要一個 _node 節點的指針，構造函數實例化一個節點的指針，比如說 list<int>::iterator it = lt.begin();，這里的 it 就會調構造函數，實例化一個 lt.begin() 節點的指針，其實 lt.begin() 就是指向頭節點的指針。

接著我們重載一些迭代器常用的運算符：

（1）前置++

就是讓迭代器往后迭代，具體的實現就是讓節點的指針指向下一個節點：

			// 前置 ++self& operator++(){_node = _node->_next;return *this;}

（2）后置++

跟前置++的區別就是，后置++需要拷貝，返回++以前的迭代器，所以一般都不用后置++；

			// 后置 ++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}

（3）前置- -、后置- -

前置- -、后置- - 與 ++ 的區別就是， - -返回上一個節點的迭代器；

			// 前置 --self& operator--(){_node = _node->_prev;return *this;}// 后置--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}

（4）!= 和 == 運算符重載

!= 運算符重載就是比較它們的節點是否相等；== 運算符就相反；

			// != 運算符重載   iterator it != lt.begin();bool operator!=(const self& s){return s._node != _node;}// == 運算符重載   iterator it == lt.begin();bool operator==(const self& s) {return s._node == _node;}

（5）* 解引用重載 和 -> 重載

解引用重載 和 -> 重載 就是改變迭代器指向內容的兩個運算符，所以我們定義的三個模板參數，就在這里起作用了；比如我們實例化的模板參數是 const 迭代器 的 __list_iterator<T, const T&, const T*>，這里的 const T& 就是 Ref，const T* 就是 Ptr，這里就可以直接用 Ref （解引用重載）和 Ptr（箭頭重載） 作返回值；

如果是 非const 迭代器的 __list_iterator<T, T&, T*>，T& 就是 Ref，T* 就是 Ptr；所以就可以根據它們的類型返回對應的迭代器類型，就不需要我們自己寫兩個迭代器的類了。

			// * 解引用重載Ref operator*(){return _node->_data;}// -> 重載Ptr operator->(){return &_node->_data;}

解引用 和 -> 重載的使用：

假設 list 里面存的類型是一個自定義類型，這個自定義類型中有兩個成員變量，那么我們在使用 解引用 和 -> 重載的時候，應該訪問哪一個呢？這時候就需要我們指定訪問了，如下代碼：

		struct AA{AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;};void test4(){Young::list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));Young::list<AA>::iterator it = lt.begin();while (it != lt.end()){// 使用解引用//cout << (*it)._a1<<" "<<(*it)._a2 << endl;//使用 ->cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;}

上面的 cout << it->_a1 << " " << it->_a2 << endl; 調用了->重載，實際上是 cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;，本來應該是有兩個 -> 的，即 it->->_a1 但是這樣寫可讀性不好，所以編譯器特殊處理，省略了一個 ->。

3. list 類

list 類首先將 const 迭代器和非 const 迭代器類型起別名為 const_iterator 和 iterator ；成員變量有 _head 哨兵位節點和 _size 記錄鏈表的長度，如下：

		// list 類template <class T>class list{public:typedef list_node<T> Node;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;private:Node* _head;size_t _size;};

（1）迭代器

注意，begin() 是哨兵位的下一個節點，end() 是哨兵位節點。

begin() 和 end() 返回的類型也是一個迭代器，這里 iterator(_head->_next) 是調用迭代器類的構造函數，構造一個節點的指針返回；也可以寫成 _head->_next，因為支持隱式類型的轉換；

			// 非 const 迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}// const 迭代器const const_iterator begin() const{return const_iterator(_head->_next);}const const_iterator end() const{return const_iterator(_head);}

（2）修改相關的接口

swap()

交換鏈表數據，需要借助標準庫的 swap 函數實現：

			// 交換鏈表數據void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}

insert()

在 pos 迭代器插入節點；新開一個節點，然后插入指定迭代器的位置，連接好 prev 和 cur 的位置即可；因為 list 的底層結構為帶頭結點的雙向循環鏈表，因此在 list 中進行插入時是不會導致 list 的迭代器失效的；

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

erase()

刪除 pos 迭代器位置的節點；在刪除時迭代器會失效，并且失效的只是指向被刪除節點的迭代器，其他迭代器不會受到影響，所以 erase() 函數執行后，it 所指向的節點已被刪除，因此 it 無效，在下一次使用 it 時，必須先給其賦值；

			// 刪除節點iterator erase(iterator pos){Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;pos._node->_next = pos._node->_prev = nullptr;--_size;return next;}

push_back、push_front、pop_back、pop_front

只需要復用 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());}

clear()

清空鏈表數據，刪除除了哨兵位的節點即可；

			// 清空鏈表數據void clear(){iterator it = begin();while (it != end()){it = erase(it);}}		

以上修改接口配合迭代器的使用如下圖：

（3）空鏈表初始化

			// 空鏈表初始化void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}

（4）構造函數

構造函數只需要創建一個哨兵位即可；

			// 構造函數list(){empty_init();}

（5）拷貝構造函數

拷貝構造函數直接初始化，然后插入數據即可；

			// 拷貝構造函數 -- lt2(lt1)list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}

（6）賦值運算符重載

現代寫法，傳參的時候調用拷貝構造，然后交換數據即可；

			// 賦值運算符重載 -- lt2 = lt1list<T>& operator=(list<T> lt){swap(lt);return *this;}

（7）析構函數

清空鏈表數據之后再釋放哨兵位的節點即可；

			// 析構函數~list(){clear();delete _head;_head = nullptr;}

4. 打印容器的接口

（1）打印鏈表整型的接口

像 vector、list 這些容器都沒有重載流插入運算符，所以我們可以自己實現一個打印的接口函數；我們先來實現一下打印鏈表整型的接口：

		// 打印鏈表 -- 只能針對 int 類型void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it = 10; errorcout << *it << " ";++it;}cout << endl;}

此接口可以打印鏈表的數據，但是只能針對 int 類型，我們可以對它進行改造一下，使用模板。

（2）打印 list 的接口

我們學了模板，就可以利用模板實現泛型編程，將類型改為模板的泛型，即可打印 list 中的不同類型，如下：

		// 打印鏈表 -- 只能打印 list 容器template<typename T>void print_list(const list<T>& lt){typename list<T>::const_iterator it = lt.begin();while (it != lt.end()){//*it = 10; errorcout << *it << " ";++it;}cout << endl;}

這里的模板參數使用了 typedef 關鍵字，這里必須使用 typedef 關鍵字，而且在指定類域前還要加上 typedef 關鍵字，如 typename list<T>::const_iterator it = lt.begin();；因為在模板還沒有進行實例化的時候， const_iterator 就到 list<T> 的類域中尋找類型，此時類中還沒有實例化參數 T，所以編譯器分不清它是類型還是靜態變量，不能去 list<T> 里面找，所以在前面加 typedef 關鍵字就說明它是個類型，編譯器在等 list<T> 實例化后，再去類里面去取根據類型去取類型。

但是上面的接口還是不夠完美，要是我想打印 vector 呢？那還是不能打印出來，所以我們可以實現一個專門打印容器的接口；

（3）打印容器的接口

我們使用模板參數代表容器，讓編譯器到指定容器去取它的迭代器即可；

		// 打印容器 -- 能打印各種容器template<typename container>void print_container(const container& con){typename container::const_iterator cit = con.begin();while (cit != con.end()){cout << *cit << " ";++cit;}cout << endl;}

使用如下圖：