1.何為iterator?
2.為什麼用iterator?
3.怎麼用iterator?
4.深入iterator.
1.何為iterator?
iterator翻譯為疊代器，主要作用是提供對容器資料進行周遊，修改的一層抽象。舉個例子，連結清單和數組是不同的資料容器，我們知道如果需要通路它們當中的某個資料的下個元素，因為資料元素在數組和連結清單中的存儲方式不一樣，是以需要針對數組和連結清單各寫兩種方法來實作。但是當我們使用了iterator之後，這些針對不同資料容器的資料通路和修改等基本操作就都被抽象了出來。比如無論是數組還是連結清單，我們要通路他們當中的下一個元素，隻要使用這種資料提供的iterator，執行iterator++操作就可以了。各個資料容器都會提供自己的iterator，并讓iterator提供本身容器所能支援的基本資料操作。iterator所支援的标準資料操和一個指針所支援的所有操作類似，r++,r--,*r,r+=n,r-=n,r->,<,>,=,!=，指派。
1.1 iterator的操作與層次結構
iterator類似一個指針，它利用各種操作符重載讓自己被操作起來就好像操作一個指針。然後這其中根據各個資料容器的差異性也有諸多的限制。設想一下下面這個情況：一個數組容器的iterator可以提供++，--等操作，因為當數組的特性是隻要修改下标的值就可以通路相應下表對因的元素，那麼數組iterator的--,++操作就很容易的實作，但是一個單項連結清單容器呢，iterator的++操作可以很好的支援，但是iterator的--操作似乎就很麻煩了，就算可以實作我們也應該盡可能的不要使用，一是因為這不符合單向連結清單的特性，二是因為效率低下。如果需要--操作何不一開始就使用雙向連結清單容器呢？
舉上面這個例子隻是為了說明各個資料容器因為自身的資料結構的特點并不是支援所有的iterator的操作，它們隻能根據自身資料結構的特點，選擇性的支援iterator的操作。但是這就會帶來一個很大的問題，各個容器的iterator支援的操作都不一樣那麼使用起來肯定很麻煩，設計出來的東西也增加了對資料容器的耦合性。對于這個問題的解決方法就是将iterator細化開來，這種細化其實是一種實踐之後得出的結果(為什麼這麼細化後面再分析)，具體的細化層次如 InputIterator < ForwardIterator < BidirectionalIterator < RandomAccessIterator. 和一個OutPutIterator. "<"符号表示前者所支援的操作的範圍包含在後者之中，可以看作是一種繼承關系。而前四種iterator都可以支援OutPutIterator的操作，隻要它們支援了OutPutIterator那麼它們就都算做是mutable的iterator，反之則是我們常說的const_iterator。各種iterator支援的操作請參閱這裡http://en.cppreference.com/w/cpp/iterator。
1.2 iterator類與概念(concept)
上述我們說的5中細化的iterator它們并不是一個具體的類或任何其他東西(這裡要強調一點其實iterator也不一定就是類)，而是一種比類更抽象的存在，concept。可以用對象和類的關系來比喻類和concept的關系。InputIterator是一種concetpt，ForwardIterator也是一種concept，既然它們都不是類，那麼我們也不應該在用類的繼承關系來形容它們之間的關系。取而代之的是Refinement，ForwardIterator支援了所有inputIterator支援的操作那麼ForwardIterator稱作inputerator的Refinement。下面是關于concept與類更為确切的解釋：
concept可以看作是一組條件，隻要滿足了這組條件的type就是這個concept的model,char*是InputIterator這個concept的model，istream_iterator這個類也是它的model。是以說iterator不一定是類，而應該是一種type。從邏輯角度來說如果某個iterator是某個concept的Refinement concept的model，那麼它也一定是這個concept的model,事實也的确如此。既然上述幾種concept既不是類也不是任何具體的東西，那麼在某些有不有什麼辦法可以判斷某個type屬于某個型别呢，其實是有的，并且利用這個特點STL的算法還進行針對不同iterator的各種優化。在第四節會講到。
2.為什麼使用iterator?
為什麼使用iterator？如果從一個資料容器的角度出發那麼你也許會想，我使用容器提供的iterator的++操作符和容器本身就提供的next()方法來通路下個元素沒有任何缺别，或者更可以說使用iterator還不如next()方法來得友善。不得不說确實是這樣。但是如果有一萬個容器來說呢？如果這一萬個容器都提供一個統一的通路方法那麼使用起來你就或多或少的會感覺到iterator的友善之處了。為什麼不讓這些容器都提供統一的方法接口而是要他們都提供一個iterator來供外界通路呢？試想一下如果一個容器提供了一個next()方法，并在容器内部定義了一個變量index用來指向這個容器目前指向的資料對象的索引，那麼如果在多個地方我都調用這個容器對象的next()方法，調用容器對象的next()方法所得到的值就不一定是你上次所通路的元素的下一個值了，而且取決于在你這調用next()方法之前，next()方法在其他地方被調用了幾次。那麼next()方法也就失去了它的意義。舉這個例子隻是為了說明容器内部不應該保留資料通路的狀态，這樣會影響到諸如通路下個元素等操作的正确性。那麼這個時候iterator就出現了替代了在容器對象内部存儲資料的通路狀态，轉而給每一個通路者一個iterator對象用來存儲通路者對這個容器對象的資料的通路狀态。
另外一個使用iterator的原因還是離不開iterator對資料容器的基本操作的抽象特性。STL中另外一個非常重要的部分就是算法，而算法的作用對象就是容器。設想一下這麼一個算法，要求給這個算法輸入一個值value和一個容器對象container，算法的目的是在這個容器搜尋這個值并傳回容器中這個值的引用。假如在沒有iterator，那麼沒有其他辦法我們隻有為每一個容器提供一個這個容器對應的算法了（不要假想所有的容器提供一個統一的方法接口這種方法，這種方法不可行的原因上面已經說明了）。但是有了iterator之後這個算法就可以寫的很簡單了,其定義類似與下面這種
template< class InputIt, class T > InputIt find( InputIt first, InputIt last, const T& value )
{
while(first!=last)
{
if(*first==value)
break;
first++;
}
return first;
}
從上面這個例子大概也就能看出iterator作為STL算法與資料容器之間橋梁的重要性了。但是還有一個額外的問題，其實就是各個算發所需要用到的iterator操作各不相同，有的算法如find，它隻需要*,++,!=這幾個操作就夠了，是以隻需要支援這幾個操作的iterator的都可以使用find算法。而sort算法就需要randomIterator。總的來說各個算法所需要的iterator操作數都可以用上面細化的幾種iterator來代表，而這幾種細化的iterator個人覺得其實也是在對容器和算法的設計過程中經驗的總結歸納吧，當然這也隻是我個人的猜測而已。使用iterator容器之後從軟體設計的角度來說降低了對資料容器的耦合性，可以很輕易在幾種資料容器之中切換開來隻要他們的iterator支援的操作滿足我們程式的要求即可。而且在有了各種STL算法的支援之後使得很多不必要的勞動得到了節省，并且各種算法的效率也是非常有保障的。
3.如何使用iterator？
3.1.iterator擴充卡 其實這裡說道擴充卡，什麼是擴充卡，就是“把一種接口轉化為另外一種接口的組建”。打個比方你寫了一個list，它隻有一些不符合标準的方法，你又寫了一個class包裝了這個list并提供了一些符合STL标準的接口，那麼你這個class就可以算作是adaptor，它将list原有接口轉化為了另外一組接口而list根本就不知道它的存在。 在STL中iterator的擴充卡，它們隻是将STL的元件進行适配提另外一些不同的接口。比如下面這個例子：
typedef vector<int>::iterator pointer;
typedef vector<int>::const_iterator cpointer;
vector<int> ve;
ve.reserve(10);
for(int i=0;i<10;i++)
{
ve.push_back(i);
}
//reverse_iterator的構造參數至少需要支援biddirectioniterator的操作
//用reverse_iterator适配vector的randomiterator
reverse_iterator<pointer> rbegin(ve.end());
reverse_iterator<pointer> rend(ve.begin());
while(rbegin!=rend)
{
cout<<*rbegin++<<", ";
}
我們将vector<int>的iterator用reverse_iterator進行适配了，改變了它的++，*等接口的實作，讓它能夠倒序周遊。但是要小心reverse_iterator的*行為，它總是會取目前引用的上一個值，是以reverse_iterator的起始點是end(),而止行點是first。 上面這個例子隻是将iterator作為參數進行了适配，而STL其它的iterator adaptor則會将容器作為參數進行适配。但是要注意這類擴充卡也有一定的前提條件比如：
vector<int> firstvector, secondvector;
for (int i=1; i<=5; i++)
{ firstvector.push_back(i); secondvector.push_back(i*10); }
//對vector容器進行了适配，産生出的iterator對象的*指派操作将被改寫成push_back操作，而++等其他操作将不會有任何實際意義。
back_insert_iterator< vector<int> > back_it (firstvector);
copy (secondvector.begin(),secondvector.end(),back_it);
vector<int>::iterator it;
for ( it = firstvector.begin(); it!= firstvector.end(); ++it )
cout << *it << " ";
cout << endl;
其中我們使用了back_insert_iterator對vector<int>容器進行了适配，back_insert_iterator的參數要求這個容器必須提供push_back接口。 STL還為我們提供了6，7中iterator，包括back(front)_insert_iterator,insert_iterator(改寫了指派操作為容器的insert操作)，i(o)stream_iterator(對iostream進行了封裝)，reverse_iterator（改變了iterator的++操作為--操作，*解引操作實作也略微改變）。
3.2.iterator誤區
如何使用iterator？其實最簡便的認識你可以把各種iterator當作一個隻支援部分功能的指針來使用即可，小心的參閱文檔不使用文檔中沒有提及的操作比如對forwarditerator那麼我們就不要使用--操作，對于BidirectionalIterator我們不使用+n操作。按照iterator的繼承結構來說子類的iterator可以向上“轉型”當作父類來用，但是父類的iterator不要當作之類來用。當你定義一個需要傳入iterator的方法時，盡量使用更上層的iterator來指定傳入參數，這樣就可以支援更多的資料容器的iterator作為傳入參數。上面隻是一些使用的建議，下面是一些我們使用iterator是經常會遇到的誤區：
1.const vector<type>::iterator 和vector<type>::const_iterator的差別。const vector<type>::iterator隻是限定iterator不可改變，而iterator所指向的值卻沒有保證,即++，--等操作不可以執行，但是*指派可以。const_iterator保證的是const_iterator的容器對象的值是不可改變的，而const_iterator本身是可以改變的++，--可以，*指派不可以。v
2.iterator的比較操作符==，!=,>,<,-,+是用來操作iterator自身的值（指針的位址），而不是所指向的容器的資料的值。
3.iterator的失效。iterator本質上來說就是一個跟容器相關的經過了包裝了的指針，當我們解引取值時還是調用的指針的*符号，而當容器内的資料發生移動，删除等操作時很可能導緻iterator所指向的位址的值已經發生改變或是已經删除。這個時候就是所謂的iterator失效。當然也并不是所有的操作都會帶來iterator失效，而且這也與容器的類型有關。隻要記住一點任何可能導緻iterator所指向位址失效的操作就會導緻iterator失效，這個時候在繼續使用iterator會帶來一些不能預料的後果。這裡是Peter Lsensee的一篇http://www.tantalon.com/pete/embracingstl.ppt PPT，裡面詳細闡述了何時iterator會失效。你需要小心使用那些使用數組存儲，會自動重新配置設定記憶體的資料結構。并且當你在循環裡調用了删除，插入等操作之後，記得利用這些操作的傳回值及時更新你的iterator以免失效。而對于關聯容器來說插入操作通常不會讓你的指針失效。下面是一個例子：
typedef vector<int>::iterator pointer;
typedef vector<int>::const_iterator cpointer;
vector<int> ve;
ve.reserve(3);//這裡預留了3的容量
pointer p=ve.begin();
for(int i=0;i<6;i++)
{
//這裡在不停插入之後導緻vector不得不重新配置設定一塊更大的連續記憶體來存儲資料
ve.insert(p,i);
}
這個例子因為vector數組的重配置設定，導緻指向原來記憶體的iterator失效，在原先記憶體上的操作将導緻不可預料的行為，當然最常見的就是段錯誤了。隻要将p=ve.insert(p,i)替換掉原來的插入語句即可，這行語句表示每次插入之後都更新iterator以免失效。
4.不要用iterator和NULL來比較來判斷容器方法的傳回值。因為當一個容器的方法如find(const type& value)沒有找到元素時它會傳回一個指向最後一個元素之後的iterator來表明沒有找到指定元素，這時你應該先比較傳回的iterator和最後一個元素之後的iterator的值是否相等來判斷是否得到你想要的東西。一般這個值的表示vector.end(),map.end()等方法的傳回值。調用iterator的==操作符和NULL比較，你會發現iterator在大多數情況下根本沒有聲明這個方法。
4.深入iterator.
暫時留到下篇文章。将會探讨：
1.如何在一個模闆方法内得到一個iterator的型别(type),即這個iterator指向的值類型。
2.STL算法是如何判斷一個iterator屬于哪個concept以及一個算法如何針對不同的iterator做相應的優化。