本項(xiàng)目GitHub： HuangCheng72/HCSTL: 我的STL實(shí)現(xiàn) (github.com): https://github.com/HuangCheng72/HCSTL

進(jìn)入正文。

for_each算法在vector中實(shí)現(xiàn)了，也達(dá)到了我們滿意的效果。

我們想到一個(gè)問題，for_each能不能在別的容器比如 list 上實(shí)現(xiàn)呢？這肯定是可以的，遍歷一個(gè)鏈表是很簡單的，我們可以輕而易舉寫出如下的代碼：

list.h ：

但是我們推廣一下，未來還有很多種容器要開發(fā)，甚至用戶自己也會(huì)實(shí)現(xiàn)容器，我們難道對每個(gè)容器都單獨(dú)實(shí)現(xiàn)一個(gè) for_each 嗎？這工作量未免也太大了。

所以，需要將 for_each 作為一個(gè)單獨(dú)的部分（算法），分離出來，它應(yīng)該是一個(gè)適用于符合一定標(biāo)準(zhǔn)的容器的組件，只要容器符合這個(gè)標(biāo)準(zhǔn)，就可以使用 for_each 這個(gè)算法。

那么我們觀察 for_each 在 vector 和 list 中實(shí)現(xiàn)的差別：

我們發(fā)現(xiàn)，輸入?yún)?shù)的類型不同，導(dǎo)致 temp 的類型不同（操作的指針類型不同）；

對于第一個(gè)問題，我們考慮到模板，可以用模板實(shí)現(xiàn)統(tǒng)一，可以實(shí)現(xiàn)像這樣的代碼。

但是我們很快遇到了問題，Pointer移動(dòng)到下一位（遞進(jìn)）的方法并不一樣，Pointer取出要操作的數(shù)據(jù)的方法也不一樣。

C++的類與對象實(shí)踐中，有時(shí)存在這么一種場景。已知一個(gè)函數(shù)，它有時(shí)候傳入?yún)?shù)的是A類的對象，有時(shí)候傳入?yún)?shù)的又是B類的對象，而A類和B類之間并沒有相互繼承的關(guān)系，函數(shù)僅用到它們都有的一個(gè)名稱為Function的函數(shù)（這里只是舉個(gè)例子，不代表真實(shí)情況）。如：

碰到這種問題，我們可以用的解決方法：

1. 函數(shù)重載，即分別實(shí)現(xiàn)只接受A類對象的函數(shù)和只接受B類對象的函數(shù)，當(dāng)接受到對應(yīng)類型的對象的時(shí)候就可以調(diào)用對應(yīng)的函數(shù)。

2. 建立一個(gè)空類或者抽象類，讓A類和B類都繼承自這個(gè)空類或者抽象類，以這個(gè)抽象類作為函數(shù)參數(shù)的類型，利用父類引用可以指向子類對象的特點(diǎn)，完成統(tǒng)一的傳參。

我們當(dāng)然可以采用方法1，但是我們也要考慮到后來，新增一種容器就要重載一次或者多次，就達(dá)不到我們減少工作量增加代碼復(fù)用性的目的，因此，我們選用方法2，即新建一個(gè)父類，在 vector 和 list 中分別實(shí)現(xiàn)其子類，封裝其中 vector 的指針和 list 的結(jié)點(diǎn)，子類中具有同一種行為，在這里是統(tǒng)一的移動(dòng)到下一位（遞進(jìn)）和取值操作函數(shù)。

實(shí)際使用中，我們封裝為類或者結(jié)構(gòu)體都行，C++的結(jié)構(gòu)體可以視為一個(gè)全部成員變量和成員函數(shù)都默認(rèn)為public的類，而且結(jié)構(gòu)體名也可以作為模板參數(shù)傳參。

我們要封裝的這個(gè)父類，有個(gè)名字，叫做 迭代器（Iterator） ，迭代器應(yīng)當(dāng)遵照統(tǒng)一的標(biāo)準(zhǔn)，執(zhí)行統(tǒng)一的行為，具體迭代器的實(shí)現(xiàn)則是視容器的不同而不同。迭代器的主要工作是 模仿指針，為用戶或者算法操作容器數(shù)據(jù)提供一個(gè)統(tǒng)一的接口，讓用戶或者算法不需要面對各種千奇百怪的結(jié)構(gòu)或者操作方法，只需要操作迭代器，就可以讀寫容器。因此，迭代器的最高境界就是用起來跟指針一樣，C++的原生指針就是最全能的迭代器。

迭代器，根據(jù)其能力大小，可以分為五種。每個(gè)容器均可以通過其中一或多種迭代器訪問其中數(shù)據(jù)。

1. 輸入迭代器（單向移動(dòng)，只能讀一次）（例如istream_iterator）

2. 輸出迭代器（單向移動(dòng)，只能寫一次）（例如ostream_iterator）

3. 正向迭代器（單向移動(dòng)，讀寫多次）（例如單鏈表的迭代器）（在輸入輸出兩個(gè)迭代器基礎(chǔ)上擴(kuò)展）

4. 雙向迭代器（雙向移動(dòng)，讀寫多次）（例如雙向鏈表的迭代器）（在正向迭代器基礎(chǔ)上擴(kuò)展）

5. 隨機(jī)訪問迭代器（在容器內(nèi)可以隨便移動(dòng)到哪里，讀寫多次）（最經(jīng)典就是指針）（在雙向迭代器基礎(chǔ)上擴(kuò)展）

我們希望迭代器最好能像指針一樣，可以通過*來讀寫數(shù)據(jù)，可以++，--，或者p += 3 ，p -= 4 之類的操作來移動(dòng)，還可以通過兩個(gè)迭代器相減計(jì)算兩個(gè)迭代器之間的距離（最好同樣用指針相減的結(jié)果ptrdiff_t類型表示，當(dāng)然你非得用其他也行）等等。

這就需要運(yùn)用C++的重載機(jī)制，在迭代器中重載這些運(yùn)算符。

同時(shí)，以用戶或者算法的視角來看，我們直接面對的只有迭代器，我們并不知道這個(gè)容器是什么，里面保存的數(shù)據(jù)是什么類型的，容器的具體實(shí)現(xiàn)原理是什么，我們能做的事情就是通過迭代器，按照我們定下的步驟去操作數(shù)據(jù)。

有些情況下，用戶或者算法需要特殊的操作，比如要讓迭代器向反方向移動(dòng)，如果提供的迭代器是個(gè)輸入輸出或者正向迭代器，這種情況顯然是沒辦法繼續(xù)進(jìn)行的。所以，用戶和算法必須要知道這個(gè)迭代器的能力范圍，因此迭代器需要保存它的種類標(biāo)簽信息（iterator_category，這是為了確定它的能力范圍）。

用戶或者算法需要知道迭代器所指向的數(shù)據(jù)的類型（value_type），C++是強(qiáng)類型語言，需要給出確切的類型才能定義變量（不考慮auto），用于接收迭代器所指向的數(shù)據(jù)。

用戶還需要確定迭代器之間的距離表達(dá)結(jié)果的類型，這樣子用戶才能接收到兩個(gè)迭代器之間的距離信息，不過一般都默認(rèn)指定為ptrdiff_t，與指針相減的結(jié)果相同。

因此，我們所設(shè)計(jì)的迭代器的原型如下：

我們得到了迭代器，需要知道迭代器里面包含的這些信息，該怎么做？

這時(shí)候我們就想起來了類型萃?。╰ype_traits）了，類型萃取是提取類型的信息，這里我們也是在提取迭代器的信息。

只要是符合上面標(biāo)準(zhǔn)的迭代器，都應(yīng)該可以被萃取出這些信息。

其實(shí)可以讓算法干這件事，但是我們希望算法只干本職工作就是計(jì)算邏輯，只要拿到迭代器就能讀寫，不要管迭代器的內(nèi)部狀態(tài)（相當(dāng)于一個(gè)ATM，我只管存錢取錢，不關(guān)心你ATM內(nèi)部運(yùn)作或者你怎么判斷假幣）。

因此，我們模仿類型萃取機(jī)制，實(shí)現(xiàn)了一個(gè) 迭代器萃?。╥terator_traits） 機(jī)制。

其實(shí)就是很簡單的起別名，但是確實(shí)實(shí)現(xiàn)了我們的功能，只要是按照迭代器規(guī)范設(shè)計(jì)的迭代器，必定可以被我們實(shí)現(xiàn)的迭代器萃取機(jī)制萃取出我們需要的信息，而且我們的結(jié)構(gòu)體都是空結(jié)構(gòu)體，并不占用內(nèi)存空間，從頭到尾我們都是利用了模板特化來實(shí)現(xiàn)的。

類型萃取的結(jié)果該怎么使用呢？以下是一種使用方法。

另外，C++11推出了decltype關(guān)鍵字，可以通過該關(guān)鍵字來直接獲取類型信息，為了代碼可讀性，可以增加一個(gè)函數(shù)，用于獲取特定的迭代器萃取結(jié)果，例如：

其用法為：

因此，我們實(shí)現(xiàn)的 iterator.h 頭文件完整如下：

歡迎訪問本項(xiàng)目的GitHub倉庫，如果對您有幫助，麻煩給項(xiàng)目一個(gè)star，謝謝！

HuangCheng72/HCSTL: 我的STL實(shí)現(xiàn) (github.com): https://github.com/HuangCheng72/HCSTL