我們之前講解了list，今天我們來看一下list的底層：

list底層是一個雙向帶頭循環的鏈表，之前我們學習數據結構的時候，我們就學過。

迭代器的封裝：

我們看這個圖片，我們的鏈表的指針可以達到鏈表的迭代器能力嗎？

達不到的，只有在數組里面，連續地數據的時候，指針才可以是看作迭代器。

迭代的兩個核心的能力就是：++和*。

在鏈表里面，數據是不連續的，對于迭代器的++，是實現不了的，得不到下一個數據的位置。*解引用的話，得到的也是這個節點，得不到里面的數據，這就和數組里面的迭代器是不一樣的。

在數組里面，數據是連續的，我們的迭代器++就可以到下一數據的個位置。*解引用就可以直接得到這個數據的。

但是：

我們在list里面我們是可以使用迭代器完成++和*的操作的，那么底層是怎么實現我們的迭代器的呢？

我們看一下我們的庫里面是怎么干的。

我們的底層使用一個自定義的類來把我們的指針封裝起來；

我們使用封裝來實現我們的迭代器的功能：

對于我們的迭代器的++和解引用*，我們可以直接使用函數重載來實現，我們直接實現在類里面。

這個類就是我們的迭代器，我們給類的名字就叫做list_iterator；

insert的底層：

我們看這個insert的底層：

我們看insert，我們的插入是把數據插入到，迭代器position位置的前面。

我們看這個代碼，我們是申請到介蒂安以后，我們的tmp的next指向position.node;

在這里可能會有疑惑，為什么是.，這個不應該是類，結構體調用里面的成員才使用的嗎？

是的：

我們在封裝我們的指針的時候，我們把我們的node結點也給封裝進去了，因為我們的后面要實現函數的重載，我們要調用node。

我們說我們的string和vector的迭代器使用的就是我們的原生指針，list使用的迭代器就是把我們的指針進行封裝，在內部實現函數重載，但是string和vector也不一定是要使用原生指針，也可以封裝他們的指針來進行。

list的底層的實現：

迭代器的實現：

我們把我們的結點的指針封裝到我們的類里面，這個類就是我們的list的迭代器。

然后我們在這個類里面，我們實現迭代器的++，*解引用等一些列的操作。

迭代器失效：

我們之前講解vector的時候，我們的insert函數和erase函數都發生了迭代器失效的問題，我們的插入函數失效的原因是我們的數組進行了擴容，但是我們的pos位置沒有進行更新，發生了迭代器失效，我們的erase函數失效的原因是我們的vs會對他進行強制的判斷，刪除數據以后這個迭代器就失效了。

這個是我們的list底層實現的insert函數，我們的list沒有擴容的問題，這里的insert是沒有迭代器失效的問題的。

這個是我們的list的刪除函數erase，這個函數和我們的vector一樣，都是會發生迭代器失效的問題的，我們的erase函數，在把pos位置的數據刪除以后，迭代器pos指向的結點就被銷毀了，這時候pos就失效了，所以我們的這個函數還是要返回下一個數據的迭代器來及時的更新我們的迭代器，來避免迭代器的失效。

這樣我們就可以向vector那樣，刪除數據以后，更新我們的迭代器；

（幾乎所有的容器的erase都會失效，至于insert會不會失效，這個就要看情況）；

const修飾迭代器：

我們看這個代碼，我們在實現拷貝構造的時候，我們的參數傳的是const修飾的參數類型，這時候我們進到函數里面的話，我們使用范圍for就會報錯，因為范圍for的底層是我們的迭代器，我們的迭代器是普通的類型。

但是我們的鏈表被const修飾，我們使用迭代器對他進行遍歷的話，我們就需要const類型的迭代器來。

我們看下面的圖片：

我們的這個圖片我們看我們的上面的兩種被const修飾的指針，我們的const放在*前面的時候，我們的指針指向的數據不能被修改，但是我們的指針的指向可以修改。

當我們的const在*的右邊的時候，這時候表示我們的指針指向的數據可以被修改，但是我們的指針的指向不能被修改。

我們的const迭代器其實就是和我們的上面的第一種是一樣的，我們的迭代器指向的數據不能被修改，但是我們的迭代器的指向可以被修改；

所以，對于這種情況，我們就創建兩種迭代器來進行應對：一種普通的迭代器，再來一種const修飾的迭代器；

我們把const迭代器封裝成一個新的類，我們的const修飾的迭代器和普通的迭代器是兩個不同的類；

這個是我們的const修飾的迭代器；

這個是我們的普通的迭代器；

這兩個類的本質的卻別其實就是解引用*的實現，const修飾的迭代器我們的返回值加上const，不能讓他修改數據；

迭代器的合并：

我們實現我們的迭代器的封裝，我們封裝了兩個類，分別是我們的普通的迭代器iterator的封裝和const修飾的const_iterator的封裝，但是其實這兩個類的話，我們看了我們上面的const修飾的迭代器，其實主要的區別就是解引用函數的返回值是否是被const修飾的。

我們就可以再加一個模板參數，把我們的解引用函數的返回值換成我們的模板參數，然后我們調用我們的迭代器的時候，我們需要什么類型的迭代器，我們直接傳參就可以了。

補充：

我們看這個圖片，我們看我們對我們的vector進行初始化的狀態。

v1.push_back({ 1,1 });?等尾插操作涉及隱式類型轉換。

AA?結構體定義了帶有默認參數的構造函數?AA(int a1 = 1, int a2 = 1)?。當執行?v1.push_back({ 1,1 });?時，花括號初始化列表?{1, 1}?沒有直接對應的?AA?類型對象。此時，編譯器會利用?AA?的這個構造函數，將?{1, 1}?隱式轉換為?AA?類型臨時對象，再調用?push_back?插入到?vector<AA>?容器?v1?中 。這符合隱式類型轉換的特征，即編譯器自動利用構造函數進行類型轉換。

我們來看這個函數，我們上面使用vector容器，我們看vector里面使用了這個容器：

我們看這個，我們使用迭代器進行遍歷然后使用箭頭->解引用得到數據打印；

這個原理是什么呢？因為我們的vector的迭代器就是他的原生指針，我們的vector是一個順序表，里面的每個元素的都是AA類型的對象，我們的迭代器指向某一個位置，這個位置的數據就是一個AA對象，那么這個迭代器就是指向這個位置的指針，那么這個指針就相當于是一個結構體struct指針，我們使用指針->得到結構體里面的數據a1和a2。

我們再看，當我們的容器換成list的時候，我們還是進行遍歷打印數據，這時候我們直接->是不行的，我們的list的迭代器不是原生的指針，我們要自己封裝實現；

我們看我們實現的；這個代碼，我們返回我們的結點的數據的指針，我們的返回值是模板類型的，因為他可能是const修飾的指針，也可能不是const修飾的。

這是我們的迭代器的最后的模板；

我們繼續回到上面看：

我們的->的返回值是結點里面的數據的指針，但是這個數據是AA類型的對象，我們還要再來一個箭頭才是最終的_a1和_a2數據；? ，，但是這里是特殊的處理，省略了，方便可讀。

這個是我們實現的完整的版本：

list的底層實現/list的底層實現/list的底層實現.h · 拾億天歌/拾億天歌 - 碼云 - 開源中國