🔥 本文專欄：c++
🌸作者主頁：努力努力再努力wz
💪 今日博客勵志語錄：
當你覺得累的時候，說明你在走上坡路
★★★ 本文前置知識：
模版
那么在之前的學習中，我們已經學習了string和vector這兩種容器，而今天我們要學的新的容器便是我們的list，那么有了之前學習string以及vector這兩個容器的基礎，那么對于上手list來說，那么想必也是不那么困難，因為stl規定每一個容器的很多的成員函數是相似的，那么廢話不多說，讓我們進入list的學習
1.引入
那么list這個容器其實對我們來說并不陌生，那么list的本質其實就是我們的鏈表，而這里的list的底層則是采取的帶頭雙向循環鏈表來實現的，那么所謂的帶頭雙向循環鏈表，就是會有一個哨兵節點，哨兵節點作為頭節點，但是其并不存儲任何有效的數據，它的作用只是為了能夠讓我們訪問定位到該鏈表，而該鏈表中的每一個節點具有兩個指針域，分別指向邏輯上相鄰的前驅節點以及后繼節點，并且該鏈表的最后一個節點還會與哨兵節點相連，這也是它的名字為什么帶有循環兩個字，那么帶頭雙向循環鏈表的這一個結構，我們就可以形象的用一圈環形的跑道到來理解，那么起點線位置處就是我們的哨兵節點，那么終點位置處就在起點位置處后方
那么正是由于list采取的是帶頭雙向循環鏈表，所以能夠讓我們訪問鏈表中的節點可以向前或者向后訪問，而不是像單鏈表那樣的只能單向的遍歷，那么這就是帶頭雙向循環鏈表的優勢，也是為什么c++的設計者選擇用帶頭雙向循環鏈表作為我們list的底層實現而不是采取單鏈表或者雙向不循環鏈表，那么知道了list的底層是采取的何種數據結構還不夠，那么我們要完整的了解與掌握list，那么我們就得知道list的三個方面的內容，分別是list的成員變量以及list的成員函數以及list的迭代器，那么接下來后文的內容我會分為兩個維度來解析list，分別是list本身的成員變量以及函數的介紹和list的模擬實現也就是嘗試自己造一個list，那么一旦你成功模擬實現了list，那么你就可以更為熟悉以及使用list
list成員變量
我們知道list的底層是采取的帶頭雙向循環鏈表，那么上文我們介紹了帶頭雙向循環鏈表，那么我們要訪問帶頭雙向循環鏈表，那么我們只需要知道一個節點的地址即可，那么該節點就是哨兵節點，而這也就是哨兵節點的作用，就是用來定位以及訪問該帶頭雙向循環鏈表，所以它不存儲任何的數據，而list的類中就只有一個成員變量，那么便是哨兵節點的地址，也就是維護一個指向該帶頭雙向循環鏈表的哨兵節點的指針，那么我們訪問遍歷該帶頭雙向循環鏈表，那么就只能從哨兵節點位置開始，可以沿著兩個方向，要么往前遍歷，要么往后遍歷
那么這里list是一個模版類，其中封裝了關于圍繞帶頭雙向循環鏈表增刪改查等功能的成員函數和一個指向一個哨兵節點的指針，但是我們卻發現這里list內部還缺少了一個東西，那么就是關于該帶頭雙向循環鏈表的節點，我們并沒有給出節點的定義，因為list是一個模版類，那么到時候它會被編譯器實例化，編譯器會識別在代碼中list對象存儲的數據類型從而根據模版然后實例化對應的一個list類，但是由于list類內部只有一個指向節點的指針，那么到時候編譯器在實例化該模版類的時候，肯定會尋找該節點的定義，所以這里就需要我們給出節點的定義，并且對于節點來說，我們也要定義成模版，因為到時候節點究竟存儲的是哪種數據類型的數據，那么我們并不清楚，所以需要我們定義一個節點的模版類，那么我們定義節點的模版類有兩種方式，那么第一種方式就是我們利用模版的嵌套，也就是在list模版類內部再嵌套定義一個list_node模版類，這種方式可行是可行，到時候實例化list模版類的同時會先實例化list_node模版類，但是對于我來說，我更喜歡第二種方式，便是將list_node單獨聲明成一份獨立的模版，而我們的list的模版類中就定義一個指向list_node模版類的節點的指針
那么這種方式就需要我們注意一個細節，那么一旦我們的模版內部使用了外部定義的模版函數或者模版類，那么此時使用了外部模版的該模版類或者函數便作為主模版，當我們編譯器是實例化主模版的時候，那么編譯器并不是立刻實例化，因為編譯器知道，在主模版中可能會用到外模版的函數或者類，所以這里編譯器會采取先優先實例化外模版的函數或者類，如果外模版還使用了其他的外模版，那么編譯器會構建一棵實例化樹，最后再來實例化主模版，所以這里在定義的時候，就要求我們使用外模版的函數或者類，那么我們一定要在后面加模版參數，比如我們的外模版是一個list_node類，那么list類中的成員變量使用了list_node外模版類作為其數據類型，那么這里我們list類中聲明該成員變量的時候，一定得是：
template<typename T> class list_node {}; template<typename T> class list {list_node<T>* node };那么這個list類中的成員變量前面數據類型 的 < T > 模版參數是必須要帶的，如果你不帶，而是寫成list_node* node，那么此時編譯器會將該成員變量視作一個自定義類型，那么它會到全局域中去尋找該自定義類型的定義而不會去尋找模版類，同理對于函數也是一樣
其次就是如果遇到這樣的場景，也就是我們的外部模版它是一個嵌套類型，也就是它里面還定義了一個模版類或者函數，比如：template<typename T> class node1 {template<typename u>class node2{template<typename o>class node3{}} }那么此時如果說我們的主模版中要用到外模版中的嵌套類型，比如這里我主模版要用到外模版中嵌套在最里層的node3，那么這里我主模版在聲明的時候，光是寫模版參數還不夠，那么還得告訴編譯器它是一個嵌套的模版，那么就需要我們手動添加typename以及template關鍵字
比如：
template<typename T> class main_tem {typename node1<T>::template node2<U>::template node3<o> member; }那么typename則是在數據類型的最前面，那么它告訴編譯器，我typename之后的內容代表著一個數據類型，那么template則是聲明在嵌套的模版類之前，那么這里之所以要加template則是因為要告訴編譯器我后面的 <> 的內容是模版參數，而不要給我識別成運算符<以及 > ，而這里對于我們list主模版類來說，那么我們沒有使用嵌套的模板類或者函數，就不需要添加typename以及template關鍵字
那么該list_iterator模版具有三個成員變量，分別是兩個指針prev和next，分別指向前驅節點以及后繼節點，還有一個數據域val，那么我們這里還要定義構造函數，分別定義一個無參數的構造函數，也就是將兩個指針初始化為nullptr將數據域初始化為默認值（內置類型為0，自定義類型調用其默認構造函數），而帶參數的構造函數則是接收一個參數，那么該參數就是用來初始化數據域，那么這就是我們的list_node模板類的構造函數，還要注意的就是這里我們list_node類中的成員變量的訪問權限得設置為public,因為到時候我們list肯定有刪除以及添加節點，需要修改指針，那么這里之所以設置public是因為我們到時候list類能夠直接訪問list_node的成員變量從而直接修改其值，如果你硬要設置成private，那么則需要你在額外定義相關修改的接口，那樣顯然麻煩并且沒有必要，因為到時候，我們的list的成員變量也就是指向哨兵節點的指針會設置為private，那么其實不用擔心外部訪問到list_node的成員變量
template<typename T>
struct list_node
{struct list_node<T>* next;struct list_node<T>* prev;T val;list_node():next(nullptr), prev(nullptr), val(T()){}list_node(const T& data):next(nullptr), prev(nullptr), val(data){}
};
template<typename T>
class list
{private:list_node<T>* head;
}
list成員變量
那么我上文介紹了list的成員變量，那么下一部分內容就是介紹list的成員函數，那么list的成員函數的功能主要圍繞著增刪改查，那么在介紹這些相關功能的函數之前，那么我們首先應該認識的，就是list的構造函數
構造函數
那么我們知道list的成員變量是一個指向哨兵節點的指針，那么list類也重載了多個版本的構造函數來滿足用戶的不同的初始化需求，那么首先就是無參數的構造函數，那么該構造函數完成的內容，就是得到一個空鏈表，那么所謂的空鏈表不是一個節點都沒有，而是只有一個哨兵節點，所以無參的構造函數所做的工作，就是開辟一個哨兵節點并且讓哨兵節點的前驅以及后繼指針都指向自己
list()
{head = new list_node<T>;head->next = head;head->prev = head;
}
那么接下來就是帶參數的構造函數，那么首先就是list可以接收兩個參數，分別是你要設置改帶頭雙向循環鏈表的節點的數量，以及這每一個節點的val值，那么如果你沒給val值，那么則是提供一個缺省參數，給其設置默認值，內置類型為0，自定義類型則是其調用默認構造函數，那么它的實現原理，就是首先還是給哨兵節點開辟空間，接著，我們在定義一個變量prevnode來指向其前驅節點，然后定義一個循環，循環n次，每次創建一個節點，然后將其與前驅節點鏈接，最后退出循環后，此時的prevnode就是最后一個節點，然后再與哨兵節點連接即可
list(size_t n, const T& val)
{head = new list_node<T>;node prevnode = head;while (n--){node newnode = new list_node<T>(val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;}prevnode->next = head;head->prev = prevnode;
}
接著就是支持一個迭代器區間初始化的構造函數，那么實現原理則是首先為哨兵節點開辟空間，然后還是額外定義一個prevnode變量指向要鏈接的前驅節點，然遍歷迭代器區間，拷貝迭代器區間的節點的數據，然后創建新節點并且與前驅節點prevnode鏈接，退出循環后，此時prevnode就指向的是尾節點，再與哨兵節點鏈接
list(iterator first, iterator last)
{head = new list_node<T>;node prevnode = head;iterator it = first;while (it != last){node newnode = new list_node<T>(it.re_node()->val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;it++;}prevnode->next = head;head->prev = prevnode;
}
拷貝構造函數
那么對于拷貝構造函數來說，那么它的作用也是用來初始化list，那么我們可以用一個已經初始化好的list對象來初始化一個還未初始化的list對象，那么對于拷貝構造函數的實現原理，那么首先還是給哨兵節點開辟空間，然后我們在依次遍歷初始化好的list對象，每次遍歷會創建新的節點，拷貝對應的已經初始化好的節點的數據，然后再處理鏈接關系即可，那么實現思路和上文的構造函數是大體一致的，只不過這里我偷了個懶，復用了push_back函數
list(const list<T>& l1)
{head = new list_node<T>;head->next = head;head->prev = head;const_iterator it = l1.begin();while (it != l1.end()){push_back(*it);++it;}
}
迭代器
那么我們知道容器中的數據都是被定義為了私有屬性，那么我們在外部是無法直接訪問到容器內部的數據，那么為了讓外部能夠訪問到容器內部的數據，那么容器都統一對外提供了迭代器來讓我們通過迭代器來訪問容器里面的數據，在此前我們學習了string以及vector，那么我們知道由于string以及vector的底層結構采取的是數組的方式來實現，所以對于string以及vector迭代器來說，那么它們就可以采取原生指針來實現，因為數組的物理空間是連續的，而指針的算術運算比如自增以及自減運算，那么都是向前以及向后移動移動的長度其指向的數據類型的大小一樣，所以對于vector來說，那么它的迭代器就可以直接利用原生指針本身的自增以及自減就能夠達到訪問到下一個元素的效果，所以它的迭代器就可以直接采取原生指針來實現其隨機訪問的一個特性
那么對于list來說，由于list的底層結構采取的是帶頭雙向循環鏈表的方式來實現，那么對于鏈表來說，我們知道它的每一個節點的在物理內存并不是連續的，那么由于節點的物理位置不連續，那么list的迭代器就不能單純按照之前vector以及string那樣還是采取原生指針，因為指針的自增向后移動的單位的長度是其指向的數據類型的大小，但是鏈表的節點的物理位置是隨機分布的，所以這些節點是邏輯上相鄰而并非物理上相鄰，而要訪問邏輯上相鄰的節點就只能將指針指向的節點的next指針的值賦給它從而訪問到下一個節點，其次就是* 運算符，那么它是解引用迭代器所指向的節點，也就是獲取迭代器指向的節點的數據域里面的內容，而我們的每一個節點是一個結構體，其中包含三個成員變量，那么如果是原生指針，那么直接解引用的是無法得到該結構體的成員變量的值的，那么結構體指針解引用得通過->運算符獲取成員變量的值。
所以根據上文的分析，我像明確的一個道理就是：list是無法單純僅僅采取原生指針來實現的，但是我們還是想要實現關于list迭代器的自增以及自減和解引用，而自增和自減的目的就是為了訪問到邏輯上相鄰的節點，那么單純靠原生指針的自增以及自減是無法做到，那么必然就需要我們利用運算符重載，來重寫這些運算符的行為，所以list的迭代器將其封裝成了一個list_iterator類，里面封裝了各種適應list也就是帶頭雙向鏈表結構的各種運算符重載的成員函數
成員變量
那么既然我們list的迭代器被封裝成了list_iterator類，那么接下來我們就得需要知道該list_iterator的成員變量以及成員函數，那么list_iterator的成員變量就是一個指向節點的指針，因為我們知道list的迭代器只是無法單純的采取指針的算術運算，需要我們重載一些指針運算相關的運算符重載函數
成員函數
構造函數
那么list的成員函數首先談的肯定就是我們的構造函數，那么由于迭代器的成員變量只有一個指向節點的指針，那么迭代器的構造函數首先就是無參數的構造函數，那么將其成員變量初始化為nullptr，然后還有一個帶參的構造函數，接受一個list_node < T >*的參數，來初始化成員變量
list_iterator():node(nullptr)
{}
list_iterator(list_node<T>* l1):node(l1)
{}
自增運算符重載函數
那么該運算符重載函數的作用就是能夠讓迭代器指向下一個邏輯上相鄰的節點，那么就需要我們將該迭代器指向的節點的next指針賦值給迭代器也就是作為返回值，但是注意的是，這里我們的返回值類型是一個迭代器，而next指針的類型是一個list_node< T>*,所以就需要我們對該返回值進行數據類型的轉化，而我們的迭代器有一個支持單參數的list_node< T> *的構造函數，那么就可以直接利用隱式類型轉化即可
self_iterator& operator++()
{node = node->next;return *this;
}
//這里將迭代器類型typedef為了self_iterator
那么剛才所說的前置自增，那么對于后置自增運算符來說，那么則需要我們首先在參數列表中顯示的添加一個int來區分前置自增，由于后置自增是先返回在自增，那么這里我們就得定義一個變量prevnode來保存成員變量node的值，然后剩余步驟和前置一樣，最后返回值就是prevnode返回
self_iterator& operator++(int)
{self_iterator prev = list_iterator(node);node = node->next;return prev;
}
自減運算符重載函數
那么自減運算符重載函數和自增的實現原理幾乎一樣，不同就在于這里是返回前一個節點
self_iterator& operator--()
{node = node->prev;return *this;
}
self_iterator& operator--(int)
{list_node<T>* prev = node->prev;node = node->prev;return prev;
}
*運算符重載函數
那么我們知道由于迭代器指向的是一個結構體，而我們*解引用運算符的目的是為了能夠得到返回其節點的數據域的內容，而迭代器內部的成員變量就是指向該結構體的指針，那么我們直接解引用該指針返回val里面的內容即可
ref operator*() const
{return node->val;
}
那么這里的ref返回值是什么，那么下文會有解釋，你在這就先理解為T&
->運算符重載函數
那么我們這里還重載了->運算符，那么這個運算符我們很熟悉，那么是給結構體指針用來訪問結構體內部的成員變量，而我們發現*運算符重載函數的作用就是返回節點數據域里面的內容，但是要注意的就是我們節點的數據域val的數據類型不一定是內置類型，也可以是自定義類型，那么對于自定義類型來說，那么我們訪問自定義類型的數據肯定是訪問其中的某個成員變量，所以這里就需要重載->運算符來得到該結構體val的某個成員變量
ptr operator->() const //這里的返回值ptr先理解為T*，至于這個ptr是什么，那么我下文會有解釋
{return &(node->val);
}
re_node函數
那么之所以定義這個函數的原因是因為到時候，我們list內部的成員函數會涉及到修改節點的鏈接關系，那么其中傳遞的都是迭代器，那么我們知道節點的next以及prev指針的數據類型都是list_node< T> * ，那么修改指針的時候，我們就不能直接將迭代器的值賦給next或者prev指針，因為迭代器是無法轉換list_node< T> *的，所以這里我們定義了一個re_node函數，那么它的返回值就是list_node< T > *,也就是成員變量，就是為了解決剛才數據類型不匹配的問題
list_node<T>* re_node() const
{return node;
}
補充
那么這里我們知道有的list對象可能會被const給修飾，那么有的list對象則不被const修飾，那么對于被const修飾的list來說，那么它只能被const的迭代器來訪問，而非const修飾的list的對象，則既可以被const的迭代器所訪問也可以被非const的迭代器所訪問，而const的迭代器的區別就是這里對于一些運算符重載函數的返回值，比如*運算符以及自增自減等返回值，都要返回被const所修飾
那么有的小伙伴實現const的迭代器的思路就是我直接在為const迭代器定義一個單獨的模版類即可，那么這種方式可以，但是缺點就是這個const迭代器的模版類和非const迭代器的模板類，他們的代碼邏輯是相同的，唯一的區別就是一些數據類型比如返回值不同，那么這就存在明顯的代碼冗余并且不便于維護的問題，所以第二種方式就是只用一個模板類來表示出const和非const迭代器，因為我們知道模版的應用場景就是根據不同的數據類型來實例化出不同的模版類，所以這里我們可以為list_iterator模版類定義三個模版參數，分別是數據域的數據類型T以及引用ref和指針ptr，而const和非const的迭代器的ref和ptr肯定是不同的，分別是T&和const T&以及T * 和 const T *，那么就可以實例化成不同的模版類
template<typename T, typename ref, typename ptr>
class list_iterator
{........
}；template<typename T>class list{public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;};
注意的實typedef也會受到訪問限定符的修飾，那么為了讓外部能夠訪問到迭代器，這個typedef一定不能是被private修飾，否則我們無法在類外部定義迭代器
begin函數
那么begin函數就是返回哨兵節點之后下一個節點，那么begin函數返回值是一個迭代器，那么由于list對象可能被const修飾，所以這里的begin有兩個重載版本分別是返回const迭代器以及非const迭代器
iterator begin()
{return head->next;
}
const_iterator begin() const
{return head->next;
}
end函數
那么end函數則是返回哨兵節點，同樣也有兩個版本，分別返回const迭代器以及非const迭代器
iterator end()
{return head;
}
const_iterator end() const
{return head;
}
insert函數
那么這里insert函數就是插入函數，那么list類重載了幾個版本的insert函數，那么最為常見的一個版本就是接收一個迭代器和一個val值，也就是插入一個節點，那么insert函數具體的實現原理就是首先得定義一個變量prevnode來保存迭代器指向的節點的前驅節點，然后我們再new一個新的節點，然后修改節點之間的鏈接關系，也就是讓前驅節點的next指針指向新插入的節點，然后讓新插入的節點的prev指針指向前驅節點，而新插入的節點與迭代器指向的節點的鏈接關系的修改也是同理
void insert(iterator pos, const T& data)
{node newnode = new list_node<T>(data);node prevnode = pos.re_node()->prev;prevnode->next = newnode;newnode->prev = prevnode;newnode->next = pos.re_node();pos.re_node()->prev = newnode;
}
第二個重載版本則是則是插入一個迭代器區間，那么這里的insert的函數實現和上面的區別就是，這里我們要用一個循環，來遍歷這個迭代器的區間，在遍歷之前我們還是會定義一個prevnode來保存新插入的節點的前驅節點，然后每一次循環，我們會創建一個與對應迭代器區間的節點的數據相同的新節點，然后就建立prevnode與新插入的節點之間的鏈接關系，并且更新prevnode，最后退出循環的時候，prevnode則是指向最后一個新建的節點，那么我們再將其與pos位置指向的迭代器相連接即可
void insert(iterator pos, iterator first, iterator last)
{node prevnode = pos.re_node()->prev;iterator it = first;while (it != last){node newnode = new list_node<T>(it.re_node()->val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;++it;}prevnode->next = pos.re_node();pos.re_node()->prev = prevnode;return;
}
那么有的小伙伴可能注意到，我在創建節點時候，我需要拷貝迭代器區間中對應節點的值，也就是獲取其中的val然后傳遞給構造函數，但是這里我是先調用了迭代器的re_node函數然后再解引用獲取val，為什么這里我不直接解引用得到val，也就是it->val而是寫成 it.re_node()->val呢？
那么這里我就要解釋一下，假設我們有一個迭代器it，由于我們的list_iterator類中定義了->運算符重載函數，而我們知道該運算符重載函數是返回一個指向節點的成員變量val的指針，而如果val是一個自定義類型的話，那么我們要訪問val中的成員變量比如member1意味著我們還需要再依次解引用返回的該指向val的指針，所以我們在寫對應的代碼時候，理論上應該是這種形式：it->->member1，但是編譯器對此進行了優化，也就是你只需要寫一次->即可，那么編譯器它會自動的先調用->運算符重載函數，然后再在后面再進行一次解引用：
it->member1;//你的視角 (it.operator->())->member1;//編譯器的視角那么有了前面的鋪墊我們就能知道為什么it->val不行，這里之所以有的小伙伴會這么寫，可能還是習慣了把迭代器當做了一個指向結構體的指針，他認為val就是node結構體中的一個成員變量，所以這么寫，但是由于->運算符重載函數的存在，那么這里會被解析為：
(it.operator->())->val也就是返回一個指向的val的指針，再對該指針解引用，那么這里如果val是一個內置類型，那么你按照結構體指針那樣的解引用，那么編譯器會報錯，如果val是自定義類型，那么編譯器就會嘗試尋找其成員變量名為val然后返回
而之前我定義的re_node函數就能派上用場，那么它是返回一個指向node的指針，而node是結構體，那么我再解引用就可以獲取其成員變量val
it.re_node()->val
erase函數
那么erase函數就是刪除該鏈表的節點，那么它有不同的重載版本，首先就是只刪除其中一個節點，那么它會接受一個迭代器，那么實現原理也很簡單，就是保存刪除節點的前一個位置的節點，然后修改鏈接關系，讓前一個節點指向刪除節點的之后的一個節點，最后在delete掉迭代器指向的節點
iterator erase(iterator pos)
{if (pos != end()) {node prevnode = pos.re_node()->prev;node nextnode = pos.re_node()->next;node to_delete = pos.re_node();prevnode->next = nextnode;nextnode->prev = prevnode;delete to_delete;return iterator(nextnode);}else{return begin();}
}
那么注意的就是對于list的insert函數，那么其不會像vector那樣出現迭代器失效的問題，因為不需要擴容，節點都是按需申請按需釋放，但是對于erase來說，那么這里就涉及到迭代器失效的問題，因為我們的傳進去的參數也就是迭代器是傳值拷貝，那么形參的改變不影響實參，所以這里我們發現erase會有一個返回值，返回被刪除的下一個節點，所以不能在使用傳進去的迭代器繼續訪問
接著就是刪除一個迭代器區間，那么會接受兩個迭代器first和last，注意的就是刪除的區間是左閉右開的，也就是[first,last)，那么思路就是可以復用之前刪除一個節點的erase函數即可
iterator erase(iterator first, iterator last)
{while (first != last){first = erase(first);}return last;
}
push_back函數
那么push_back就是尾插函數，那么尾插函數就是在尾節點之后添加一個新節點，那么這里我們就可以直接利用函數的復用，調用實現好的insert函數來實現
void push_back(const T& val)
{insert(end(), val);
}
pop_front函數
那么頭刪函數就是可以復用之前實現好的erase函數來實現
void pop_front()
{erase(begin());
}
size函數
那么size函數就是返回該鏈表中節點的數量其中不包括哨兵節點，那么這里我們首先定義一個變量size來記錄，然后遍歷該鏈表利用迭代器即可
size_t size() const
{size_t count = 0;const_iterator it = begin();while (it != end()){count++;it++;}return count;
}
empty函數
那么empty函數就是確認該鏈表為空鏈表，那么鏈表為空意味著該鏈表只有哨兵節點而不是一個節點都沒有，那么判斷的條件就是哨兵節點的next或者prev指針是否指向自己
bool empty(){if (head->next == head){return true;}return false;}
clear函數
那么clear函數就是清空所有非哨兵節點，那么我們還是遍歷該鏈表，復用我們的erase函數
void clear()
{erase(begin(), end());
}
賦值運算符重載函數
那么賦值運算符重載函數則是復制拷貝新的節點，那么這里我們首先得釋放我們原本的節點，那么這一步我們可以復用clear函數，然后只剩哨兵節點，然后我們再遍歷目標鏈表
list<T>& operator=(const list<T>& l1)
{clear();const_iterator it = l1.begin();node prevnode = head;while (it != l1.end()){node newnode = new list_node<T>(it.re_node()->val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;it++;}prevnode->next = head;head->prev = prevnode;return *this;
}
那么有的小伙伴可能會有一個疑問，因為它有vector的實現經驗，之前實現vector的賦值運算符重載函數，那么涉及到淺拷貝的問題，也就是說假設這里我們的目標鏈表節點的val是一個自定義類型比如是string，那么這里淺拷貝就會導致析構兩次等問題，那么這樣的擔心是沒錯的，但是這里每一個自定義類型肯定會有實現了深拷貝的拷貝構造函數，那么這里我new的時候，實參傳遞給形參就會調用拷貝構造，所以不用擔心淺拷貝問題
析構函數
那么析構函數則是釋放我們該鏈表申請的所有節點，其中包括哨兵節點，這一步我們可以復用clear函數，最后再將成員變量也就是head置為nullptr即可
~list()
{clear();delete head;head = nullptr;
}
源碼
list.h
#pragma once
namespace wz
{template<typename T>struct list_node{struct list_node<T>* next;struct list_node<T>* prev;T val;list_node():next(nullptr), prev(nullptr), val(T()){}list_node(const T& data):next(nullptr), prev(nullptr), val(data){}};template<typename T, typename ref, typename ptr>class list_iterator{public:list_node<T>* node;typedef list_iterator<T, ref, ptr> self_iterator;list_iterator():node(nullptr){}list_iterator(list_node<T>* l1):node(l1){}self_iterator& operator++(){node = node->next;return *this;}self_iterator& operator++(int){self_iterator prev = list_iterator(node);node = node->next;return prev;}list_node<T>* re_node() const{return node;}self_iterator& operator--(){node = node->prev;return *this;}self_iterator& operator--(int){list_node<T>* prev = node->prev;node = node->prev;return prev;}bool operator!=(const self_iterator& it) const{return node != it.node;}bool operator==(const self_iterator& it) const{return node == it.node;}ref operator*() const{return node->val;}ptr operator->() const{return &(node->val);}};template<typename T>class list{private:typedef list_node<T>* node;node head;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;list(){head = new list_node<T>;head->next = head;head->prev = head;}list(size_t n, const T& val){head = new list_node<T>;node prevnode = head;while (n--){node newnode = new list_node<T>(val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;}prevnode->next = head;head->prev = prevnode;}list(iterator first, iterator last){head = new list_node<T>;node prevnode = head;iterator it = first;while (it != last){node newnode = new list_node<T>(it.re_node()->val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;it++;}prevnode->next = head;head->prev = prevnode;}list(const list<T>& l1){head = new list_node<T>;head->next = head;head->prev = head;const_iterator it = l1.begin();while (it != l1.end()){push_back(*it);++it;}}~list(){clear();delete head;head = nullptr;}iterator begin(){return head->next;}iterator end(){return head;}const_iterator begin() const{return head->next;}const_iterator end() const{return head;}size_t size() const{size_t count = 0;const_iterator it = begin();while (it != end()){count++;it++;}return count;}list<T>& operator=(const list<T>& l1){clear();const_iterator it = l1.begin();node prevnode = head;while (it != l1.end()){node newnode = new list_node<T>(it.re_node()->val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;it++;}prevnode->next = head;head->prev = prevnode;return *this;}void clear(){erase(begin(), end());}bool empty(){if (head->next == head){return true;}return false;}void push_back(const T& val){insert(end(), val);}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}void pop_back(){iterator end = iterator(head->prev);erase(end);}void insert(iterator pos, const T& data){node newnode = new list_node<T>(data);node prevnode = pos.re_node()->prev;prevnode->next = newnode;newnode->prev = prevnode;newnode->next = pos.re_node();pos.re_node()->prev = newnode;}void insert(iterator pos, iterator first, iterator last){node prevnode = pos.re_node()->prev;iterator it = first;while (it != last){node newnode = new list_node<T>(it.re_node()->val);prevnode->next = newnode;newnode->prev = prevnode;prevnode = newnode;++it;}prevnode->next = pos.re_node();pos.re_node()->prev = prevnode;return;}iterator erase(iterator pos){if (pos != end()) {node prevnode = pos.re_node()->prev;node nextnode = pos.re_node()->next;node to_delete = pos.re_node();prevnode->next = nextnode;nextnode->prev = prevnode;delete to_delete;return iterator(nextnode);}else{return begin();}}iterator erase(iterator first, iterator last){while (first != last){first = erase(first);}return last;}};
}
list.cpp
#include "list.h"
#include <iostream>
#include <cassert>
using std::cout;
using std::endl;void test_basic_operations() {wz::list<int> lst;// 測試空鏈表assert(lst.empty());assert(lst.size() == 0);assert(lst.begin() == lst.end());// 測試尾部插入lst.push_back(1);lst.push_back(2);assert(*lst.begin() == 1);assert(*(++lst.begin()) == 2);assert(lst.size() == 2);// 測試頭部插入lst.push_front(0);assert(*lst.begin() == 0);assert(lst.size() == 3);// 測試刪除lst.pop_front();assert(*lst.begin() == 1);lst.pop_back();assert((++lst.begin()) == lst.end());
}void test_iterator_and_insert() {wz::list<std::string> words;words.push_back("hello");words.push_back("world");// 測試迭代器遍歷auto it = words.begin();assert(*it == "hello");++it;assert(*it == "world");++it;assert(it == words.end());// 測試范圍插入wz::list<std::string> new_words;new_words.insert(new_words.end(), words.begin(), words.end());assert(new_words.size() == 2);assert(*new_words.begin() == "hello");
}void test_copy_and_splice() {wz::list<int> source;source.push_back(10);source.push_back(20);// 測試拷貝構造wz::list<int> copy1(source);assert(copy1.size() == 2);assert(*copy1.begin() == 10);// 測試拷貝賦值wz::list<int> copy2;copy2 = source;assert(copy2.size() == 2);// 測試自插入copy2.insert(copy2.begin(), copy2.begin(), copy2.end());assert(copy2.size() == 4);
}void test_edge_cases() {wz::list<int> lst;// 測試在空鏈表插入lst.insert(lst.end(), 42);assert(*lst.begin() == 42);// 測試刪除唯一元素lst.pop_back();assert(lst.empty());// 測試自引用lst.push_back(1);lst.insert(lst.begin(), *lst.begin());assert(lst.size() == 2);assert(*lst.begin() == 1);
}int main() {// 基礎功能測試test_basic_operations();// 迭代器和插入測試test_iterator_and_insert();// 拷貝和拼接測試test_copy_and_splice();// 邊界條件測試test_edge_cases();// 可視化測試wz::list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.pop_front();wz::list<int> l2 (l1.begin(),l1.end());l1.insert(l1.begin(), l2.begin(), l2.end());cout << "Final list contents:" << endl;wz::list<int>::iterator it = l2.begin();while (it != l2.end()) {cout << *it << endl;++it;}cout << "All tests passed!" << endl;return 0;
}
運行截圖：
結語
那么這就是本篇文章的所有內容，那么帶你從兩個維度全面解析list，那么也建議讀者看完本文后，讀者下來也可以自己模擬實現list，加深你對list的理解并且還能鞏固類和對象等知識，那么我會持續更新，希望大家能夠多多關注，那么我的下一篇文章，會講解棧和隊列，那么如果本文對你有幫組的話，還請多多支持，你的支持就是我創作的最大的動力！
 在PyInstaller打包前后的區別)
