迭代器

迭代器類似于指針類型，也提供了對對象的間接訪問。
就迭代器而言，其對象是容器中的元素或 string 對象中的字符。

獲取迭代器

容器的迭代器類型

使用作用域運算符來說明我們希望使用的類型成員；例：string::iterator iter;

類型別名	功能
iterator	此容器類型的迭代器
const_iterator	可以讀取元素，但不能修改元素的迭代器類型
diffreence_type	帶符號整數類型，足夠保存兩個迭代器之間的距離
reverse_iterator	按逆序尋址元素的迭代器
const_reverse_iterator	不允許修改元素的逆迭代器

begin 和 end 成員

和指針不同的是，獲取迭代器不適用取地址運算符，有迭代器的類型，同時擁有返回迭代器
的成員函數。
成員函數 begin 生成指向容器中的第一個元素的迭代器。
成員函數 end 生成指向容器中的尾元素之后位置的迭代器（簡稱尾后迭代器）。

/*獲取迭代器，使用 auto 推斷迭代器的類型*/string str{ "Hello World" };auto iter_b = str.begin(); auto iter_e = str.end();

begin 和 end 有多個版本：帶 r 的版本返回反向迭代器，以 c 開頭的版本則返回 const 迭代器。
可以將一個普通的 iterator 轉換為對應的 const_iterator，但反之不行。
以 c 開頭的版本是C++新標準引入的，用以支持 auto 與 begin 和 end 函數結合使用。

迭代器運算

解引用

可以通過解引用迭代器來獲取它所指向的元素。

	string str{ "Hello World" };auto iter = str.begin();cout << *iter << endl; //輸出 H 

試圖解引用一個非法的迭代器或者尾后迭代器結果都是未定義的。

算數運算

迭代器加上或減去整數

迭代器加上（或減去）一個整數值扔得一個迭代器，迭代器指示的新位置與原來相比向前移動了若干個元素。

	string str{ "Hello World" };auto iter = str.begin();iter = iter + 4;cout << *iter << endl;       // 輸出 ocout << *(iter - 3) << endl; // 輸出 e

迭代器支持加法（或減法）的復合賦值語句

	string str{ "Hello World" };auto iter = str.begin();iter +=  4;cout << *iter << endl; // 輸出 oiter -= 3;cout << *iter << endl; // 輸出 e

迭代器支持遞增（或遞減運算符），表示迭代器指向下一個元素。

	string str{ "Hello World" };auto iter = str.begin();/* 將迭代器向前移動一個元素,然后輸出移動后的值 */ cout << *++iter << endl;  // 輸出 e/* 將迭代器向后移動一個元素,然后輸出移動后的值 */ cout << *--iter << endl;  // 輸出 H

兩個迭代器可以相減

如果兩個迭代器指向同一個容器，則兩個迭代器相減的結果是它們之間的距離。

	string str{ "Hello World" };auto iter = str.begin();auto iter_b = iter + 1;auto iter_e = iter + 4;cout << (iter_e - iter_b) << endl; //輸出 3

兩個迭代器可以比較

如果兩個迭代器指向同一個容器，則可以進行比較；指向前面元素的迭代器小于指向后面元素的迭代器。

	string str{ "Hello World" };auto iter = str.begin();auto iter_b = iter + 1;auto iter_e = iter +  4;cout << (iter_b  < iter_e) << endl; //輸出 1

如果兩個迭代器相等，則兩個迭代器指向同一個元素，或者它們是同一個容器的尾后迭代器。

使用迭代器遍歷容器

	string str{ "Hello World" };auto it_c = str.cbegin();for (auto iter = str.begin(); iter < it_c + str.size(); iter += 1){cout << *iter;}

迭代器范圍

一個迭代器范圍（iterator range）由一對迭代器表示，兩個迭代器分別指向同一個容器中的元素或者尾元素之后的位置（one past the last element）。
迭代器范圍也被稱為左閉合區間（left-inclusive interval），其標準數學描述為：[begin end)
標準庫使用左閉合范圍是因為這種范圍有三種方便的性質。
假定 begin 和 end 構成一個合法的迭代器范圍，則

• 如果 begin 和 end 相等，則范圍為空。
• 如果 begin 和end 不相等，則范圍至少包含一個元素，且 begin 指向該范圍中的第一個元素。
• 我們可以對 begin 遞增若干次，使得begin == end。

使用迭代器遍歷容器

	string str{ "Hello World" };auto iter = str.begin();while ( iter != str.cend() ){cout << *iter++;}

再探迭代器

除了為每個容器定義的迭代器之外，標準庫在頭文件<iterator>中還定義額外幾種迭代器。這些迭代器包括以下幾種：

• 插入迭代器（insert iterator）：這些迭代器被綁定到一個容器上，可用來向容器插入元素。
• 流迭代器（stream iterator）：這些迭代器被綁定到輸入或輸出流上，可用來遍歷所關聯的IO流。
• 反向迭代器（reverse iterator）：這些迭代器向后而不是向前移動。除了 forward_list 之外的標準庫容器都有反向迭代器。
• 移動迭代器（move iterator）：這些專用的迭代器不是拷貝其中的元素，而是移動它們。

插入迭代器

插入迭代器是一種迭代器適配器，它接受一個容器，生成一個迭代器，能實現向給定容器添加元素。當我們通過一個插入迭代器進行賦值時，該迭代器調用容器操作來給定容器的指定位置插入一個元素。
插入迭代器有三種類型，差異在于元素插入的位置：
back_inserter 創建一個使用 push_back 的迭代器。

	deque <char> D{ 'F','G','H' };auto it = back_inserter(D);/*尾后插入字母 A B C D E */for (char i = 'A'; i < 'F'; ++i){*it = i; //等價于 D.push_back( i );}
/* 隊列內的元素變為：F G H A B C D E */

front_inserter 創建一個使用 push_front 的迭代器。

	deque <char> D{ 'F','G','H' };auto it = front_inserter(D);/*首前插入字母 A B C D E */for (char i = 'A'; i < 'F'; ++i){*it = i; //等價于 D.push_front( i );}
/* 隊列內的元素變為：E D C B A F G H */

inserter 創建一個使用 insert 的迭代器。此函數接受第二個參數，這個參數必須是一個指向給定容器的迭代器；元素被插入到給定迭代器所表示的元素之前。

	deque <char> D{ 'F','G','H' };auto it = inserter ( D ,D.begin() );for (char i = 'A'; i < 'F'; ++i){*it = i; //等價于 it = D.insert(it,i); ++it; 其中，it = D.begin();}
/* 隊列內的元素變為：A B C D E F G H */

iostream 迭代器

雖然 iostream 類型不是容器，但標準庫定義了可以用于這些 IO 類型對象的迭代器。
當創建一個流迭代器時，必須指定迭代器將要讀寫的對象類型。
istream_iterator 讀取輸入流

	deque <char> D;/*in_iter從輸入流 cin 讀取類型為 char 的值*/istream_iterator <char> in_iter( cin ); istream_iterator <char> eof; //尾后迭代器while (in_iter != eof){D.push_back( *in_iter++ ); //返回從流中讀取的值，然后從流中讀取下一個值}

ostream_iterator 向一個輸出流寫數據
我們可以提供一個（可選的）第二參數，它是一個字符串字面值，在輸出每個元素后都會打印此字符串。

	deque <char> D{ 'A','B','C','D','E' };ostream_iterator <char> out_iter (cout, " ");for (auto i : D)out_iter = i; //等價于cout << i << ' ';

反向迭代器

反向迭代器就是在容器中從尾元素反向移動的迭代器。
除了 forward_list 之外，其它容器都支持反向迭代器。
成員函數 rbegin 返回指向容器尾元素的迭代器。
成員函數 rend 返回指向容器首元素之前位置的迭代器。
反向迭代器迭代器也有 const 版本，即 crbegin 和 crend。

使用反向迭代器逆序遍歷容器

	deque <char> D{ 'A','B','C','D','E' };auto it = D.crbegin();while (it != D.crend()){cout << *it++ << ' ';}

泛型算法結構

任何算法的最基本的特征是它要求其迭代器提供哪些操作。
算法所要求的迭代器操作可以分為 5 個迭代器類別：

迭代器類別	特點
輸入迭代器	只讀，不寫；單遍掃描，只能遞增
輸出迭代器	只寫，不讀；單遍掃描，只能遞增
前向迭代器	可讀寫；多遍掃描，只能遞增
雙向迭代器	可讀寫；多遍掃描，可遞增遞減
隨機訪問迭代器	可讀寫；多遍掃描，支持全部迭代器運算