C++ STL Iterator Category

InputIterator

支援行為

  • i++
    可將將 Iterator 往前走一步,但之前的 iterator 所指的位置不保證有效。一次性的讀取。

  • result = *i
    對 Iterator 所指位置作 提領,將提領出來的值放在等號左邊的 result。

  • i != j
    對 Iterator 判斷是否不相等,通常用於測試是否己到區間尾端(end)。
    for(i=vec.begin();i != vec.end();i++);

代表性例子: istream_iterator<T>

InputIterator 是 STL 中唯二操作限制最高的 Iterator,你只能巡航一次 Iterator 所指的位置一次。你把當前的 Iterator 位置存起來,再將 Iterator 步進,接著再提領你存起來那個 舊 Iterator,將導致 Undefined Behavior。

就像是你在操作 cin >> str 代表從鍵盤中讀取一段字串,那麼讀取上一次的輸入己經了無意義,因為他己經被 buffer 洗掉了。

因為它是限制最高的 Iterator,所以當 STL 演算法支援的是這種 Iterator ,代表它相容的 Iterator 最多,最 generic。在制作 STL-like 的演算法時,也應該以支援 InputIterator 為目標,來達到容納最多種的 Iterator。

OutputIterator

支援行為

  • i++
    與 InputIterator 相同,它也只保證一次性的巡航。

  • *i = element
    可以將 Iterator 指向的位置寫入 element。

代表性例子: ostream_iterator<T>

對於 cout << str; ,你也無法再對印出的字串再做修改寫入,對於巡航過後的舊位置,不保證可以寫入。就像是說出去的話一樣,收不回來;嫁出去的女兒;打出去的全疊打;當年的18歲,你都無法重過了。

ForwardIterator

支援行為

  • 具有 InputIterator 與 OutputIterator 所有支援操作。

  • old_i = i; i++; valid_result = *old_i
    與 InputIterator 最大的不同就是,對於走過的位置,可以無限次做存取,往前走一步,之前的 iterator 所指的位置保證有效。

代表性例子: C++ 11 的 forward_list<T>::iterator

可以想像操作單向陣列,它只儲存著 next 指標,對於 iterator 只能往下走,沒辦法往回頭路。跟 InputIterator 最大的不同是,它的 Iterator 所指位置,在巡航過後,依然都有效,可以多次存取。
STL Container 一般來說都是可以支援此種 Iterator,因為 Container 實體一直都存在,不像 cin, cout 無法使用舊有的位置。因為依然存在於 Container 中,所以就算對 Iterator 做了巡航,還是可以做存取舊有的 Iterator 位置。

BidirectionalIterator

支援行為

  • 具有 ForwardIterator 所有支援操作。

  • i--
    可將 Iterator 往後走一步,其提領的值皆有效。

代表性例子: list<T>::iterator

STL 的 list 是一個雙向 list,你可以對做 i++i--,來前後巡航它。list 的 提領第 n 個 element 的操作,可以想像的出來是做 next n 次,其複雜度是 linear ,沒有很好的效率,所以它的 Iterator 並不支援 i[n] 的操作,此像操作要由下面會提到 RandomAccessIterator 才能夠支援。

RandomAccessIterator

支援行為

  • 具有 BidirectionalIterator 所有支援操作

  • i[n], i += n: 允許 Iterator 進行 offset n 的移動。

  • i < ji > ji - n 等等其他具有 位置性的操作

代表性例子: vectordequestringStandard Pointer

vector 可以在常數時間,使用 subscript 下標操作,指領出 index 是 n 的 element。這次威力最強大的 Iterator,對於容器的需要也是最大的,通常是要連續續擺放跟位置有相依性的容器,才有這種威力強大的 Iterator。

STL 演算法依照 Iterator Tag 來判斷所能做的操作

基本上每一種 STL 的 Iterator 都帶有一個 Tag,來讓 STL 演算法判斷,對於此種 Iterator 是否可以操作、或是有更快的操作。像是你傳入了一個 ForwardIterator 給 sort,STL 演算法就會噴 error 說需要至少 RandomAccessIterator。

對於 distance 判斷兩個 Iterator 的距離,STL 演算法對於一般的 Iterator 就是乖乖的步進到 endIterator,來算出距離,複雜度是 linear。但是面對到了 RandomAccessIterator,卻可以直接 endIterator - beginIterator ,直接 constant time 算出。

依照不同的 IteratorTag class type 可以使用 function overloading ,在 compile 時間就決定其實作內容。

STL 演算法:盡量接收限制最少的 Iterator

STL 演算法只有幾種操作,才會需要這種限制最高的 RandomAccessIterator,像是 sortrandom_shuffle。連 rotatereversenext_permutation都不需要用到 RandomAccessIterator。

  • 對於只會掃過一遍的 Iterator 區間,能夠用 InputIterator 就不會用到 ForwardIterator,像是 copyreplace
  • 對於只會往前走的,能夠用 ForwardIterator 就不會用 BidirectionalIterator,像是 unique
  • 對於能夠用走一步一步走就好的操作,能用 BidirectionalIterator,就不會用 RandomAccessIterator,像是 reverse

有時候演算法設計可以依照對於 Iterator 操作限制較低的方向設計,不一定要用 subscript 來操作 container,有時候 i++、i-- 也能夠做到,而且複雜度還不會因此較高。

為什麼要用 STL style for loop

  1. for(auto i = container.begin() + 0; i < container.end(); i += 1)
  2. instead of for(auto i = container.begin(); i != conatiner.end() ; i++ )
  • i = container.begin() + 0
    operator+,Iterator 需要offset 移動,將會要求 container Iterator 必需支援 RandomAccessIterator,

  • i < container.end()
    operator<,Iterator 需要比較,將會要求 container Iterator 必需支援 RandomAccessIterator。

  • i += 1
    operator+=,Iterator 需要offset 移動並賦值,將會要求 container Iterator 必需支援 RandomAccessIterator。

所以不支援 RandomAccessIterator 的 list, set, map 與其他容器不能適用此 1. 判斷式。

若寫成第 2. 式的 for loop,則對於 container 的 Iterator 只要最低限制的 InputIterator 即可,擁有最佳的 generic 性質。

STL 演算法對於傳入的容器 Iterator,只會做有限制的操作

STL 演算法是依照 Iterator Category 所支援的操作所做事,Iterator 能做什麼事,STL 演算法就只會對 Iterator 做什麼事。這表示 STL 演算法不會操作跟容器相依的操作,像是 push_backinserteraseoperator>> 等等。

如果要讓你的容器,像是 vector 讓 STL 演算法對它做 push_back,你就要用某種 iterator 會將 push_back 包裝成 RandomAccessIterator 所支援的操作其中之一。STL 有提供一個 Iterator 叫做 BackInserterIterator<T>,會將含有 push_back 的容器,包裝起來,當你對容器操作 *i++ = element; 時,就像是在對它操作 vector<T>::push_back(element);,也就可以讓 STL 演算法,間接操作容器的 push_back操作。

OutputIterator 與 const 修飾子

除了 InputIterator 之外,其他 Iterator 都支援 OutputIterator 的 Iterator Tag,但是一個 iterator 指向的值能否被寫入,不只是看它能否支援 OutputIterator,還要看它有沒有被修飾成 const。

OutputIterator 只是 描述 operator= 有沒有意義;而 const 則是最更實際地判斷能不能寫入

comments powered by Disqus