迭代器是一種抽象的設計概念，《Design Patterns》一書中對于 iterator 模式的定義如下：提供一種方法，使之能夠依序巡訪某個聚合物（容器）所含的各個元素，而又無需暴露該聚合物的內部表述方式。

有時在我們使用迭代器的時候，很可能會用到其相應型別（associated type）。什么是相應型別，迭代器所指之物的型別、所屬的類型（隨機迭代器、單向雙向、只讀只寫）便是。

如果我們想要以迭代器所指之物型別為類型聲明一個變量，該怎么辦呢？

一種解決方法是：利用 function template 的參數推倒（argument deducation）機制。

例如：

templatevoid func(I iter, T t) {T tmp;	// 成功聲明了迭代器所指之物類型的變量
}

templatevoid func(I iter) {func_impl(iter, *iter);
}

int main() {int num = 0;
    func(&num);
}

但迭代器的型別不只是迭代器所指對象的型別，而且上述解法并不能用于所有情況，因此需要更加全面的解法。

比如上述解法就無法解決 value type 用于函數返回值的情況，畢竟推導的只是參數，無法推導返回值型別。

聲明內嵌類型似乎是個很好的方法，像這樣：

templatestruct MyIter {typedef T value_type;
    T* ptr;
    
    MyIter(T* p) {ptr = p;
    }
    T& operator*() {return *ptr; 
    }
};

templatetypename I::valie_type func (I ite) {// typename I::valie_type 為返回值類型
	return *ite;
}

MyIterite(new int(1231));
cout<< func(ite)<< endl;

此處 typename 的作用是告訴編譯器這是一個類型，因為 I 是一個模板參數，在它被具現化之前編譯器對它一無所知，也就是說編譯器不知道 I::valie_type 是個類型或是成員函數等等。

更多關于 typename 的用法可以看這個鏈接：typename 的用法

還有一種情況是上述代碼無法解決的，那就是不是所有的迭代器都是 class type，原生指針就不是。如果不是 class type 就無法為它定義內嵌型別，因此我們需要對原生指針作些特殊處理。

例如：

templatestruct iterator_traits {typedef typename I::value_type value_type;
};
templatestruct iterator_traits{typedef T value_type;
};
templatestruct iterator_traits{typedef T value_type;
};

此時，不管是 class type 類型的迭代器還是原生指針都可以處理了。

迭代器萃取，就是為我們榨取出迭代器的相應型別。當然，要使萃取有效的運行，每個迭代器都要自行以內嵌性別定義（nested typedef）的方式定義出相應型別。

最常用的迭代器型別有五種：value type，difference type，pointer，reference，iterator catagoly。

迭代萃取機 traits 會很忠實地將它們榨取出來：

templatestruct iterator_traits {typedef typename I::iterator_category 	iterator_category;
    typedef typename I::value_type			value_ type;
    typedef typename I::difference_type		difference_type;
    typedef typename I::pointer				pointer;
    typedef typename I::reference			reference;
};

iterator_traits 必須針對傳入型別為 point 及 point-to-const 者，設計特化版本。

value type 是指迭代器所指對象的型別。

做法如上文所述。

difference type 用來表示兩個迭代器之間的距離。對于連續空間的容器來說，頭尾之間的距離就是大容量，因此它也可以用來表示一個容器的大容量。

如果一個泛型算法提供記數功能，例如 STL 的count()，其返回值就必須使用迭代器的 difference type：

templatetypename iterator_traits::difference_type		// 返回值類型，實際是 I::difference type
    count(I first, I last, const T& value) {typename iterator_traits::difference_type ret = 0;
    for (; first != last; ++first) {if (*first == value) {ret++;
        }
    }
    return ret;
}

針對相應型別 difference type，traits 的兩個特化版本，以 C++ 內建的 ptrdiff_t 作為原生指針的 difference type。

templatestruct iterator_traits {typedef typename I::difference_type difference_type;
};
templatestruct iterator_traits{typedef ptrdiff_t difference_type;
};
templatestruct iterator_traits{typedef ptrdiff_t difference_type;
};

templatestruct iterator_traits {typedef typename I::pointer 	pointer;
    typedef typename I::reference	reference;
};
templatestruct iterstor_traits{typedef T* 	pointer;
    typedef T& 	reference;
};
templatestruct iterstor_traits{typedef const T*	pointer;
    typedef const T& 	reference;
};

templateinline iterator_traits::difference_type
    __distance(InputIterator first, InputIterator last,
              input_iterator_tag) {iterator_traits::iteratordifference_type n = 0;
    // 逐一累計距離
    while (first != last) {++first;
        ++n;
    }
    return n;
}

templateinline iterator_traits::difference_type
    __distance(RandomAccessIterator first, RandomAccessIterator last,
               random_access_iterator_tag) {// 直接計算差距
    return last - first;
}

// InputIterator 命名規則：所能接受的最低階迭代器類型
templateinline iterator_traits::difference_type
    distance(InputIterator first, InputIterator last) {typedef typename iterator_traits::iterator_category category;
    return __distance(first, last, category());
}