大家好，我是小賀，
點贊再看，養成習慣
文章每周持續更新，可以微信搜索「herongwei」第一時間閱讀和催更，本文 GitHub : https://github.com/rongweihe/MoreThanCPlusPlus 已經收錄，有一線大廠面試點思維導圖，也整理了很多我的檔案，歡迎 star 和完善，一起加油，變得更好！
前言
上一篇，我們剖析了 STL 空間配置器，這一篇文章，我們來學習下 STL 迭代器以及背后的 traits 編程技法，
在 STL 編程中，容器和演算法是獨立設計的，容器里面存的是資料，而演算法則是提供了對資料的操作，在演算法操作資料的程序中，要用到迭代器，迭代器可以看做是容器和演算法中間的橋梁，
1、迭代器設計模式
為何說迭代器的時候，還談到了設計模式？這個迭代器和設計模式又有什么關系呢？
其實，在《設計模式：可復用面向物件軟體的基礎》（GOF）這本經典書中，談到了 23 種設計模式，其中就有 iterator 迭代模式，且篇幅頗大，
碰巧，筆者在研究 STL 原始碼的時候，同樣的發現有 iterator 迭代器，而且還占據了一章的篇幅，
在設計模式中，關于 iterator 的描述如下：一種能夠順序訪問容器中每個元素的方法，使用該方法不能暴露容器內部的表達方式，而型別萃取技術就是為了要解決和 iterator 有關的問題的，
有了上面這個基礎，我們就知道了迭代器本身也是一種設計模式，其設計思想值得我們仔細體會，
那么 C++ STL 實作 iterator 和 GOF 介紹的迭代器實作方法什么區別呢？ 那首先我們需要了解 C++ 中的兩個編程范式的概念，OOP（面向物件編程）和 GP（泛型編程），
在 C++ 語言里面，我們可用以下方式來簡單區分一下 OOP 和 GP ：
OOP：將 methods 和 datas 關聯到一起 （通俗點就是方法和成員變數放到一個類中實作），通過繼承的方式，利用虛函式表（virtual）來實作運行時型別的判定，也叫"動態多型"，由于運行程序中需根據型別去檢索虛函式表，因此效率相對較低，
GP：泛型編程，也被稱為"靜態多型"，多種資料型別在同一種演算法或者結構上皆可操作，其效率與針對某特定資料型別而設計的演算法或者結構相同， 具體資料型別在編譯期確定，編譯器承擔更多，代碼執行效率高，在 STL 中利用 GP 將 methods 和 datas 實作了分而治之，
而 C++ STL 庫的整個實作采用的就是 GP（Generic Programming），而不是 OOP（Object Oriented Programming），而 GOF 設計模式采用的就是繼承關系實作的，因此，相對來講，C++ STL 的實作效率會相對較高，而且也更有利于維護，
在 STL 編程結構里面，迭代器其實也是一種模板 class ，迭代器在 STL 中得到了廣泛的應用，通過迭代器，容器和演算法可以有機的系結在一起，只要對演算法給予不同的迭代器，比如 vector::iterator、list::iterator，std::find() 就能對不同的容器進行查找，而無需針對某個容器來設計多個版本，
這樣看來，迭代器似乎依附在容器之下，那么，有沒有獨立而適用于所有容器的泛化的迭代器呢？這個問題先留著，在后面我們會看到，在 STL 編程結構里面，它是如何把迭代器運用的爐火純青，
2、智能指標
STL 是泛型編程思想的產物，是以泛型編程為指導而產生的，具體來說，STL 中的迭代器將范型演算法 (find, count, find_if) 等應用于某個容器中，給演算法提供一個訪問容器元素的工具，iterator 就扮演著這個重要的角色，
稍微看過 STL 迭代器原始碼的，就明白迭代器其實也是一種智能指標，因此，它也就擁有了一般指標的所有特點—— 能夠對其進行 * 和 -> 操作，
template<typename T>
class ListIterator {//mylist迭代器
public:
ListIterator(T *p = 0) : m_ptr(p){} //建構式
T& operator*() const { return *m_ptr;} //取值，即dereference
T* operator->() const { return m_ptr;} //成員訪問，即member access
//...
};
但是在遍歷容器的時候，不可避免的要對遍歷的容器內部有所了解，所以，干脆把迭代器的開發作業交給容器的設計者，如此以來，所有實作細節反而得以封裝起來不被使用者看到，這也正是為什么每一種 STL 容器都提供有專屬迭代器的緣故，
比如筆者自己實作的 list 迭代器在這里使用的好處主要有：
- (1) 不用擔心記憶體泄漏（類似智能指標，解構式釋放記憶體）；
- (2) 對于
list，取下一個元素不是通過自增而是通過next指標來取，使用智能指標可以對自增進行多載，從而提供統一介面，
3、template 引數推導
引數推導能幫我們解決什么問題呢？
在演算法中，你可能會定義一個簡單的中間變數或者設定演算法的回傳變數型別，這時候，你可能會遇到這樣的問題，假如你需要知道迭代器所指元素的型別是什么，進而獲取這個迭代器操作的演算法的回傳型別，但是問題是 C++ 沒有 typeof 這類判斷型別的函式，也無法直接獲取，那該如何是好？
注意是型別，不是迭代器的值，雖然 C++ 提供了一個 typeid() 運算子，這個運算子只能獲得型別的名稱，但不能用來宣告變數，要想獲得迭代器型別，這個時候又該如何是好呢？
function template 的引數推導機制是一個不錯的方法，
例如：
如果 I 是某個指向特定物件的指標，那么在 func 中需要指標所指向物件的型別的時候，怎么辦呢？這個還比較容易，模板的引數推導機制可以完成任務，
template <class I>
inline void func(I iter) {
func_imp(iter, *iter); // 傳入 iter 和 iter 所指的值，class 自動推導
}
通過模板的推導機制，就能輕而易舉的獲得指標所指向的物件的型別，
template <class I, class T>
void func_imp(I iter, T t) {
T tmp; // 這里就是迭代器所指物的類別
// ... 功能實作
}
int main() {
int i;
func(&i);//這里傳入的是一個迭代器（原生指標也是一種迭代器）
}
上面的做法呢，通過多層的迭代，很巧妙地匯出了 T ，但是卻很有局限性，比如，我希望 func() 回傳迭代器的 value type 型別回傳值， 函式的 "template 引數推導機制" 推導的只是引數，無法推導函式的回傳值型別，萬一需要推導函式的回傳值，好像就不行了，那么又該如何是好？
這就引出了下面的內嵌型別，
4、宣告內嵌型別
上述所說的 迭代器所指物件的型別，稱之為迭代器的 value type ，
盡管在 func_impl 中我們可以把 T 作為函式的回傳值，但是問題是用戶需要呼叫的是 func ，
如果在引數推導機制上加上內嵌型別 (typedef) 呢？為指定的物件型別定義一個別名，然后直接獲取，這樣來看一下實作：
template<typename T>
class MyIter {
public:
typedef T value_type; //內嵌型別宣告
MyIter(T *p = 0) : m_ptr(p) {}
T& operator*() const { return *m_ptr;}
private:
T *m_ptr;
};
//以迭代器所指物件的型別作為回傳型別
//注意typename是必須的，它告訴編譯器這是一個型別
template<typename MyIter>
typename MyIter::value_type Func(MyIter iter) {
return *iter;
}
int main(int argc, const char *argv[]) {
MyIter<int> iter(new int(666));
std::cout<<Func(iter)<<std::endl; //print=> 666
}
上面的解決方案看著可行，但其實呢，實際上還是有問題，這里有一個隱晦的陷阱：實際上并不是所有的迭代器都是 class type ，原生指標也是一種迭代器，由于原生指標不是 class type ，所以沒法為它定義內嵌型別，
因為 func 如果是一個泛型演算法，那么它也絕對要接受一個原生指標作為迭代器，下面的代碼編譯沒法通過：
int *p = new int(5);
cout<<Func(p)<<endl; // error
要解決這個問題，Partial specialization （模板偏特化）就出場了，
5、Partial specialization（模板偏特化）
所謂偏特化是指如果一個 class template 擁有一個以上的 template 引數，我們可以針對其中某個（或多個，但不是全部）template 引數進行特化，比如下面這個例子：
template <typename T>
class C {...}; //此泛化版本的 T 可以是任何型別
template <typename T>
class C<T*> {...}; //特化版本，僅僅適用于 T 為“原生指標”的情況，是泛化版本的限制版
所謂特化，就是特殊情況特殊處理，第一個類為泛化版本，T 可以是任意型別，第二個類為特化版本，是第一個類的特殊情況，只針對原生指標，
5.1、原生指標怎么辦？——特性 “萃取” traits
還記得前面說過的引數推導機制+內嵌型別機制獲取型別有什么問題嗎？問題就在于原生指標雖然是迭代器但不是class ，無法定義內嵌型別，而偏特化似乎可以解決這個問題，
有了上面的認識，我們再看看 STL 是如何應用的，STL 定義了下面的類模板，它專門用來“萃取”迭代器的特性，而value type 正是迭代器的特性之一：
traits 在 bits/stl_iterator_base_types.h 這個檔案中：
template<class _Tp>
struct iterator_traits<_Tp*> {
typedef ptrdiff_t difference_type;
typedef typename _Tp::value_type value_type;
typedef typename _Tp::pointer pointer;
typedef typename _Tp::reference reference;
typedef typename _Tp::iterator_category iterator_category;
};
template<typename Iterator>
struct iterator_traits { //型別萃取機
typedef typename Iterator::value_type value_type; //value_type 就是 Iterator 的型別型別
}
加入萃取機前后的變化：
template<typename Iterator> //萃取前
typename Iterator::value_type func(Iterator iter) {
return *iter;
}
//通過 iterator_traits 作用后的版本
template<typename Iterator> //萃取后
typename iterator_traits<Iterator>::value_type func(Iterator iter) {
return *iter;
}
看到這里也許你會問了，這個萃取前和萃取后的 typename ：iterator_traits::value_type 跟 Iterator::value_type 看起來一樣啊，為什么還要增加 iterator_traits 這一層封裝，豈不是多此一舉？
回想萃取之前的版本有什么缺陷：不支持原生指標，而通過萃取機的封裝，我們可以通過類模板的特化來支持原生指標的版本！如此一來，無論是智能指標，還是原生指標，iterator_traits::value_type 都能起作用，這就解決了前面的問題，
//iterator_traits的偏特化版本，針對迭代器是原生指標的情況
template<typename T>
struct iterator_traits<T*> {
typedef T value_type;
};
看到這里，我們不得不佩服的 STL 的設計者們，真·秒啊！我們用下面這張圖來總結一下前面的流程：
5.2 、const 偏特化
通過偏特化添加一層中間轉換的 traits 模板 class，能實作對原生指標和迭代器的支持，有的讀者可能會繼續追問：對于指向常數物件的指標又該怎么處理呢？比如下面的例子：
iterator_traits<const int*>::value_type // 獲得的 value_type 是 const int，而不是 int
const 變數只能初始化，而不能賦值（這兩個概念必須區分清楚），這將帶來下面的問題：
template<typename Iterator>
typename iterator_traits<Iterator>::value_type func(Iterator iter) {
typename iterator_traits<Iterator>::value_type tmp;
tmp = *iter; // 編譯 error
}
int val = 666 ;
const int *p = &val;
func(p); // 這時函式里對 tmp 的賦值都將是不允許的
那該如何是好呢？答案還是偏特化，來看實作：
template<typename T>
struct iterator_traits<const T*> { //特化const指標
typedef T value_type; //得到T而不是const T
}
6、traits編程技法總結
通過上面幾節的介紹，我們知道，所謂的 traits 編程技法無非 就是增加一層中間的模板 class，以解決獲取迭代器的型別中的原生指標問題，利用一個中間層 iterator_traits 固定了 func 的形式，使得重復的代碼大量減少，唯一要做的就是稍稍特化一下 iterator_tartis 使其支持 pointer 和 const pointer ，
#include <iostream>
template <class T>
struct MyIter {
typedef T value_type; // 內嵌型別宣告
T* ptr;
MyIter(T* p = 0) : ptr(p) {}
T& operator*() const { return *ptr; }
};
// class type
template <class T>
struct my_iterator_traits {
typedef typename T::value_type value_type;
};
// 偏特化 1
template <class T>
struct my_iterator_traits<T*> {
typedef T value_type;
};
// 偏特化 2
template <class T>
struct my_iterator_traits<const T*> {
typedef T value_type;
};
// 首先詢問 iterator_traits<I>::value_type,如果傳遞的 I 為指標,則進入特化版本,iterator_traits 直接回答;如果傳遞進來的 I 為 class type,就去詢問 T::value_type.
template <class I>
typename my_iterator_traits<I>::value_type Func(I ite) {
std::cout << "normal version" << std::endl;
return *ite;
}
int main(int argc, const char *argv[]) {
MyIter<int> ite(new int(6));
std::cout << Func(ite)<<std::endl;//print=> 6
int *p = new int(7);
std::cout<<Func(p)<<std::endl;//print=> 7
const int k = 8;
std::cout<<Func(&k)<<std::endl;//print=> 8
}
上述的程序是首先詢問 iterator_traits::value_type，如果傳遞的 I 為指標,則進入特化版本, iterator_traits 直接回答T；如果傳遞進來的 I 為 class type ，就去詢問 T::value_type，
通俗的解釋可以參照下圖：
總結：核心知識點在于 模板引數推導機制+內嵌型別定義機制， 為了能處理原生指標這種特殊的迭代器，引入了偏特化機制，traits 就像一臺 “特性萃取機”，把迭代器放進去，就能榨取出迭代器的特性，
這種偏特化是針對可呼叫函式 func 的偏特化，想象一種極端情況，假如 func 有幾百萬行代碼，那么如果不這樣做的話，就會造成非常大的代碼污染，同時增加了代碼冗余，
7、迭代器的型別和種類
7.1 迭代器的型別
我們再來看看迭代器的型別，常見迭代器相應型別有 5 種：
-
value_type：迭代器所指物件的型別，原生指標也是一種迭代器，對于原生指標 int*，int 即為指標所指物件的型別，也就是所謂的 value_type ， -
difference_type： 用來表示兩個迭代器之間的距離，對于原生指標，STL 以 C++ 內建的 ptrdiff_t 作為原生指標的 difference_type， -
reference_type： 是指迭代器所指物件的型別的參考，reference_type 一般用在迭代器的 * 運算子多載上，如果 value_type 是 T，那么對應的 reference_type 就是 T&；如果 value_type 是 const T，那么對應的reference_type 就是 const T&， -
pointer_type： 就是相應的指標型別，對于指標來說，最常用的功能就是 operator* 和 operator-> 兩個運算子， -
iterator_category： 的作用是標識迭代器的移動特性和可以對迭代器執行的操作，從 iterator_category 上，可將迭代器分為 Input Iterator、Output Iterator、Forward Iterator、Bidirectional Iterator、Random Access Iterator 五類，這樣分可以盡可能地提高效率，template<typename Category, typename T, typename Distance = ptrdiff_t, typename Pointer = T*, typename Reference = T&> struct iterator //迭代器的定義 { typedef Category iterator_category; typedef T value_type; typedef Distance difference_type; typedef Pointer pointer; typedef Reference reference; };
iterator class 不包含任何成員變數，只有型別的定義，因此不會增加額外的負擔，由于后面三個型別都有默認值，在繼承它的時候，只需要提供前兩個引數就可以了，這個類主要是用來繼承的，在實作具體的迭代器時，可以繼承上面的類，這樣子就不會漏掉上面的 5 個型別了，
對應的迭代器萃取機設計如下：
tempalte<typename I>
struct iterator_traits {//特性萃取機，萃取迭代器特性
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typeanme I:difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
//需要對型別為指標和 const 指標設計特化版本看
7.2、迭代器的分類
最后，我們來看看，迭代器型別 iterator_category 對應的迭代器類別，這個類別會限制迭代器的操作和移動特性，
除了原生指標以外，迭代器被分為五類：
Input Iterator： 此迭代器不允許修改所指的物件，是只讀的，支持 ==、!=、++、*、-> 等操作，Output Iterator：允許演算法在這種迭代器所形成的區間上進行只寫操作，支持 ++、* 等操作，Forward Iterator：允許演算法在這種迭代器所形成的區間上進行讀寫操作，但只能單向移動，每次只能移動一步，支持 Input Iterator 和 Output Iterator 的所有操作，Bidirectional Iterator：允許演算法在這種迭代器所形成的區間上進行讀寫操作，可雙向移動，每次只能移動一步，支持 Forward Iterator 的所有操作，并另外支持 – 操作，Random Access Iterator：包含指標的所有操作，可進行隨機訪問，隨意移動指定的步數，支持前面四種 Iterator 的所有操作，并另外支持 [n] 運算子等操作，
那么，這里，小賀想問大家，為什么我們要對迭代器進行分類呢？迭代器在具體的容器里是到底如何運用的呢？這個問題就放到下一節在講，
最最后，我們再來回顧一下六大組件的關系：
這六大組件的互動關系：container（容器） 通過 allocator（配置器） 取得資料儲存空間，algorithm（演算法）通過 iterator（迭代器）存取 container（容器） 內容，functor（仿函式） 可以協助 algorithm（演算法） 完成不同的策略變化，adapter（配接器） 可以修飾或套接 functor（仿函式），
參考文章：
-
《STL原始碼剖析-侯捷》
-
https://zhuanlan.zhihu.com/p/85809752
-
https://wendeng.github.io/
8、結尾
如果覺得文章對你有幫助，歡迎分享給你的朋友，一鍵三連，謝謝各位，
我是 herongwei ，是男人，就對自己狠一點，祝大家作業愉快，我們下期見，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/242712.html
標籤：其他