本文的技術可以參考本博客: Traits 技術 --- 模板元編程 (轉)
迭代器可以區分為不同的類型，每個類型都有特定的迭代器功能。
根據迭代器類型，將算法根據類型的不同實現出更加有效率的版本，將會很有用，也很必要！
透過迭代器標志(tags)和迭代器特性(traits,由<iterator>提供)可以實現這樣的重載.
STL為每種迭代器都提供了一個迭代器標志(iterator tags),用來作為迭代器的標簽(label)
namespace
{
struct output_iterator_tag
{
};
struct input_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
{
};
}
-------------------------------------------------------------------------------------------
五種迭代器類別
首先，引進迭代器是為了在算法與容器之間隔開，可以讓兩者獨立發展。這樣勢必要求迭代器需要像算法展現統一的接口，也就是說，從算法的角度出發，迭代器的功能接口是一樣的，算法無法直接看到容器的，而是通過迭代器簡介管理操作容器，這樣可以推到出：算法眼里容器都是一樣的。而顯然這并不合理。
因為，即使各種容器有統一的基本特性——“聚集”同一類型的數據元素。但是由于不同的容器聚集的方式不同，導致表現出來的許多功能特性不同。（例如vector，deque表現可以很好的支持random access性質，但是你叫list也支持這個，這將是非常不明智的）。所以，即使我們盡量希望向外部展現一個統一的容器接口（迭代器），我們仍然需要區分對待，我們在迭代器上區分對待，就可以充分發揮各種容器的個性特點。算法也可以根據相應的不同，優化對待不同的容器。這就是出現不同的類型容器的原因。
Iterator Category | Ability | Providers |
Input iterator | Reads forward | istream |
Output iterator | Writes forward | ostream, inserter |
Forward iterator | Reads and writes forward | |
Bidirectional iterator | Reads and writes forward and backward | list, set, multiset, map, multimap |
Random access iterator | Reads and writes with random access | vector, deque string, array |
可以看到，不同類別的迭代器，所能支持的功能是不同的，定義容器的選擇定義哪個類別的應不同的容器特性而定。在設計算法的時候，算法會通過類型萃取獲得該迭代器的類別。并根據不同的類別視機做特定的算法實現優化。
Input iterator
Operations of Input Iterators |
Expression | Effect |
*iter | Provides read access to the actual element |
iter ->member | Provides read access to a member (if any) of the actual element |
++iter | Steps forward (returns new position) |
iter++ | Steps forward (returns old position) |
Iter1 == iter2 | Returns whether two iterators are equal |
Iter1 != iter2 | Returns whether two iterators are not equal |
TYPE(iter) | Copies iterator (copy constructor) |
這個迭代器用于，從容器中依次讀取數據（只讀，并且只能前進）。但是還有一個會讓你匪夷所思的特性是，這種迭代器不能重復讀某個元素兩次。這是一個很奇怪但是有很合理的規定，最常見的需要用輸入迭代器的就是標準輸入口，不管有幾個迭代器指向這個標準輸入口，語義上不容許同一個元素被讀兩次。但是，我們奇怪的是，這個意思的就是說，讀動作是與迭代器相前進一步的動作是一起發生的，那么這種迭代器就不需要向前進一步的功能的必要了，但這里提供了。
事實上我認為，上面的要求只是一種語義上的要求。告訴你，如果你在某個容器定義迭代器的時候選擇了輸入迭代器，那么這個迭代器所應該提供的功能模式應該需要保持“不容許同一個元素被讀兩次”，我們知道STL對各種類別的區別只是用tags來區別的。語法上沒有寫死語義上的“建議”。
還有一個原因是，下面有幾種迭代器，是以這種迭代器為基礎的，所以如果你不提供這種基本的操作（向前去！），那他們如何提供。
Output iterator
Operations of Output Iterators |
Expression | Effect |
*iter = value | Writes value to where the iterator refers |
++iter | Steps forward (returns new position) |
iter++ | Steps forward (returns old position) |
TYPE (iter) | Copies iterator (copy constructor) |
與input iterator 想對應的就是output iterator，他們有很多相似點，并且，也有與前面類似的奇怪規定，這導致兩個指向同一個容器的寫迭代器，寫的過程不會出現覆蓋寫。其中一個有名的例子就是屏幕輸出。并且，你會發現寫迭代器沒有比較操作（讀模式中就有）。這是因為寫的時候，是一直往外寫的，語義上以沒有終點限制的。有一個特殊的（也是我們將要介紹的）迭代器，就是inserter。
Forward iterator
Operations of Forward Iterators |
Expression | Effect |
*iter | Provides access to the actual element |
iter-> member | Provides access to a member of the actual element |
++iter | Steps forward (returns new position) |
iter++ | Steps forward (returns old position) |
iter1 == iter2 | Returns whether two iterators are equal |
iter1 != iter2 | Returns whether two iterators are not equal |
TYPE() | Creates iterator (default constructor) |
TYPE(iter) | Copies iterator (copy constructor) |
iter1 = iter2 | Assigns an iterator |
從iterator中表達的迭代器tags定義可以看出：
struct forward_iterator_tag : public input_iterator_tag {};
forward iterator 是以input iterator為基礎的。這就是給我們一個奇怪的錯覺。語義上forward只限制了向前，不限制讀寫，這樣forward iterator應該繼承input iterator和output iterator兩種。但是它只支持一種。
這里我們提出兩個原因：
首先，iterator中迭代器tags的規定只是語義上的規定，它對最終的具體實現沒有什么限制，（當然你不按照這種方式實現，那將是一個不道德的行為）。所以這種定義，從本質實現上并不能影響我們許多。
其次，權威的書籍中所闡述的原因是，output中，由于語義上不提供比較功能（這就表明不判斷是否越界）。所以forward不能全部繼承output的語義功能。
最后，我說一句，這里的規定始終都是語義上的規定，所以基本上，forward iterator繼承誰，都是一句屁話。這是標準，但是對于實際實現的程序員來說，這些東西都是屁。
Bidirectional iterator
Additional Operations of Bidirectional Iterators |
Expression | Effect |
-- iter | Steps backward (returns new position) |
iter-- | Steps backward (returns old position) |
可以看出，雙向迭代器只是在forward iterator上面加上一個向后一步的功能。我們事實上我們知道我們通常見到的迭代器都這種，以及后面一種Random iterator.
Random iterator
Additional Operations of Random Access Iterators |
Expression | Effect |
iter[n] | Provides access to the element that has index n |
iter+=n | Steps n elements forward (or backward, if n is negative) |
iter-=n | Steps n elements backward (or forward, if n is negative) |
iter+n | Returns the iterator of the nth next element |
n+iter | Returns the iterator of the nth next element |
iter-n | Returns the iterator of the nth previous element |
iter1-iter2 | Returns the distance between iter1 and iter2 |
iter1<iter2 | Returns whether iter1 is before iter2 |
iter1>iter2 | Returns whether iter1 is after iter2 |
iter1<=iter2 | Returns whether iter1 is not after iter2 |
iter1>=iter2 | Returns whether iter1 is not before iter2 |
可以看出，Random iterator的功能主要體現在，在forward iterator 的基礎上提供了隨機存儲的功能，這個功能連帶提供了迭代器算數功能（指針算數功能）以及比較功能。
-------------------------------------------------------------------------------------------
類型萃取器問題前面提到，類型萃取器用于給算法使用，同過它你可以得到有關你所操縱的迭代器的幾乎所有有用的相關類型。
namespace std {
template <class T>
struct iterator_traits {
typedef typename T::value_type value_type;
typedef typename T::difference_type difference_type;
typedef typename T::iterator_category iterator_category;
typedef typename T::pointer pointer;
typedef typename T::reference reference;
};
}
算法可以使用如下語句得到相關類型：
typename std::iterator_traits<T>::value_type
有些書上說，這種設置有兩種好處：
首先，它規定了每種迭代器在定義的時候都需要提供者幾種類型信息以供被使用，從某種角度上講，它提供一種定義迭代器有關相關屬性的標準。
為了強行對這一標準進行規定，在iterator頭文件中有一個結構(struct iterator)用于給用戶定義迭代器的時候繼承的（就是接口），但是這并非是語法規定。事實上，如果你如果能夠保證一定會提供traits結構中所需求的那些類型信息，不繼承這個也是可以的：
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;
};
事實上，對于我們系統自定義的那五種迭代器，我們使用的比較多的仍然是tags。但是系統為了用戶子定義迭代器方便，仍然按照各自的特點，給他們各自定義了類似于iterator的、用于管理traits所指明的類型信息。
例如，定義特定類別迭代器的時候繼承特定結構體，你就可以不同管trait規定的那些東西了。
template <class T, class Distance> struct input_iterator {
typedef input_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
struct output_iterator {
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};
template <class T, class Distance> struct forward_iterator {
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
template <class T, class Distance> struct bidirectional_iterator {
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
template <class T, class Distance> struct random_access_iterator {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
其次，它讓普通指針也被列為迭代器的一種。
namespace std {
template <class T>
struct iterator_traits<T*> {
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef random_access_iterator_tag iterator_category;
typedef T* pointer;
typedef T& reference;
};
}
如上面所說，通過模板偏特化技術，使得當算法獲得了普通指針作為迭代器的時候，需要同樣知道那些類型（事實上，這種情況下獲得還是比較簡單的，但是需要和普通迭代器進行統一，以實現泛型
為什么不使用常變量呢？指針沒辦法！所以traits技術最大的亮點就在于可以對traits類進行特化。