?最常使用的5種迭代器的型別為 value_type、difference_type、pointer、reference、iterator_category。
如果想要自己開發的容器和STL進行適配，就需要定義上述5種類型?
iteraor_traits 必須針對傳入的型別為 pointer 或者 pointer-to-const設計偏特化版本

template <class I>
struct iteraor_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;
};

value_type

迭代器所指對象的型別?

difference_type

兩個迭代器之間的距離，表示容器的最大容量([begin,end))
例：STL 的count() 返回的數值就是迭代器的 difference type

template <class I>
struct iteraor_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;
};template <class I,class T>
typename iteraor_traits<I>::difference_type //這一整行限定的是函數的回返型別
count (I first,I last,const T& value){typename iteraor_traits<I>::difference_type n = 0;for (;first != last;++first) {if (*first == value){++n;}}return n;
}

針對相應型別differe type,traits 的如下兩個(針對原生指針而寫的)特化版本
使用C++內建的ptrdiff_t （定義在<cstddef>頭文件）作為原生指針的difference type

//針對原生指針設計的偏特化版本
template <class T>
struct iteraor_traits<T*>{typedef ptrdiff_t difference_type;
};//針對原生的pointer-to-const設計的偏特化版本
template <class T>
struct iteraor_traits<const T*>{typedef ptrdiff_t difference_type;
};

當我們需要的任何迭代器I的difference type，可以怎么寫 typename iterator_traits<I>::difference_type?

pointer

指針和引用之間的關系是非常密切的，傳回一個左值，令他代表所指之物，也可以令其代表所指之物的地址，即可以通過傳回一個指針，指向迭代器的所指之物

Item& operator*() const {return *ptr;}
Item* operator->() const {return ptr;}

//針對原生指針設計的偏特化版本
template <class T>
struct iteraor_traits<T*>{typedef T* pointer;typedef T& reference;
};//針對原生的pointer-to-const設計的偏特化版本
template <class T>
struct iteraor_traits<const T*>{typedef const T* pointer;typedef const T& reference;
};

reference

從迭代器所指之物的內容是否允許改變的角度出發，迭代器分為兩種：不允許改變所指對象的內容稱為const int*pic
允許改變所指之物的內容稱為mutable iterators ，例如int * pi；
對于mutable iterator進行提領操作的時候，得到的不是一個右值(右值不允許賦值操作)，應該是一個左值。

    int *pi = new int(5);const int* pci = new int(9);*pi = 7; //對mutable iterator進行提領操作的時候 得到的是左值，允許賦值*pci = 1; //這個操作是不允許的，pci是const iterator//提領pci得到的結果是一個 右值 不允許賦值

C++左值是通過reference的方式返回的
當p是mutable iterator時，其value type是T? 那么*p型別不應該是T 應該是T&
當p是constant iterator時，其value type是const T? 那么*p型別不應該是const T 應該是const T&

iterator_category

//針對原生指針設計 偏特化版本
template <class T>
struct iteraor_traits<T*>{//注意 原生指針是一種Random access iteratortypedef random_access_iterator_tag iterator_category;
};//針對原生指針 pointer-to-const 設計 偏特化版本
template <class T>
struct iteraor_traits<const T*>{//注意 原生指針pointer-to-const 是一種Random access iteratortypedef random_access_iterator_tag iterator_category;
};

迭代器的分類( 根據移動特性和施行操作?)

Input iterator :不允許外界改變只讀
output iterator：唯寫
forward iterator：允許寫入型算法 (例如 replace() ) 在這種迭代器形成的區間上進行讀寫操作
bidirectional iterator : 可以雙向移動，可以逆向訪問迭代器的區間(例如逆向拷貝某個范圍內的元素)
random access iterator : 前四種僅僅具備一部分指針算數的能力(前三種支持operator++，第四種需要加上operator--)；第五種需要涵蓋所有的只針的算數的能力，比如p+n p-n? p[n]? p1-p2 p1<p2

直線和箭頭并不代表繼承的關系，而是所謂的概念和強化的關系
例子使用advance函數舉例，這個函數有兩個參數，迭代器p和數值n，函數需要實現迭代器p累計前進n次
3個例子：input iterator、bidirectional? iterator 、random access iterator
倒是沒有針對forwarditerator設計的版本，因為這個和 inputiterator而設計的版本完全一致

template <class InputIterator,class Distance>
void advance_II(InputIterator& i,Distance n){//單向 逐一前進while (n--)++i;
}template <class BidirectionalIterator,class Distance>
void advance_BI(BidirectionalIterator& i,Distance n){//雙向 逐一前進if(n >= 0){while (n--){++i;}} else{while (n++){--i;}}
}template <class RandomAccessIterator,class Distance>
void advance_RAI(RandomAccessIterator&i ,Distance n){//雙向 跳躍前進i += n;
}

?程序調用advance()的時候具體使用哪一個函數定義呢？如果選擇advance_II（）對于randomaccess iterator而言缺乏效率，O(1)操作變成了O(N)操作
如果是advance_RAI（）則無法接受 Input Iterator? 需要對上述三個函數進行合并

template <class InputIterator,class Distance>
void advance(InputIterator& i,Distance n){if (is_random_access_iterator(i)){advance_RAI(i,n);} else if (is_bidiractional_iterator(i)){advance_BI(i,n);} else{advance_II(i,n);}
}

在執行期間決定使用哪一個版本，會影響程序的執行的效率，最好在編譯期間就確定程序執行的正確的版本，因此使用函數的重載是最好的方式

struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag       : public input_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};

上述這些classes只能作為標記使用，不需要任何成員
加上第三個參數，讓他們之間形成重載的關系

template <class InputIterator,class Distance>
void __advance(InputIterator& i,Distance n,input_iterator_tag){//單向 逐一前進while (n--)++i;
}//這是一個單純的傳遞調用的函數(trivial forwarding function)
template <class ForwardIterator,class Distance>
inline void __advance(ForwardIterator&i, Distance n,forward_iterator_tag){//單純的進行傳遞調用 (forwarding)advance(i,n,input_iterator_tag());
}template <class BidirectionalIterator,class Distance>
void advance_BI(BidirectionalIterator& i,Distance n,bidirectional_iterator_tag){//雙向 逐一前進if(n >= 0){while (n--){++i;}} else{while (n++){--i;}}
}template <class RandomAccessIterator,class Distance>
void advance_RAI(RandomAccessIterator&i ,Distance n,random_access_iterator_tag){//雙向 跳躍前進i += n;
}

__advance()的第三個參數只聲明了型別，但是并沒有指定參數的名稱，其主要的目的是為了激活重載機制，函數中根本不使用這個參數
還需要一個對外開放的上層控制接口，調用上述的各自重載的__advance() ，這一層只需要兩個參數，當其準備將工作轉移給上述的_advance()時才會自行加上第三個參數：迭代器的類型。
使用traits機制從所獲得的迭代器中推導出其類型

template <class I>
struct iteraor_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;
};template <class InputIterator,class Distance>
inline void advance(InputIterator&i, Distance n){__advance(i,n,iteraor_traits<InputIterator>::iterator_category());
}

iteraor_traits<InputIterator>::iterator_category() 將產生一個暫時對象，就像int() 產生一個int暫時對象一樣。
這個臨時對象的型別應該隸屬于前面所述的5個迭代器之一，然后根據這個迭代器的型別，編譯器才決定調用哪一個_advance()重載函數

?注意事項

迭代器其類型隸屬于各個適配類型中最強化的那個。例如int* 既是random 、bidirectional、forward、input，那么其類型應該從屬為random_access_iterator_tag
但是迭代器的參數需要按照最低階的類型為其命名，比如advance（）函數，使用最低級的inputIterator為其命名

消除 “單純傳遞調用的函數”

使用class定義迭代器的各種分類標簽，不僅可以促進重載機制的成功運作，使得編譯器得以正確執行重載決議，overloaded resolution
還可以通過繼承不比再寫 "單純只做傳遞調用"的函數，即advance不需要寫 Forwarditerator這個版本

仿真測試tag types繼承關系所帶來的影響

?例子：使用distance舉例子計算兩個迭代器之間的距離

distance可以接受任何類型的迭代器，但是template型別參數設置為InputIterator，是為了遵循STL算法的命名規則，使用最低級的迭代器命名
考慮到繼承關系，當客戶端調用distance()函數輸入的參數型別是 Output iterators、Bidirectional Iterators、ForwardIterator時，統統都會轉化為Input Iterator版_distance函數
即存在繼承關系的模型，僅僅實現首和尾即可，中間版本都會被隱式轉化為首，尾巴調用專屬的函數即可

?std::iterator 保證

規范需要任何的迭代器都需要實現上述的五個內嵌的型別，從而方便traits進行類型的萃取，否則無法適配 STL的組件
STL提供了iterator class，新設計的迭代器需要繼承自它，它不包含任何的成員，只是進行了型別的定義，因此繼承它不會導致額外的負擔

#include <memory>struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag : public input_iterator_tag{};
struct bidirectional_iterator_tag : public forward_iterator_tag{};
struct random_access_iterator_tag : public bidirectional_iterator_tag{};//自行開發的迭代器需要繼承 std::iterator
template <class Category,class T,class Distance = ptrdiff_t,class Pointer = T*,class Reference = T&>
struct iterator{typedef Category    iterator_category;typedef T           value_type;typedef Distance    difference_type;typedef Pointer     pointer;typedef Reference   reference;
};//traits
template <class Iterator>
struct iterator_traits{typedef typename Iterator::iterator_category iterator_category;typedef typename Iterator::value_type value_type;typedef typename Iterator::difference_type difference_type;typedef typename Iterator::Pointer pointer;typedef typename Iterator::reference reference;
};//針對原生指針(native pointer)設計traits偏特化版本
template <class T>
struct iterator_traits<T*>{typedef random_access_iterator_tag iterator_category;typedef T                          value_type;typedef ptrdiff_t                  difference_type;typedef T*                         pointer;typedef T&                         reference;
};//針對原生指針(pointer-to-const)設計的traits偏特化版本
template <class T>
struct iterator_traits<const T*>{typedef random_access_iterator_tag iterator_category;typedef T                          value_type;typedef ptrdiff_t                  difference_type;typedef T*                         pointer;typedef T&                         reference;
};//函數的目的是為了 方便的決定某個迭代器的類型 (category)
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&){typedef typename iterator_traits<Iterator>::iterator_category category;return category();
}//函數的目的是為了 方便的決定某個迭代器的類型 distance type
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type *
distance_type(const Iterator&){return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}//函數的目的是為了 方便的決定某個迭代器的類型 value type
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type  *
value_type(const Iterator&){return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}//整組的distance函數
template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
__distance(InputIterator first,InputIterator last,input_iterator_tag){typename iterator_traits<InputIterator>::difference_type n = 0;while (first != last){++first;++n;}return n;
}template <class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type 
__distance(RandomAccessIterator first,RandomAccessIterator last,random_access_iterator_tag){return (last - first);
}template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first,InputIterator last){typedef typename iterator_traits<InputIterator>::iterator_category category;return (__distance(first,last,category()));
}//以下是整組的advance函數
template <class InputIterator,class Distance>
inline void __advance(InputIterator& i,Distance n,input_iterator_tag){while (n--){++i;}
}template <class BidirectionalIterator,class Distance>
inline void __advance(BidirectionalIterator&i,Distance n,bidirectional_iterator_tag){if (n>=0){while (n--) ++i;} else{while (n++) --i;}
}template <class RandomAccessIterator,class Distance>
inline void __advance(RandomAccessIterator& i,Distance n,random_access_iterator_tag){i+=n;
}template<class InputIterator,class Distance>
inline void advance(InputIterator& i,Distance n){__advance(i,n,iterator_category(i));
}