大家好,，我是小賀,。

點(diǎn)贊再看，養(yǎng)成習(xí)慣

文章每周持續(xù)更新,，可以微信搜索「herongwei」第一時(shí)間閱讀和催更,，本文 GitHub : https://github.com/rongweihe/MoreThanCPlusPlus 已經(jīng)收錄，有一線大廠面試點(diǎn)思維導(dǎo)圖,，也整理了很多我的文檔，歡迎 star 和完善,。一起加油,，變得更好！

前言

上一篇,，我們剖析了 STL 空間配置器,，這一篇文章，我們來學(xué)習(xí)下 STL 迭代器以及背后的 traits 編程技法,。

在 STL 編程中,，容器和算法是獨(dú)立設(shè)計(jì)的，容器里面存的是數(shù)據(jù),，而算法則是提供了對(duì)數(shù)據(jù)的操作,，在算法操作數(shù)據(jù)的過程中，要用到迭代器,，迭代器可以看做是容器和算法中間的橋梁,。

1,、迭代器設(shè)計(jì)模式

為何說迭代器的時(shí)候,，還談到了設(shè)計(jì)模式？這個(gè)迭代器和設(shè)計(jì)模式又有什么關(guān)系呢,？

其實(shí),，在《設(shè)計(jì)模式：可復(fù)用面向?qū)ο筌浖幕A(chǔ)》（GOF）這本經(jīng)典書中，談到了 23 種設(shè)計(jì)模式,，其中就有 iterator 迭代模式,，且篇幅頗大。

碰巧,，筆者在研究 STL 源碼的時(shí)候,，同樣的發(fā)現(xiàn)有 iterator 迭代器，而且還占據(jù)了一章的篇幅,。

在設(shè)計(jì)模式中,，關(guān)于 iterator 的描述如下：一種能夠順序訪問容器中每個(gè)元素的方法,，使用該方法不能暴露容器內(nèi)部的表達(dá)方式。而類型萃取技術(shù)就是為了要解決和 iterator 有關(guān)的問題的,。

有了上面這個(gè)基礎(chǔ),，我們就知道了迭代器本身也是一種設(shè)計(jì)模式，其設(shè)計(jì)思想值得我們仔細(xì)體會(huì),。

那么 C++ STL 實(shí)現(xiàn) iterator 和 GOF 介紹的迭代器實(shí)現(xiàn)方法什么區(qū)別呢,？ 那首先我們需要了解 C++ 中的兩個(gè)編程范式的概念，OOP（面向?qū)ο缶幊蹋┖?GP（泛型編程）,。

在 C++ 語言里面,，我們可用以下方式來簡(jiǎn)單區(qū)分一下 OOP 和 GP ：

OOP：將 methods 和 datas 關(guān)聯(lián)到一起 （通俗點(diǎn)就是方法和成員變量放到一個(gè)類中實(shí)現(xiàn)），通過繼承的方式,，利用虛函數(shù)表（virtual）來實(shí)現(xiàn)運(yùn)行時(shí)類型的判定,，也叫"動(dòng)態(tài)多態(tài)"，由于運(yùn)行過程中需根據(jù)類型去檢索虛函數(shù)表,，因此效率相對(duì)較低,。

GP：泛型編程，也被稱為"靜態(tài)多態(tài)",，多種數(shù)據(jù)類型在同一種算法或者結(jié)構(gòu)上皆可操作,，其效率與針對(duì)某特定數(shù)據(jù)類型而設(shè)計(jì)的算法或者結(jié)構(gòu)相同， 具體數(shù)據(jù)類型在編譯期確定,，編譯器承擔(dān)更多,，代碼執(zhí)行效率高。在 STL 中利用 GP 將 methods 和 datas 實(shí)現(xiàn)了分而治之,。

而 C++ STL 庫的整個(gè)實(shí)現(xiàn)采用的就是 GP（Generic Programming）,，而不是 OOP（Object Oriented Programming）。而 GOF 設(shè)計(jì)模式采用的就是繼承關(guān)系實(shí)現(xiàn)的,，因此,，相對(duì)來講，C++ STL 的實(shí)現(xiàn)效率會(huì)相對(duì)較高,，而且也更有利于維護(hù),。

在 STL 編程結(jié)構(gòu)里面，迭代器其實(shí)也是一種模板 class ,，迭代器在 STL 中得到了廣泛的應(yīng)用,，通過迭代器，容器和算法可以有機(jī)的綁定在一起,，只要對(duì)算法給予不同的迭代器,，比如 vector::iterator、list::iterator,，std::find() 就能對(duì)不同的容器進(jìn)行查找,，而無需針對(duì)某個(gè)容器來設(shè)計(jì)多個(gè)版本,。

這樣看來，迭代器似乎依附在容器之下,，那么,，有沒有獨(dú)立而適用于所有容器的泛化的迭代器呢？這個(gè)問題先留著,，在后面我們會(huì)看到,，在 STL 編程結(jié)構(gòu)里面，它是如何把迭代器運(yùn)用的爐火純青,。

2、智能指針

STL 是泛型編程思想的產(chǎn)物,，是以泛型編程為指導(dǎo)而產(chǎn)生的,。具體來說，STL 中的迭代器將范型算法 (find, count, find_if) 等應(yīng)用于某個(gè)容器中,，給算法提供一個(gè)訪問容器元素的工具,，iterator 就扮演著這個(gè)重要的角色,。

稍微看過 STL 迭代器源碼的,，就明白迭代器其實(shí)也是一種智能指針，因此,，它也就擁有了一般指針的所有特點(diǎn)—— 能夠?qū)ζ溥M(jìn)行 * 和 -> 操作,。

template<typename T>
class ListIterator {//mylist迭代器
public:
    ListIterator(T *p = 0) : m_ptr(p){} //構(gòu)造函數(shù)
    T& operator*() const { return *m_ptr;}  //取值，即dereference
    T* operator->() const { return m_ptr;} //成員訪問,，即member access
    //...
};

但是在遍歷容器的時(shí)候,，不可避免的要對(duì)遍歷的容器內(nèi)部有所了解，所以,，干脆把迭代器的開發(fā)工作交給容器的設(shè)計(jì)者,，如此以來，所有實(shí)現(xiàn)細(xì)節(jié)反而得以封裝起來不被使用者看到,，這也正是為什么每一種 STL 容器都提供有專屬迭代器的緣故,。

比如筆者自己實(shí)現(xiàn)的 list 迭代器在這里使用的好處主要有：

• (1) 不用擔(dān)心內(nèi)存泄漏（類似智能指針，析構(gòu)函數(shù)釋放內(nèi)存）,；
• (2) 對(duì)于 list ,，取下一個(gè)元素不是通過自增而是通過 next 指針來取，使用智能指針可以對(duì)自增進(jìn)行重載,，從而提供統(tǒng)一接口,。

3,、template 參數(shù)推導(dǎo)

參數(shù)推導(dǎo)能幫我們解決什么問題呢,？

在算法中,，你可能會(huì)定義一個(gè)簡(jiǎn)單的中間變量或者設(shè)定算法的返回變量類型，這時(shí)候,，你可能會(huì)遇到這樣的問題,，假如你需要知道迭代器所指元素的類型是什么，進(jìn)而獲取這個(gè)迭代器操作的算法的返回類型,，但是問題是 C++ 沒有 typeof 這類判斷類型的函數(shù),，也無法直接獲取，那該如何是好,？

注意是類型,，不是迭代器的值，雖然 C++ 提供了一個(gè) typeid() 操作符,，這個(gè)操作符只能獲得型別的名稱,，但不能用來聲明變量。要想獲得迭代器型別,，這個(gè)時(shí)候又該如何是好呢,？

function template 的參數(shù)推導(dǎo)機(jī)制是一個(gè)不錯(cuò)的方法。

例如：

如果 I 是某個(gè)指向特定對(duì)象的指針,，那么在 func 中需要指針?biāo)赶驅(qū)ο蟮男蛣e的時(shí)候,，怎么辦呢？這個(gè)還比較容易,，模板的參數(shù)推導(dǎo)機(jī)制可以完成任務(wù),，

template <class I>
inline void func(I iter) {
    func_imp(iter, *iter); // 傳入 iter 和 iter 所指的值，class 自動(dòng)推導(dǎo)
}

通過模板的推導(dǎo)機(jī)制,，就能輕而易舉的獲得指針?biāo)赶虻膶?duì)象的類型,。

template <class I, class T>
void func_imp(I iter, T t) {
        T tmp; // 這里就是迭代器所指物的類別
        // ... 功能實(shí)現(xiàn)
}
int main() {
    int i;
    func(&i);//這里傳入的是一個(gè)迭代器（原生指針也是一種迭代器）
}

上面的做法呢，通過多層的迭代,，很巧妙地導(dǎo)出了 T ,，但是卻很有局限性，比如,，我希望 func() 返回迭代器的 value type 類型返回值,， 函數(shù)的 "template 參數(shù)推導(dǎo)機(jī)制" 推導(dǎo)的只是參數(shù)，無法推導(dǎo)函數(shù)的返回值類型,。萬一需要推導(dǎo)函數(shù)的返回值,，好像就不行了，那么又該如何是好,？

這就引出了下面的內(nèi)嵌型別,。

4、聲明內(nèi)嵌型別

上述所說的 迭代器所指對(duì)象的型別,，稱之為迭代器的 value type ,。

盡管在 func_impl 中我們可以把 T 作為函數(shù)的返回值，但是問題是用戶需要調(diào)用的是 func ,。

如果在參數(shù)推導(dǎo)機(jī)制上加上內(nèi)嵌型別 (typedef) 呢,？為指定的對(duì)象類型定義一個(gè)別名，然后直接獲取,，這樣來看一下實(shí)現(xiàn)：

template<typename T>
class MyIter {
public:
    typedef T value_type; //內(nèi)嵌類型聲明
    MyIter(T *p = 0) : m_ptr(p) {}
    T& operator*() const { return *m_ptr;}
private:
    T *m_ptr;
};

//以迭代器所指對(duì)象的類型作為返回類型
//注意typename是必須的,，它告訴編譯器這是一個(gè)類型
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
}

上面的解決方案看著可行，但其實(shí)呢,，實(shí)際上還是有問題,，這里有一個(gè)隱晦的陷阱：實(shí)際上并不是所有的迭代器都是 class type ，原生指針也是一種迭代器,，由于原生指針不是 class type ,，所以沒法為它定義內(nèi)嵌型別。

因?yàn)?func 如果是一個(gè)泛型算法,，那么它也絕對(duì)要接受一個(gè)原生指針作為迭代器,，下面的代碼編譯沒法通過：

int *p = new int(5);
cout<<Func(p)<<endl; // error

要解決這個(gè)問題，Partial specialization （模板偏特化）就出場(chǎng)了,。

5、Partial specialization（模板偏特化）

所謂偏特化是指如果一個(gè) class template 擁有一個(gè)以上的 template 參數(shù),，我們可以針對(duì)其中某個(gè)（或多個(gè),，但不是全部）template 參數(shù)進(jìn)行特化,，比如下面這個(gè)例子：

template <typename T>
class C {...}; //此泛化版本的 T 可以是任何類型
template <typename T>
class C<T*> {...}; //特化版本,，僅僅適用于 T 為“原生指針”的情況，是泛化版本的限制版

所謂特化,，就是特殊情況特殊處理,，第一個(gè)類為泛化版本，T 可以是任意類型,，第二個(gè)類為特化版本,，是第一個(gè)類的特殊情況，只針對(duì)原生指針,。

5.1,、原生指針怎么辦,？——特性 “萃取” traits

還記得前面說過的參數(shù)推導(dǎo)機(jī)制+內(nèi)嵌型別機(jī)制獲取型別有什么問題嗎？問題就在于原生指針雖然是迭代器但不是class ,，無法定義內(nèi)嵌型別,，而偏特化似乎可以解決這個(gè)問題,。

有了上面的認(rèn)識(shí)，我們?cè)倏纯?STL 是如何應(yīng)用的,。STL 定義了下面的類模板,，它專門用來“萃取”迭代器的特性，而value type 正是迭代器的特性之一：

traits 在 bits/stl_iterator_base_types.h 這個(gè)文件中：

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 {  //類型萃取機(jī)
typedef typename Iterator::value_type value_type; //value_type 就是 Iterator 的類型型別
}

加入萃取機(jī)前后的變化：

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;
}

看到這里也許你會(huì)問了,，這個(gè)萃取前和萃取后的 typename ：iterator_traits::value_type 跟 Iterator::value_type 看起來一樣啊,，為什么還要增加 iterator_traits 這一層封裝，豈不是多此一舉,？

回想萃取之前的版本有什么缺陷：不支持原生指針,。而通過萃取機(jī)的封裝，我們可以通過類模板的特化來支持原生指針的版本,！如此一來,，無論是智能指針，還是原生指針,，iterator_traits::value_type 都能起作用,，這就解決了前面的問題。

//iterator_traits的偏特化版本,，針對(duì)迭代器是原生指針的情況
template<typename T>
struct iterator_traits<T*> {
    typedef T value_type;
};

看到這里,，我們不得不佩服的 STL 的設(shè)計(jì)者們，真·秒??！我們用下面這張圖來總結(jié)一下前面的流程：

5.2 ,、const 偏特化

通過偏特化添加一層中間轉(zhuǎn)換的 traits 模板 class,，能實(shí)現(xiàn)對(duì)原生指針和迭代器的支持，有的讀者可能會(huì)繼續(xù)追問：對(duì)于指向常數(shù)對(duì)象的指針又該怎么處理呢,？比如下面的例子：

iterator_traits<const int*>::value_type  // 獲得的 value_type 是 const int,，而不是 int

const 變量只能初始化，而不能賦值（這兩個(gè)概念必須區(qū)分清楚）,。這將帶來下面的問題：

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); // 這時(shí)函數(shù)里對(duì) tmp 的賦值都將是不允許的

那該如何是好呢,？答案還是偏特化，來看實(shí)現(xiàn)：

template<typename T>
struct iterator_traits<const T*> { //特化const指針
    typedef T value_type; //得到T而不是const T
}

6,、traits編程技法總結(jié)

通過上面幾節(jié)的介紹，我們知道,，所謂的 traits 編程技法無非 就是增加一層中間的模板 class,，以解決獲取迭代器的型別中的原生指針問題。利用一個(gè)中間層 iterator_traits 固定了 func 的形式，使得重復(fù)的代碼大量減少,，唯一要做的就是稍稍特化一下 iterator_tartis 使其支持 pointer 和 const pointer ,。

#include <iostream>

template <class T>
struct MyIter {
    typedef T value_type; // 內(nèi)嵌型別聲明
    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 為指針,則進(jìn)入特化版本,iterator_traits 直接回答;如果傳遞進(jìn)來的 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 為指針,則進(jìn)入特化版本, iterator_traits 直接回答T,；如果傳遞進(jìn)來的 I 為 class type ,，就去詢問 T::value_type。

通俗的解釋可以參照下圖：

總結(jié)：核心知識(shí)點(diǎn)在于 模板參數(shù)推導(dǎo)機(jī)制+內(nèi)嵌類型定義機(jī)制,， 為了能處理原生指針這種特殊的迭代器,，引入了偏特化機(jī)制。traits 就像一臺(tái) “特性萃取機(jī)”,，把迭代器放進(jìn)去,，就能榨取出迭代器的特性。

這種偏特化是針對(duì)可調(diào)用函數(shù) func 的偏特化,，想象一種極端情況,，假如 func 有幾百萬行代碼，那么如果不這樣做的話,，就會(huì)造成非常大的代碼污染,。同時(shí)增加了代碼冗余。

7,、迭代器的型別和種類

7.1 迭代器的型別

我們?cè)賮砜纯吹鞯男蛣e，常見迭代器相應(yīng)型別有 5 種：

• value_type：迭代器所指對(duì)象的類型,，原生指針也是一種迭代器,，對(duì)于原生指針 int*，int 即為指針?biāo)笇?duì)象的類型,，也就是所謂的 value_type ,。

• difference_type： 用來表示兩個(gè)迭代器之間的距離，對(duì)于原生指針,，STL 以 C++ 內(nèi)建的 ptrdiff_t 作為原生指針的 difference_type,。

• reference_type： 是指迭代器所指對(duì)象的類型的引用,，reference_type 一般用在迭代器的 * 運(yùn)算符重載上,，如果 value_type 是 T，那么對(duì)應(yīng)的 reference_type 就是 T&,；如果 value_type 是 const T,，那么對(duì)應(yīng)的reference_type 就是 const T&。

• pointer_type： 就是相應(yīng)的指針類型,，對(duì)于指針來說,，最常用的功能就是 operator* 和 operator-> 兩個(gè)運(yùn)算符。

• iterator_category： 的作用是標(biāo)識(shí)迭代器的移動(dòng)特性和可以對(duì)迭代器執(zhí)行的操作，從 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 不包含任何成員變量,，只有類型的定義，因此不會(huì)增加額外的負(fù)擔(dān),。由于后面三個(gè)類型都有默認(rèn)值,，在繼承它的時(shí)候，只需要提供前兩個(gè)參數(shù)就可以了,。這個(gè)類主要是用來繼承的,，在實(shí)現(xiàn)具體的迭代器時(shí)，可以繼承上面的類,，這樣子就不會(huì)漏掉上面的 5 個(gè)型別了,。

對(duì)應(yīng)的迭代器萃取機(jī)設(shè)計(jì)如下：

tempalte<typename I>
struct iterator_traits {//特性萃取機(jī)，萃取迭代器特性
    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;
};

//需要對(duì)型別為指針和 const 指針設(shè)計(jì)特化版本看

7.2,、迭代器的分類

最后，我們來看看,，迭代器型別 iterator_category 對(duì)應(yīng)的迭代器類別,，這個(gè)類別會(huì)限制迭代器的操作和移動(dòng)特性。
除了原生指針以外,，迭代器被分為五類：

• Input Iterator： 此迭代器不允許修改所指的對(duì)象,，是只讀的。支持 ==,、!=,、++、*,、-> 等操作,。
• Output Iterator：允許算法在這種迭代器所形成的區(qū)間上進(jìn)行只寫操作。支持 ++,、* 等操作,。
• Forward Iterator：允許算法在這種迭代器所形成的區(qū)間上進(jìn)行讀寫操作，但只能單向移動(dòng),，每次只能移動(dòng)一步,。支持 Input Iterator 和 Output Iterator 的所有操作,。
• Bidirectional Iterator：允許算法在這種迭代器所形成的區(qū)間上進(jìn)行讀寫操作，可雙向移動(dòng),，每次只能移動(dòng)一步,。支持 Forward Iterator 的所有操作，并另外支持 – 操作,。
• Random Access Iterator：包含指針的所有操作,，可進(jìn)行隨機(jī)訪問，隨意移動(dòng)指定的步數(shù),。支持前面四種 Iterator 的所有操作,，并另外支持 [n] 操作符等操作。

那么,，這里,，小賀想問大家，為什么我們要對(duì)迭代器進(jìn)行分類呢,？迭代器在具體的容器里是到底如何運(yùn)用的呢,？這個(gè)問題就放到下一節(jié)在講。

最最后,，我們?cè)賮砘仡櫼幌铝蠼M件的關(guān)系：

這六大組件的交互關(guān)系：container（容器） 通過 allocator（配置器） 取得數(shù)據(jù)儲(chǔ)存空間,，algorithm（算法）通過 iterator（迭代器）存取 container（容器） 內(nèi)容，functor（仿函數(shù)） 可以協(xié)助 algorithm（算法） 完成不同的策略變化,，adapter（配接器） 可以修飾或套接 functor（仿函數(shù)）,。

參考文章：

• 《STL源碼剖析-侯捷》

• https://zhuanlan.zhihu.com/p/85809752

• https://wendeng./

8,、結(jié)尾

如果覺得文章對(duì)你有幫助,，歡迎分享給你的朋友，一鍵三連,，謝謝各位,。
我是 herongwei ，是男人,，就對(duì)自己狠一點(diǎn),，祝大家工作愉快，我們下期見,。