C++/STL/Iterator

維基教科書,自由的教學讀本
< C++

iteratorw: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

參考文獻[編輯]

  1. Iterator library