在上一節中我們學習了STL中的vector這個容器，這節我們來學習一下另外一個常用的容器——list。
文章目錄
前言
一、list的介紹
二、list的使用及相關接口
1.list的使用
2.list的迭代器使用
3.list的相關接口
3.1 list capacity
3.2 list element access
3.3 list modifiers
三、list與vector的對比
四、list的模擬實現
前言
我們在vector中就已經介紹了C++中引入了STL的方便，這里我們就不多贅述了。我們上節所學習的vector，這個容器使用于那個存儲空間連續的結構，因為它的底層設計是數組實現的。對于那些存儲空間不連續的結構，如我們在數據結構中所學習的鏈表，它是有一個一個的指針連接起來的，這里我們就來學習一下這種容器——list。
一、list的介紹
上面這個介紹是引入C++文檔指導的，我們從上面的文檔中，我們可以知道list就是一個允許在任意位置進行插入/刪除的序列容器，它同樣可以使用迭代器，因此我們可以通過迭代器輕松遍歷list中的內容。
如上圖所示，我們在C++中所學習的list就是我們在數據結構中學習的帶頭雙向循環鏈表，因此我們可以往前遍歷，也可以往后遍歷。因此它的頭結點是一個關鍵的結點，我們要注意，后面我們在list的模擬實現中會著重介紹這個的。
二、list的使用及相關接口
1.list的使用
我們現在如果想要使用C++中的STL都是需要提前寫出它們的頭文件，并把它們包含起來，那么在主函數中，我們就可以直接使用它們了。list的頭文件包含就是#include<list>，我們包含這個頭文件之后，我們不僅可以使用list的迭代器還可以使用它的各種接口。
對于list對象的創建和之前的vector是一樣的，我們在實例化對象時，我們寫類類型的時候，我們要將類模板與數據類型一起寫上去，這樣才能夠算是一個數據類型。
template<class T> //我們定義類模板中的元素類型
list<T> //這就是一個list對象的數據類型
如上圖所示，我們可以構造一個空的list，也可以構造一個包含n個值為val的元素的list,我們還可以使用迭代器區間中的元素來構造list，除了上面哪幾種構造函數，我們其實還可以使用初始化列表來初始化list中的內容，初始化列表就是使用一對{ },里面放置的是我們想要進行初始化的內容。（這種構造方法我覺得挺香的，可以自己來初始化想要的內容，不然我們還得創建一個空的list，然后再逐個插入元素，才能得到我們想要的list)
2.list的迭代器使用
這里我們可以將迭代器認為是一個指針，但是它實際上比不是指針，只是功能與指針很相似，這點我們需要注意，我們學習就將它們進行一下類比學習。list中的迭代器與我們vector迭代器不一樣，由于vector中的存儲空間是連續的，因此它的迭代器就相當于原生指針，使用起來十分方便，但是list的存儲空間不連續，那么它的迭代器就不能用原生指針來代替。這里我們只是來初步介紹一下如何使用list的迭代器，至于list中的迭代器是如何實現的，我們在后面的模擬實現中會著重講解的。
對于容器的使用方式都是一個模板，我們首先先使用我們想要的容器類型來定義一個迭代器變量并給它初始化，我們一般把第一個迭代器作為初始值。后面我們根據自己的需求來使用迭代器。對于list的迭代器，我們就將容器類型換成list<int>即可。如下代碼是我們使用list迭代器進行遍歷訪問list中的元素。
對于迭代器的函數基本都是一樣的，如下圖中的那幾個函數就是迭代器的接口函數，我們根據不同的場合進行使用。
?
注意：
1.begin,end是正向迭代器函數，我們實行++操作的時候，迭代器向后移動；
2.rbegin,rend是反向迭代器函數，我們實行++操作的時候，迭代器向前移動。
3.list的相關接口
3.1 list capacity
對于list容器，它沒有像vector,string那樣的capacity函數，因為list是一個存儲空間不連續的結構，因此它的容量大小，我們無法通過函數接口來獲取，我們只能得到它當前的元素個數size，以及list是否為空。這兩個接口使用起來也是十分簡單的，和之前幾種容器的使用方法一樣，我們直接調用函數即可。
3.2 list element access
我們在介紹list的時候就已經說了list是一個帶頭雙向循環鏈表。因此對于它有兩個元素我們是可以直接獲取的：表頭元素，表尾元素。我們可以分別使用front和back這兩個函數來獲取。
3.3 list modifiers
list中那些增刪函數與vector中的函數接口基本差不多，兩者上面主要的區別就是list可以在表頭，表尾進行插入/刪除，而vector只能夠進行尾刪/尾插操作。它們兩個都沒有了find函數了（string類中有find函數），它們如果想要使用這個函數，可以直接使用庫中的find函數,對于庫中的find函數，原型如下所示：
輸入參數：我們要輸入一個迭代器區間，還有一個我們想要查找的值。我們一般使用這個函數使用下面這個模板(以list舉例）：
#include<algorithm>
#include<iostream>
#include<list>
using namespace std;
int main()
{int x;cin >> x;auto it = find(lt.begin(), lt.end(),x); //auto 推導出來的是迭代器類型return 0;
} 如下代碼，是插入/刪除等函數的代碼演示：
對于insert/erase這兩個函數，我要好好來介紹一下。這里list中的insert/erase函數，它們的返回值類型都是迭代器類型(這里vector中的也是一樣的）。而且我們傳遞的參數也是迭代器類型的參數或者迭代器區間。在vector中對于insert/erase中都會出現迭代器失效的情況，但是在list中insert并不會出現迭代器失效的情況，只有erase才會使得迭代器失效。因為我們在前面已經說了list是一個帶頭雙向循環鏈表，這里迭代器失效即迭代器所指的結點無效，即該結點被刪除了。因此插入結點時迭代器是不會失效的（我們每次插入的結點都是一個新的結點，都是有效的迭代器），而且erase導致迭代器失效的也只是指向被刪除的那個結點的迭代器失效了，其他的結點并沒有被影響。
這是文檔中list::insert的介紹，我們傳遞的參數是迭代器位置，我們插入的位置是我們傳遞的迭代器位置的前一個迭代器位置，這一點我們要記住。至于它的返回值就是我們插入的位置的迭代器。
這是文檔中list::erase的介紹，我們傳遞的參數迭代器就是我們想要刪除位置的迭代器，但是它的返回值我們要注意了，它的返回值是我們被刪除位置的下一個位置的迭代器。我們在vector中就說過了如何解決迭代器失效的方法：更新迭代器的值。因此，我們為了保證迭代器不會失效，我們可以將erase的函數返回值賦值給迭代器，那樣迭代器進行了更新，就不會出現迭代器失效的情況了。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函數執行后，it所指向的節點已被刪除，因此it無效，在下一次使用it時，必須先給
其賦值l.erase(it); ?++it;}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); ? ?// it = l.erase(it);}
}三、list與vector的對比
vector與list都是STL中非常重要的序列式容器，由于兩個容器的底層結構不同，導致其特性以及 應用場景不同，其主要不同如下：
四、list的模擬實現
#pragma once#include<assert.h>namespace hjc
{// 慣例// 全部都是公有，一般用structtemplate<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){}};// typedef list_iterator<T, T&, T*> iterator;// typedef list_iterator<T, const T&, const T*> const_iterator;template<class T, class Ref, class Ptr> //我們定義模板的時候，我們定義多個參數//我們除了定義元素類型的參數，還定義一個引用類型的參數和一個指針類型的參數//這個對于我們后面實例化出普通迭代器與const迭代器有著奇效struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self; //重命名的時候，我們要將上面模板中定義的參數都帶上Node* _node;list_iterator(Node* node):_node(node){}//下面重載*和—>運算符的使用，我們要使用上面定義的參數作為返回值//因為，我們普通迭代器與const迭代器的區別就是在這解引用，我們const修飾的是迭代器所指向的內容即頂層constRef operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//其余地方不變Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};template<class T>class list{typedef list_node<T> Node;public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*///本質上還是實現了兩個迭代器的類，這里不過是我們傳遞給模板參數，然后編譯器幫我們實例化出來兩種迭代器typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//begin,end函數需要我們自己來重新定義，上面模板生成的迭代器，只是對那些運算符進行了重載const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0; //初始化時，size=0}list(){empty_init();}// lt2(lt1) 拷貝構造，我們傳遞的參數是類類型的引用類型//我們先對其初始化，然后我們將值逐個插入到我們要拷貝的鏈表中list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt2 = lt3//list& operator=(list lt)//對于賦值運算符的重載，我們可以直接將兩個鏈表中的內容交換（交換一下頭指針即可）list<T>& operator=(list<T> lt){swap(lt); //使用我們自己實現的swap函數 這里實際是 this.swap(lt)return *this; //這是賦值后的鏈表內容，原來的鏈表內容交換給了lt//由于lt是一個局部變量，在這個函數結束的時候，然后它就自動銷毀了}//~list(){clear();delete _head;_head = nullptr;}//鏈表中的交換函數（直接交換兩個頭指針即可）std中的swap函數則需要重新創建兩個空間，然后分別將值拷貝過去void swap(list<T>& tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size); //兩個鏈表中的有效元素個數也要進行交換}//使用迭代器+erase直接將鏈表中的元素都刪除掉，但是這里可能會導致迭代器失效的情況，因此我們需要對迭代器進行更新//erase函數的返回值類型是迭代器類型，返回的迭代器是被刪除的緊接著的下一個迭代器位置void clear(){auto it = begin();while (it != end()){it = erase(it); //因此我們直接將erase的返回值賦給it,這樣就相當于對迭代器更新+向后移動一位了}}//構造函數（構造n個相同值）list(size_t n, const T& val = T()){empty_init();//初始化 for (size_t i = 0; i < n; i++) //由于這里已經明確給了多少個元素了，于是我們就使用普通的for循環來插入值{push_back(val);}}//尾插 我們首先要定義一個要插入的新結點，然后找出插入結點與頭結點等結點的關系//使用使用指針連續關系即可void push_back(const T& x){//定義兩個新的結點/*Node* new_node = new Node(x);Node* tail = _head->_prev;//首先處理中間的tail->_next = new_node;new_node->_prev = tail;//然后處理后面的new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x); //我們可以直接使用insert來進行復用//end()即_head位置，這里是頭結點之前的位置，即鏈表尾的位置}void push_front(const T& x){insert(begin(), x); //begin()=>_head->_next，頭結點的下一結點位置}void pop_front(){erase(begin());}void pop_back(){erase(--end()); //--end()指向的是頭結點的上一個元素，即鏈表的最后一個元素}//插入位置是我們指定位置（pos)之前一個位置插入元素iterator insert(iterator pos, const T& val) {Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}//返回的位置為被刪除位置的下一個迭代器位置iterator erase(iterator pos) //參數即為要刪除位置{assert(pos != end()); //我們不可以刪除頭結點位置的值（頭結點指向的內容不是有效內容Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;--_size;return iterator(next);}private://這里，我們定義了兩個成員變量，一個頭指針，一個是元素的有效個數//size我們直接定義為成員變量，在上面的函數中如果有修改的地方我們就直接進行修改Node* _head;size_t _size;};//函數模板，這是std庫中的//這個函數模板需要重新創建空間，然后拷貝內容過去template <class T>void swap(T& a, T& b){T c(a); a = b; b = c;}//這是list庫中的swap函數模板template <class T>void swap(list<T>& a, list<T>& b) //傳遞兩個鏈表類型的引用作為參數{a.swap(b); //實際是對我們上面那個swap的函數的一個封裝，寫這個函數是想讓編譯器優先使用這個函數，而不用上面那個函數模板}
}對于上面的list的模擬實現，我主要講解一下，迭代器的模擬實現。由于list是個鏈表由一個個的節點所組成的，因此我們并不能夠像之前的vector那樣，直接使用原生指針typedef即可。我們需要使用類來進行封裝。我們要將迭代器的那些操作（運算符的重載）都封裝到一個類中，但是迭代器又有還幾種迭代器（這里我們就實現比較簡單的迭代器：普通迭代器和const迭代器，至于方向迭代器我們這里就暫時不模擬實現）我們知道兩種迭代器的實現功能都是不一樣的但是又很相似，如果我們為了const迭代器再重寫一個類，這樣就顯得有點冗余（其中許多操作都是相似的，只是幾處有所差別）于是，我們就在模板上做點手腳：我們在模板參數中多設定幾個參數：一般我們寫模板參數時只寫一個參數：類中對象的數據類型，這里我們加了兩個參數：一個引用類型的參數Ref，一個指針類型的參數Ptr。對于const迭代器，const修飾的是迭代器所指向的內容，我們并不能簡單的使用const來修飾我們最初模擬實現的普通迭代器然后typedef就行了。我們需要修改它們解引用操作的那幾個運算符，因此我們直接在模板中給定參數，在我們實例化時，我們給定我們想要的參數就行了。其實，我們在模板中多設定幾個參數，然后再傳遞參數來實例化就是讓編譯器幫我們寫兩個迭代器的類，這樣的粗活就不用我們自己親自來做了。
)
