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

2. 迭代器設(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ì)體會。

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

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

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

3. 智能指針

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í)候，不可避免的要對遍歷的容器內(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) 對于 list ，取下一個(gè)元素不是通過自增而是通過 next  指針來取，使用智能指針可以對自增進(jìn)行重載，從而提供統(tǒng)一接口。

4.模板參數(shù)推導(dǎo)

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

在算法中，你可能會定義一個(gè)簡單的中間變量或者設(shè)定算法的返回變量類型，這時(shí)候，你可能會遇到這樣的問題：

假如你需要知道迭代器所指元素的類型是什么，進(jìn)而獲取這個(gè)迭代器操作的算法的返回類型，但是問題是 C++   沒有 typeof 這類判斷類型的函數(shù)，也無法直接獲取，那該如何是好？

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

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

例如：

如果 I  是某個(gè)指向特定對象的指針，那么在 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ǎo)
}

通過模板的推導(dǎo)機(jī)制，就能輕而易舉的獲得指針?biāo)赶虻膶ο蟮念愋汀?/span>

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)嵌型別。

5. 聲明內(nèi)嵌型別

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

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

如果在參數(shù)推導(dǎo)機(jī)制上加上內(nèi)嵌型別 (typedef)  呢？為指定的對象類型定義一個(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;
};

//以迭代器所指對象的類型作為返回類型
//注意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è)泛型算法，那么它也絕對要接受一個(gè)原生指針作為迭代器，下面的代碼編譯沒法通過：

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

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

6. Partial specialization 模板偏特化

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

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

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

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

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

有了上面的認(rèn)識，我們再看看 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;
}

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

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

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

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

6.2 、const 偏特化

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

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ù)里對 tmp 的賦值都將是不允許的

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

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

7. traits編程技法

通過上面幾節(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é)：核心知識點(diǎn)在于 模板參數(shù)推導(dǎo)機(jī)制+內(nèi)嵌類型定義機(jī)制， 為了能處理原生指針這種特殊的迭代器，引入了偏特化機(jī)制。traits 就像一臺 “特性萃取機(jī)”，把迭代器放進(jìn)去，就能榨取出迭代器的特性。

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

8.迭代器的型別和分類

8.1 迭代器的型別

我們再來看看迭代器的型別，常見迭代器相應(yīng)型別有 5 種：

• value_type：迭代器所指對象的類型，原生指針也是一種迭代器，對于原生指針 int*，int 即為指針?biāo)笇ο蟮念愋停簿褪撬^的 value_type 。

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

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

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

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

對應(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;
};

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

8.2、迭代器的分類

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

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

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

最最后，我們再來回顧一下六大組件的關(guān)系：

這六大組件的交互關(guān)系：

container（容器） 通過 allocator（配置器） 取得數(shù)據(jù)儲存空間，algorithm（算法）通過 iterator（迭代器）存取 container（容器） 內(nèi)容，functor（仿函數(shù)） 可以協(xié)助 algorithm（算法） 完成不同的策略變化，adapter（配接器） 可以修飾或套接 functor（仿函數(shù)）。