疊代器
設計思維
設計模式：提供一種方法，使之能夠依序巡訪某個聚合物（容器）所含的各個元素，而又無需暴露該聚合物的内部表述方式。
疊代器作用：STL的中心思想是将容器和算法分開，彼此獨立設計，最後再用膠着劑将它們撮合在一起，疊代器扮演膠着劑
疊代器是一種是智能指針
疊代器行為類似于指針，最重要的作用是内容提領（deference）和成員通路（member access），是以，疊代器最重要的程式設計工作就是對operator*和operator->進行重載工作，可以參考auto_ptr（過時了）。
為什麼每種STL容器有專屬疊代器？
疊代器的實作需要容器細節：
要完成一個容器如List的疊代器，需要暴露很多List實作細節，如1.為了制作begin和end兩個疊代器，疊代器内部需要連結清單節點的指針，暴露了連結清單節點。2.為了打成++，需要暴露next屬性。
暴露細節無法避免，幹脆讓容器設計者開發專屬疊代器
疊代器相應型别
概念：疊代器所指之物的型别等
問題：C++隻支援sizeof()，不支援typeof()，不能識别疊代器所指之物的型别
解決：
方法1.利用function template的參數推導機制
局限性：
●五種類型不能全推出
●不能用于函數的傳回值，template參數推導的隻是參數
Traits程式設計技法——STL源代碼門鑰
traits大量運用于STL中，利用“内嵌型别”的程式設計技巧與編譯器的template參數推導功能，增強了C++未能提供的關于型别認證方面的能力
方法2.聲明内嵌型别
可以傳回疊代器所指類型
局限性：并不是所有的疊代器都是類，如原生指針。不是類就無法定義内嵌型别。
方法3.traits（traits意為特性）
偏特化：針對template參數更進一步的條件限制所設計出來的一個特化版本，不一定要指定template部分參數。
//這也是一種偏特化，這個特化版本适用于“T為原生指針”的情況
//“T為原生指針”是對“T為任何型别”的限制，隻要限制了就是特化
template<typename T>
class C<T*>{}
traits萃取疊代器特性
//1.如果I(疊代器)定義了自己的value type，那麼萃取出的value_type就是I::value_type
template<class I>
struct iterator_traits{
typedef typename I::value_type value_type;
};
//2.原生指針特化版，如int*不是類，沒有定義value type，也可以萃取出所指的類型
template<class T>
struct iterator_traits<T*>{
typedef T value_type;
};
//3.原生const指針特化版，我們不需要const特性
template<class T>
struct iterator_traits<const T*>{
typedef T value_type;
};
應用
可以用
typename iterator_traits<I>::value_type
來得到任何疊代器I的value_type
疊代器的五種型别
為了所開發的容器與STL相容，一定定義五種相應型别
1.value type
概念：疊代器所指對象的型别
具體見上面
2.difference type
概念：兩個疊代器之間的距離（元素個數）
traits：
//1.普通版本，針對類内定義了difference_type
template<class I>
struct iterator_traits{
typedef typename I::difference_type difference_type;
};
//2.原生非const指針版本
template<class T>
struct iterator_traits<T*>{
typedef ptrdiff_t difference_type; //ptrdiff_t為兩個指針的差，定義于<cstddef>
};
//3.原生const指針 略
template<class T>
struct iterator_traits<const T*>{
typedef ptrdiff_t difference_type; //ptrdiff_t為兩個指針的差，定義于<cstddef>
};
應用：STL的計數函數count()，傳回值必須使用疊代器的difference type
3.reference type
4.pointer type
區分：reference type和pointer type
Item& operator*() const{return *ptr;} //Item&是reference type
Item* operator->() const{return ptr;} //Item*是pointer type
traits：
//1.普通版本，針對class type
template<class I>
struct iterator_traits{
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
//2.針對非const原生指針
template<class I>
struct iterator_traits<T*>{
typedef T* pointer;
typedef T& reference;
};
//2.針對非const原生指針
template<class I>
struct iterator_traits<const T*>{
typedef const T* pointer;
typedef const T& reference;
};
5.iterator_category
●五類疊代器：
●關系：
●考慮效率：如果對Random類一個個移動效率太低，是以要根據類别調用不同的函數
方法1：缺乏效率
方法2：函數重載
●traits實作
//這個traits比前面四種難了解一點
//如value type萃取的是iter所指的類型，iterator_categoty萃取的就是屬于五類疊代器中的哪一類
//萃取的是疊代器的最強類型
//1.普通版本，類内自行指定
template<class I>
struct iterator_traits{
typedef typename I::iterator_category iterator_category;
};
//2.原生指針版本，原生指針是一種Random
template<class I>
struct iterator_traits<T*>{
typedef random_access_iterator_tag iterator_category;
};
//3.原生const指針版本，原生cosnt指針是一種Random
template<class I>
struct iterator_traits<const T*>{
typedef random_access_iterator_tag iterator_category;
};
std::iterator的保證
iterator源代碼完整重列
見p101
注意：
SGI STL的私房菜 __type_traits
萃取什麼：型别的特性，即這個型别是否有預設構造，預設析構，預設拷貝構造/操作符
差別：iterator_traits負責萃取疊代器的特性，__type_traits則負責萃取型别的特性。
SGI STL一般化：
偏特化：
應用：和疊代器型别差不多，擷取五個屬性中的一個，然後true和false臨時變量調用不同的重載函數