迭代器對於任何自定義的類序列都是一個強大的附加工具。它允許我們將演算法運用到有自定義類元素的容器上。可能會出現一種情形，沒有可以滿足我們需要的標準 STL 容器，這時候就需要定義一個自己的容器。我們的容器類可能需要疊代器。通過深入理解什麼樣的類(定義了疊代器)才能被 STL 所接受，可以讓我們了解到 STL 內部發生了些什麼。
STL疊代器的要求
STL 對定義了疊代器的類型別有一些特定的要求。這是為了保證所有接受這種疊代器的演算法都可以正常工作。演算法不需要知道，也不在乎它所處理的元素來自何種容器，但是它們在意傳給它們作為引數的迭代器的特性。不同的演算法要求不同功能的疊代器。我們在前面章節看到過這幾類疊代器：輸入疊代器、輸出疊代器、前向疊代器、雙向疊代器和隨機存取疊代器。我們總是可以在需要低階別疊代器的地方使用高階別疊代器。
定義演算法的模板需要決定可傳入疊代器的類別，用來驗證所傳入的疊代器的功能是否足夠。知道疊代器引數的類別能為演算法的應用提供潛在的優勢，可以充分利用任何最少的額外功能讓演算法更加高效。
一般來說，必須用標準的方式確認疊代器的功能。不同類別的疊代器意味著需要為疊代器類定義不同的成員函數集。我們知道，疊代器類別具有功能疊加性，這當然也會反映到每種類別的成員函數集上。在探討這些之前，先介紹一下函數模板如何使用疊代器。
使用 STL 疊代器存在的問題
定義一個引數中有疊代器的函數模板會產生一個問題，我們並不總是知道在函數模板中要用到哪些型別的疊代器。思考下面用疊代器作為引數的交換函數；模板型別引數指定了疊代器型別：
template <typename Iter> void my_swap(Iter a, Iter b)
{
tmp = *a;//error -- variable tmp undeclared
*a = *b;
*b = tmp;
}
函數模板的範例用來交換迭代器引數所指向的兩個物件：a 和 b。dmp 應該是什麼型別我們沒法知道，我們知道疊代器指向物件的型別卻無計可施，因為直到類別範本生成範例時，才能確定物件的型別。在不知道物件的型別時，如何定義變數？當然，這裡可以使用 auto。在一些情況下，我們也想知道疊代器型別的值和型別差別。
有些其他的機制可以確定一個疊代器引數所指向值的型別。一種是，堅持要求每個使用 my_swap() 的疊代器都應該包含一個公共定義的型別別名，因為這樣就可以確定迭代器所指向物件的型別。既然這樣，就可以在疊代器類中使用 value_type 的別名來指定函數模板 my_swap() 中 tmp 的型別，如下所示：
template <typename Iter> void my_swap(Iter a, Iter b)
{
typename Iter::value—type tmp = *a;
*a = *b;
*b = tmp;
}
因為 value_type 的別名定義在 Iter 類中，所以可以通過用類名限定 value_type 的方式參照它。這樣定義了 value_type 別名的疊代器類就能在函數中正常使用。然而，演算法既使用指標，也使用疊代器；如果 Iter 是普通型別的指標，例如 int*，甚至是 Box*，而 Box 是型別一這樣可能就無法使用了。因為指標不是類，不能包含定義的別名，所以不能寫成 int*::value_type 或 Box*::value_type。STL 用模板優雅地解決了這個問題和其他一些相關問題！
走進 STL
模板型別 iterator_traits 定義在標頭檔案 iterator 中。這個模板為疊代器的型別特性定義了一套標準的型別別名，讓演算法既可以用疊代器，也可以用一般的指標。iterator_traits 模板的定義如下所示：
template<class Iterator>
struct iterator_traits
{
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::iterator_category iterator_category;
}；
相信你肯定記得，結構體和類在本質上是相同的，除了結構體的成員預設是 public，這個結構體模板中沒有成員變數和成員函數。iterator_traits 模板的主體只包含型別別名的定義。這些別名以 Iterator 作為型別引數的模板。它在模板的型別別名——difference_type、value_type 等，以及用來生成疊代器模板範例的型別，與對應 Iterator 的型別引數之間定義了對映。
因此，對於一個實體類 Boggle，iterator_traits<Boggle> 範例定義 difference_type 作為 Boggle::difference_type 的別名，定義 value_type 作為 Boggle::value_type 的別名，等等。
這幫我們有效地解決了不知道模板定義中型別是什麼的問題。首先，假設定義了一個疊代器型別 MyItemtor，它包含具有下列型別別名的定義：
-
difference_type：兩個 MyIterator 型別的疊代器之間差別值的型別。
-
value_type：MyIterator 型別的疊代器所指向值的型別。
-
pointer：Mylterator 型別的疊代器所表示的指標型別。
-
reference：來自於 *MyIterator 的參照型別。
-
iterator_category：前面介紹的疊代器類別的標籤類型別：它們是 input_iterator_tag、output_iterator_tag、forward_iterator_tag、bidirectional_iterator_tag、random_access_iterator_tag。
一個滿足 STL 要求的疊代器類必須全部定義這些別名。但是對於輸出疊代器，除了 iterator_category，所有的別名都可以定義為 void。這是因為輸出疊代器指向物件的目的地址而不是物件。這套疊代器提供了我們所想知道的關於迭代器的一切。
當以疊代器為引數定義函數模板時，可以在模板中使用 iterator_traits 模板定義的標準型別別名。因此型別 MyIterator 的疊代器代表的指標型別總是可以作為 std::iterator_traits<MyIterator>:: pointer 參照，因為它等同於 MyIterator::pointer。當需要指定一個 MyIterator 疊代器所指向值的型別時，可以寫作 std::iterator_traits<MyIterator>::value_type，這將會被對映為 Mylterator::value_ type。我們用 my_swap() 模板中的 iterator_traits 模板型別別名來指定 tmp 的型別，例如：
template <typename Iter>
void my_swap(Iter a, Iter b)
{
typename std::iterator_traits<Iter>::value_type tmp = *a;
*a = *b;
*b = tmp;
}
上述程式碼將 tmp 的型別指定為 iterator_traits 模板中的 value_type 別名。當用 Iter 模板引數範例化 my_swap() 模板時，tmp 的型別變為疊代器所指向的型別 Iter::value_type。
為了說清楚發生了什麼，以及是如何解決這個問題的，讓我們考慮一個 my_swap() 模板範例的具體情況。假設一個程式包含下面的程式碼：
std::vector<std::string> words {"one", "two", "three"};
my_swap(std::begin(words), std::begin(words)+1); //Swap first two elements
當編譯器遇到 my_swap() 呼叫時，它會生成一個基於呼叫引數的函數模板範例。模板型別的疊代器是 iterator<std::string>。在 my_swap() 模板的主體中，編譯器不得不處理 tmp 的定義，編譯器知道模板的型別引數是 iterator<std::string>，因此在向模板新增了這個型別後，tmp 的定義變為：
typename std::iterator_traits<iterator<std::string> >::value_type tmp = *a;
tmp 的型別現在是一個 iterator_traits 模板範例的成員變數。為了弄清楚這意味著什麼，編譯器需要使用 my_swap() 函數中用來指定 tmp 型別的型別引數來範例化 iterator_traits 模板。下面是一個編譯器將會生成的 iterator_traits 模板範例：
struct iterator—traits
{
typedef typename iterator<std::string>::difference_type difference_type;
typedef typename iterator<std::string>::value_type value_type;
typedef typename iterator<std::string>::pointer pointer;
typedef typename iterator<std::string>::reference reference;
typedef typename iterator<std:: string>:: iterator_category iterator_category;
}；
從這裡編譯器可以確定 tmp 的型別為 iterator_traits<iterator<std::string>>::value_type，然而它也是 iterator<std::string>::value_type 的別名。就像所有的 STL 疊代器型別，iterator<std::string> 型別的定義是從 iterator 模板中生成的，並且會包含 value_type 的定義， 看起來像下面這樣：
typedef std::string value_type;
現在編譯器從 iterator_traits 範例中知道 itemtor_traits<itemtor<std::string>>::value_type 是 iterator<std::string>::value_type 的別名，並且從 itemtor<std::string> 類定義中知道 iterator<std::string>:: value_type 是 std::string 的別名。通過將別名轉換為真實型別，編譯器推斷出 my_swap() 函數中 tmp 的定義是：
std::string tmp = *a;
有必要提醒自己模板不是程式碼一它是編譯器用來生成程式碼的配方。iterator_traits 模板只包含型別別名，因此不會產生可執行程式碼。編譯器在生成 C++ 程式碼的過程中，會用到它。被編譯的程式碼中將不會有 iterator_traits 模板的蹤跡；它的唯一用武之地是在生成 C++ 程式碼的過程中。
這裡仍然遺留了一些有關指標的問題。iterator_traits 如何讓演算法像接受疊代器一樣接受指標。iterator_traits 模板特化了型別 T* 和 const T* 的定義。例如，當模板型別引數是指標型別 T* 時，特化被定義為：
template<class T>
struct iterator_traits<T*>
{
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef random_access_iterator_tag iterator_category;
}；
當模板型別引數是指標型別時，這定義了對應於別名的型別。T* 型別的指標 value_type 的別名總是為 T；如果將 Box* 型別的指標作為 my_swap() 的引數，那麼 value_type 的別名是 Box，因此 tmp 也為這種型別。
隨機存取疊代器類別所要求的全部操作都可以運用到指標上。因此對於指標，iterator_categor 的別名總是等同於 std::random_access_iterator_tag 型別。因而 iterators_traits 能否正常工作取決於模板型別引數是指標還是疊代器類型別。當模板型別引數是指標時，會選擇使用 iterators_traits 針對指標的特例化模板；否則選擇標準的模板定義。
使用疊代器模板
STL 定義了疊代器模板，用來幫助我們在自己的疊代器類中包含要求的型別別名。 iterator 是一個結構體模板，它定義了 5 個來自於 iterator_traits 模板的型別別名：
template<class Category, class T, class Difference = ptrdiff_t, class Pointer =T*,class Reference = T&> struct iterator
{
typedef T value_type;
typedef Difference difference_type;
typedef Pointer pointer;
typedef Reference reference;
typedef Category iterator_category
}；
這個模板定義了 STL 對疊代器所要求的全部型別。例如，如果有一個未知型別的模板引數 Iter，當需要宣告一個指標時，它指向一個疊代器解除參照時提供的型別，這時可以寫作 Iter::pointer。 iterator_category 的值必定是在前面章節介紹的類別標籤類中的一個。
當定義一個表示疊代器的類時，可以使用以疊代器模板為基礎類別生成的範例，這樣會新增類需要的型別別名。例如：
class My_Iterator : public std::iterator<std::random_access_iterator_tag,int>
{
// Members of the iterator class...
}；
還需要注意，需要為疊代器定義 STL 要求的全部型別。模板的第 1 個引數指定了作為完全隨機存取疊代器的疊代器型別。第 2 個引數是疊代器所指向物件的型別。最後的 3 個引數是預設值，因此第 3 個引數和這兩個疊代器的型別不同，是 ptrdiff_t。第 4 個引數是一個指向物件的指標型別，因此是 int*。最後一個模板引數指定了參照的型別，是 int&。當然，疊代器型別不做任何事，仍然需要定義類的全部成員。
STL疊代器成員函數的要求
STL 定義了一套需要疊代器型別支援並且依賴疊代器類別的成員函數。如果把它們編成組，顯然很有用。第一組需要全部疊代器和一些所有疊代器類都需要的重要函數：預設建構函式、拷貝建構函式以及賦值運算子。根據經驗，如果為疊代器類定義了其中任意一個函數，就需要定義一個顯式的解構函式。該組中型別疊代器的全套函數是：
Iterator(); // Default constructor
Iterator (const Iterator& y) ; // Copy constructor
~Iterator (); // Destructor
Iterator& operator= (const Iterator& y) ;// Assignment operator
對於隨機存取疊代器類，STL 需要一整套的關係運算子。事實上，可以通過使用 utility 標準庫標頭檔案中的函數模板來完成這些定義：
bool operator==(const Iterator& y) const;
bool operator<(const Iterator& y) const;
下面假定已經直接 #include 標頭檔案 utility，並且直接使用名稱空間 std::relops：
#include <utility>
using namespace std::rel_ops;
如果為類定義了 operator=() 和 operator<()，然後 std 中宣告的名稱空間 rel_ops 在必要時，就可以包含我們為 !=、>、>= 和 <= 生成的運算子函數的函數模板。因此直接用 using 啟用 std::rel_ops，就可以顯式儲存這 4 個運算子函數。如果定義一個運算子函數，但是它已經被名稱空間 std::rd_ops 模板生成，那麼我們的實現的優先順序高於模板生成的實現。函數 operator() 比較特別，叫作順序關係，它對搜尋和比較演算法很重要。
函數 operator==() 可以檢驗兩個容器物件的內容是否相同。這是一個有趣的方面，對於任意一對運算元 x 和 y，表示式 (x<y || y<x || x==y) 總為真，因為這個表示式的三部分中總有一部分為真。
事實上，不需要那樣做，如果 x==y 為真，那麼 x<y 和 y<x 都不可能為真。唯一可以確定的是兩個相等元素沒有什麼不同。然而，如果 x!=y，就無法斷定中的哪個為真。當表示式 (!(x<y)) &&(!(y<x)) 為真時，就可以說 x 和 y 不相等，也就意味著在排序時沒有偏向。這種情況的一個常見範例是對字串進行排序時，但是要忽略大小寫。如果以大小寫敏感為基準，字串 "A123" 和 "a123" 是不等價的(第一個字母不相同)，它們不相同，也不相等。
疊代器的其他操作由它的類別決定。可以在前面章節看到每種疊代器的特定操作，而且因為疊代器的累加特性，隨機存取疊代器可以支援全部操作。
讓我們在範例中看一個簡單迭代器型別的定義。我們定義一個類別範本，用來表示一段數值型別值，也可以生成指定範圍的開始和結束疊代器。這個疊代器也是模板型別，兩個模板都定義在同一個標頭檔案 Numeric_Range.h 中。下面是 Numeric_Range<T> 模板的定義：
template <typename T> class Numeric_Iterator; // Template type declaration
// Defines a numeric range
template<typename T>
class Numeric_Range
{
static_assert(std::is_integral<T>::value || std::is_floating_point<T>::value,
"Numeric_Range type argument must be numeric.");
friend class Numeric_Iterator < T >;
protected:
T start; // First value in the range
T step; // Increment between successive values
size_t count; // Number of values in the range
public:
Numeric_Range(T first=0, T incr=1, size_t n=2) : start {first}, step {incr}, count {n}{}
// Return the begin iterator for the range
Numeric_Iterator<T> begin(){ return Numeric_Iterator<T>(*this); }
// Return the end iterator for the range
Numeric_Iterator<T> end()
{
Numeric_Iterator<T> end_iter(*this);
end_iter.value = start + count*step; // End iterator value is one step over the last
return end_iter;
}
};
型別引數 T 是序列的值型別，因此它必定是數值型別。對於模板主體中的函數 static_assert()，當 T 不是整型也不是浮點型時，它的第一個引數會為 false，這時會生成一條包含第二個字串引數的編譯時錯誤訊息。這裡使用的斷言模板定義在標頭檔案 type_traits 中，模板中還有一些其他的編譯時模板型別引數檢查斷言。這個建構函式的三個引數都有預設值，因此它也可以作為無參建構函式。這三個引數分別用來初始化值、指定一個值到另一個值的增量，以及指定值的個數。因此預設定義了又有兩個值的元素段：0 和 1。編譯器會在需要時，提供適當的拷貝建構函式。
另有兩個成員函數生成，然後返回元素段的開始和結束疊代器。結束疊代器的成員變數 value 的值為最後一個 value+1。結束疊代器是通過修改開始疊代器的 value 生成的。Numeric_Itemtor<T>模板型別的宣告在其定義之前是必要的，因為還沒有定義疊代器型別模板。Numeric_Iterator<T> 模板被指定為這個模板的友元類，這樣 Numeric_Iterator<T> 的範例就可以存取Numeric_Range<T> 的私有成員。Numeric_Range<T> 模板也需要成為 Numeric_Iterator<T> 的友元類，因為 Numeric_Range<T> 的成員函數 end() 需要存取 Numeric_Iterator<T> 的一個私有成員。
這個疊代器的模板型別定義如下：
// Iterator class template- it's a forward iterator
template<typename T>
class Numeric_Iterator : public std::iterator < std::forward_iterator_tag, T >
{
friend class Numeric_Range < T >;
protected:
Numeric_Range<T>& range; // Reference to the range for this iterator
T value; // Value pointed to
public:
explicit Numeric_Iterator(Numeric_Range<T>& a_range) : range {a_range}, value {a_range.start} {};
// Assignment operator
Numeric_Iterator& operator=(const Numeric_Iterator& src)
{
range = src.range;
value = src.value;
}
// Dereference an iterator
T& operator*()
{
// When the value is one step more than the last, it's an end iterator
if (value == static_cast<T>(range.start + range.count*range.step))
{
throw std::logic_error("Cannot dereference an end iterator.");
}
return value;
}
// Prefix increment operator
Numeric_Iterator& operator++()
{
// When the value is one step more than the last, it's an end iterator
if (value == static_cast<T>(range.start + range.count*range.step))
{
throw std::logic_error("Cannot increment an end iterator.");
}
value += range.step; // Increment the value by the range step
return *this;
}
// Postfix increment operator
Numeric_Iterator operator++(int)
{
// When the value is one step more than the last, it's an end iterator
if (value == static_cast<T>(range.start + range.count*range.step))
{
throw std::logic_error("Cannot increment an end iterator.");
}
auto temp = *this;
value += range.step; // Increment the value by the range step
return temp; // The iterator before it's incremented
}
// Comparisons
bool operator<(const Numeric_Iterator& iter) const { return value < iter.value; }
bool operator==(const Numeric_Iterator& iter) const { return value == iter.value; }
bool operator!=(const Numeric_Iterator& iter) const { return value != iter.value; }
bool operator>(const Numeric_Iterator& iter) const { return value > iter.value; }
bool operator<=(const Numeric_Iterator& iter) const { *this < iter || *this == iter; }
bool operator>=(const Numeric_Iterator& iter) const { *this > iter || *this == iter; }
};
#endif
程式碼看起來雖多，卻很簡單直白。這個疊代器有一個成員變數，它儲存了一個和它相關聯的 Numeric_Range 物件的參照，另外還儲存了它所指向元素的值。疊代器的建構函式的引數是一個 Numeric_Range 物件的參照。建構函式用引數初始化成員變數 range，並將成員變數 value 的值設為 Numeric_Range 的 start。
還定義了一些解除參照運算子、字首或字尾自增運算子以及一套比較運算子。對元素段的結束疊代器的解除參照或自增都是非法的，因此如果運算元是結束疊代器，那麼自增運算子函數和解除參照運算子函數都會拋出異常；這表明成員變數 value 超出了元素段中的最後一個值。為了簡單，選擇拋出一個標準異常。
標頭檔案 Numeric_Range.h 的完整內容如下：
// Exercising the Numeric_Range template
#include <algorithm> // For copy()
#include <numeric> // For accumulate()
#include <iostream> // For standard streams
#include <vector> // For vector container
#include "Numeric_Range.h" // For Numeric_Range<T> & Numeric_Iterator<T>
int main()
{
Numeric_Range<double> range {1.5, 0.5, 5};
auto first = range.begin();
auto last = range.end();
std::copy(first, last, std::ostream_iterator<double>(std::cout, " "));
std::cout << "nSum = " << std::accumulate(std::begin(range), std::end(range), 0.0) << std::endl;
// Initializing a container from a Numeric_Range
Numeric_Range<long> numbers {15L, 4L, 10};
std::vector<long> data {std::begin(numbers), std::end(numbers)};
std::cout << "nValues in vector are:n";
std::copy(std::begin(data), std::end(data), std::ostream_iterator<long>(std::cout, " "));
std::cout << std::endl;
// List the values in a range
std::cout << "nThe values in the numbers range are:n";
for (auto n : numbers)
std::cout << n << " ";
std::cout << std::endl;
}
執行結果為：
1.5 2 2.5 3 3.5
Sum = 12.5
Values in vector are:
15 19 23 27 31 35 39 43 47 51
The values in the numbers range are:
15 19 23 27 31 35 39 43 47 51
生成的第一個 Numeric_Range 範例有 5 個 double 型元素，它們從 1.5 開始，每次增加 0.5。Numeric_Range 的疊代器用來在 copy() 演算法中將值複製到 ostream_iterator。這表明演算法可以接受這個疊代器。第二個 Numeric_Range 範例有 10 個 long 型元素。在 vector 容器的初始化列表中，使用開始和結束疊代器，然後用 copy() 演算法輸出 vector 中的元素。最後，為了演示它的工作原理，以 for 迴圈的方式輸出它的值。輸出表明 Numeric_Range 模板成功建立了整型和浮點型的元素段，我們成功定義了一個可以使用 STL 的疊代器型別。