C++/STL/Iterator

iterator 是w:C++標準程式庫中的一個w:頭文件，定義了C++ STL標準中的一些w:迭代器模板類，這些類都是以std::iterator為基類派生出來的。

迭代器模擬了C++中的指針，可以有++運算，用*（解引用算符，deference）或->算符來訪問容器中的元素。容器中元素如果改變了所用內存，也不影響綁定的迭代器指向正確的位置。因此，迭代器實際上更像是句柄（handler）。

STL的迭代器實現了設計模式中的「w:迭代器模式」。即順序訪問一個聚合中的元素，又不暴露聚合的實現細節。

迭代器支持以不同方法遍歷聚合類型。例如，對一顆樹數據類型，可以有前序、中序、後序遍歷的迭代器。同一個聚合類型的對象上，可以同時有多個迭代器，各自保持不同的遍歷狀態。在不同的聚合類型上實現的迭代器具有標準的對外接口，這給STL中的算法使用迭代器提供了可能。熟練掌握這些迭代器的構造、用法，是基於STL的模板元編程的基礎。

迭代器的分類與接口

所有迭代器都應該實現自增算符：iter++、++iter

Input迭代器：
- *iter 解引用後只能用作右值
- iter->member 解引用訪問當前對象的成員數據
- iter=iter1 迭代器賦給另一個迭代器
- iter==iter1 迭代器相等比較
- iter!=iter1 迭代器不等比較
Output迭代器：
- *iter 解引用後只能用作左值
- iter=iter1 迭代器賦給另一個迭代器
Forward迭代器：具有輸入迭代器、輸出迭代器的所有功能，且可以反覆遍歷操作。支持對同一個元素的多次讀寫。可複製前向迭代器來記錄序列中的一個位置，以便將來返回此處。
Bidirectional迭代器：是在前向迭代器的基礎上，多了單步向後遍歷的能力
- --iter
- iter--
Random Access迭代器：在雙向迭代器基礎上，具有直接訪問各數據元素的能力。隨機迭代器增加了「迭代器算術運算」：
- iter+=i 迭代器遞增i位
- iter-=i 迭代器遞減i位
- iter+i 加i位後的迭代器
- iter-i 減i位後的迭代器
- iter[i] 加i位後的迭代器的解引用
- iter<iter1 如果迭代器iter的位置在iter1前，返回true，否則返回false
- iter<=iter1 如果iter的位置在iter1的前面或同一位置時返回true，否則返回false
- iter>iter1 如果迭代器iter的位置在iter1後，返回true，否則返回false
- iter>=iter1 如果iter的位置在iter1的後面或同一位置時返回true，否則返回false

在STL定義的容器中，string，vector與deque提供了隨機訪問迭代器，list、set、multiset、map、multimap提供了雙向迭代器。

<iterator>中定義的類

iterator_traits

iterator_traits是一個類模板，用於定義一批成員數據類型，使得STL的算法可以用一致的界面來使用各種迭代器。下述類型定義中的Iterator是類模板參數：^[1]

difference_type Iterator::difference_type
value_type Iterator::value_type
pointer Iterator::pointer
reference Iterator::reference
iterator_category Iterator::iterator_category

5個作為iterator tag的空類

input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag均為空類。用於函數（模板）重載時的參數，以便STL算法據此判明迭代器所屬類別做進一步優化。

iterator模板類

在iterator模板類中，定義了5個成員類別：value_type,difference_type pointer，reference, iterator_category，用作所有其它迭代器的基類。

iterator adapters

reverse_iterator模板類，用來逆序遍歷聚合，是STL各容器類的rbegin、rend成員函數返回的類型。其構造函數用正向迭代器作為參數，構造得到的迭代器指向參數迭代器所指位置的逆序的下一個元素。如果逆序迭代器r是用正序迭代器i構造得到，則&*r == &*(i-1)為真。逆序迭代器的成員函數base()，返回指向當前定位的正序迭代器。
move_iterator模板類，是一種輸入迭代器。但與普通的迭代器不同，解引用（deference）操作得到的是右值，並按移動(move)賦值語義處理。
make_move_iterator模板函數，用於方便地由一個容器構造出move_iterator。
back_insert_iterator模板類，是一種輸出迭代器，用於在容器對象的尾部追加新的元素。該迭代器被賦值時，調用了容器對象的push_back()成員函數。該迭代器的自增操作實際上為空操作。
back_inserter模板函數，用於方便地由一個容器構造出back_insert_iterator
front_insert_iterator模板類，是一種輸出迭代器，用於在容器對象的頭部插入新的元素。該迭代器被賦值時，調用了容器對象的push_front()成員函數。該迭代器的自增操作實際上為空操作。
front_inserter模板函數，用於方便地由一個容器構造出front_insert_iterator
insert_iterator模板類，是一種輸出迭代器，用於在容器對象的指定位置插入新的元素。該迭代器被賦值時，調用了容器對象的insert()成員函數。該迭代器的自增操作實際上為空操作。
insert_inserter模板函數，用於方便地由一個容器構造出insert_iterator

流迭代器

任何已定義輸入操作符(>>)的類型都可以定義istream_iterator。任何已定義輸出操作符(<<)的類型也可定義ostream_iterator。在創建流迭代器時，必須指定迭代器所讀寫的對象類型。

istream_iterator模板類，是一種單次遍歷（single-pass）的輸入迭代器。把一個std::basic_istream包裝為一個輸入流迭代器。從輸入流迭代器通過自增操作來讀取數據，實際上是調用了輸入流的>>算符。輸入流迭代器的默認構造函數返回一個指向流結束（end-of-stream）的迭代器。
ostream_iterator模板類，是一種單次遍歷（single-pass）的輸出迭代器。把一個std::basic_ostream包裝為一個輸出流迭代器。對輸出流迭代器賦值數據，實際上是調用了輸出流的<<算符。對輸出流迭代器自增，實際上是空操作。輸出流迭代器的解引用操作返回該迭代器自身。
istreambuf_iterator模板類，是一種單次遍歷（single-pass）的輸入迭代器。把一個std::basic_istreambuf包裝為一個輸入流迭代器。操作類似於istream_iterator，但效率更高。
ostreambuf_iterator模板類，是一種單次遍歷（single-pass）的輸出迭代器。把一個std::basic_ostreambuf包裝為一個輸出流迭代器。操作類似於ostream_iterator，但效率更高。

迭代器操作函數

advance：把迭代器增量指定的步數。步數可以是負值。不檢查迭代器是否超過序列尾部位置end()
distance：返回兩個迭代器的距離值。兩個迭代器必須指向同一個容器。如果不是隨機迭代器，則第二個迭代器的位置必須與第一個迭代器的位置相同或在其後。
iter_swap：交換兩個迭代器所指的容器對象的元素值。迭代器類型可以不同，但其所指的值對象必須可以相互賦值。
next：增量一個正向迭代器增量指定步數。此函數不適用reverse_iterator
prev：把一個雙向迭代器減量指定步數。

迭代器範圍函數

包括begin, cbegin, end, cend,rbegin,crbegin,rend, crend等函數。返回聚合容器的開始位置、結束位置。

成員函數base()把逆向迭代器轉化為對應的正向迭代器。

正向迭代器轉化為逆向迭代器，只需要類型轉化。

例子程序

 
#include <iostream>
#include <sstream>
#include <iterator>
#include <numeric>
 
int main()
{
    std::istringstream str("0.1 0.2 0.3 0.4");
    std::partial_sum(std::istream_iterator<double>(str),
                     std::istream_iterator<double>(),
                     std::ostream_iterator<double>(std::cout, " "));
}

運行後，輸出結果：

0.1 0.3 0.6 1

參考文獻

↑ Iterator library

[1] Iterator library

[1]