迭代器（iterator）是連接容器和算法的紐帶，為數(shù)據(jù)提供了抽象，使寫算法的人不必關(guān)心各種數(shù)據(jù)結(jié)構(gòu)的細節(jié)。迭代器提供了數(shù)據(jù)訪問的標準模型——對象序列，使對容器更廣泛的訪問操作成為可能。

泛型編程的關(guān)鍵所在，就是如何找到一種通用的方法，來訪問具有不同結(jié)構(gòu)的各種容器中的每個元素，而這正是迭代器的功能。

迭代器是一種廣義的指針，是指向序列元素指針概念的一種抽象。迭代器可以指向容器中的任意元素，還能遍歷整個容器。

（序列）容器是數(shù)組的抽象，而迭代器則是指向數(shù)組指針的抽象。迭代器雖然是廣義的指針，但是，迭代器并不是通用的指針。不同的容器可能需要不同的迭代器，實際上，在STL中，為每種容器都typedef了一個迭代器，名為iterator。例如，vector<T>的迭代器類型為<vector<T>::iterator（是一種隨機訪問迭代器）、list<T>的迭代器類型為list<T>::iterator（是一種雙向迭代器）。

（1）特征與操作

<!--[if !supportLists]-->l         <!--[endif]-->迭代器的基本特征有：

<!--[if !supportLists]-->n         <!--[endif]-->解除——支持解除引用（dereference）操作，以便可以訪問它引用的值。即，如果p是一個迭代器，則應(yīng)該對*p和p->進行定義（似指針）；

<!--[if !supportLists]-->n         <!--[endif]-->賦值——可將一個迭代器賦給另一個迭代器。即，如果p和q都是迭代器，則應(yīng)該對表達式p=q進行定義；

<!--[if !supportLists]-->n         <!--[endif]-->比較——可將一個迭代器與另一個迭代器進行比較。即，如果p和q都是迭代器，則應(yīng)該對表達式p==q和p!=q進行定義；

<!--[if !supportLists]-->n         <!--[endif]-->遍歷——可以使用迭代器來遍歷容器中的元素，這可以通過為迭代器p定義++p和p++操作來實現(xiàn)。

<!--[if !supportLists]-->l         <!--[endif]-->迭代器的操作有：

<!--[if !supportLists]-->n         <!--[endif]-->讀——通過解除引用*來間接引用容器中的元素值，例如x = *p;

<!--[if !supportLists]-->n         <!--[endif]-->寫——通過解除引用*來給容器中的元素賦值，例如*p = x;

<!--[if !supportLists]-->n         <!--[endif]-->訪問——通過下標和指向引用容器中的元素及其成員，例如p[2]和p->m

<!--[if !supportLists]-->n         <!--[endif]-->迭代——利用增量和減量運算（++和--、+和-、+=和-=）在容器中遍歷、漫游和跳躍，例如p++、--p、p+5、p-=8

<!--[if !supportLists]-->n         <!--[endif]-->比較——利用比較運算符（==、！=、<、>、<=、>=）來比較兩個迭代器是否相等或誰大誰小，例如if(p < q)……;、wihle(p != c.end())……;

不同的泛型算法，對迭代器的要求也是不同的。例如，查找算法，只要求定義++操作符，以便迭代器能遍歷整個容器，讀取每一個元素的值來進行比較；但是，查找算法，并不需要修改數(shù)據(jù)，所以不要求寫操作。排序算法則要求能隨機訪問，以便交換不相鄰的元素；這需要對迭代器iter定義+操作，以便能夠使用像iter + 12這樣的表達式；另外，排序算法還要求可以讀寫數(shù)據(jù)。

（2）分類

根據(jù)迭代器所支持的操作不同，在STL中定義了如下5種迭代器：

<!--[if !supportLists]-->l         <!--[endif]-->輸入迭代器（input iterator）——用于讀取容器中的信息，但不一定能夠修改它。

<!--[if !supportLists]-->n         <!--[endif]-->輸入迭代器iter通過解除引用（即*iter），來讀取容器中其所指向元素之值；

<!--[if !supportLists]-->n         <!--[endif]-->為了使輸入迭代器能夠訪問容器中的所有元素的值，必須使其支持（前/后綴格式的）++ 操作符；

<!--[if !supportLists]-->n         <!--[endif]-->輸入迭代器不能保證第二次遍歷容器時，順序不變；也不能保證其遞增后，先前指向的值不變。即，基于輸入迭代器的任何算法，都應(yīng)該是單通（single-pass）的，不依賴于前一次遍歷時的值，也不依賴于本次遍歷中前面的值。

可見輸入迭代器是一種單向的只讀迭代器，可以遞增但是不能遞減，而且只能讀不能寫。適用于單通只讀型算法。

<!--[if !supportLists]-->l         <!--[endif]-->輸出迭代器（output iterator）——用于將信息傳輸給容器（修改容器中元素的值），但是不能讀取。例如，顯示器就是只能寫不能讀的設(shè)備，可用輸出容器來表示它。也支持解除引用和++操作，也是單通的。所以，輸出迭代器適用于單通只寫型算法。

<!--[if !supportLists]-->l         <!--[endif]-->前向迭代器（forward iterator正向迭代器）——只能使用++操作符來單向遍歷容器（不能用--）。與I/O迭代器一樣，前向迭代器也支持解除引用與++操作。與I/O迭代器不同的是，前向迭代器是多通的（multi-pass）。即，它總是以同樣的順序來遍歷容器，而且迭代器遞增后，仍然可以通過解除保存的迭代器引用，來獲得同樣的值。另外，前向迭代器既可以是讀寫型的，也可以是只讀的。

<!--[if !supportLists]-->l         <!--[endif]-->雙向迭代器（bidirectional iterator）——可以用++和--操作符來雙向遍歷容器。其他與前向迭代器一樣，也支持解除引用、也是多通的、也是可讀寫或只讀的。

<!--[if !supportLists]-->l         <!--[endif]-->隨機訪問迭代器（random access iterator）——可直接訪問容器中的任意一個元素的雙向迭代器。

可見，這5種迭代器形成了一個層次結(jié)構(gòu)：I/O迭代器（都可++遍歷，但是前者只讀/后者只寫）最基本、前向迭代器可讀寫但只能++遍歷、雙向迭代器也可讀寫但能++/--雙向遍歷、隨機迭代器除了能夠雙向遍歷外還能夠隨機訪問。

迭代器性能

注意：各種迭代器的類型并不是確定的，而只是一種概念性的描述。不能用面向?qū)ο蟮恼Z言來表達迭代器的種類，迭代器的種類只是一系列的要求，而不是一種類型（類）。在STL中，用概念（concept）一詞來描述這一系列要求。因此，有輸入迭代器概念和雙向迭代器概念，但是卻沒有輸入迭代器類型和雙向迭代器類型。

（3）聲明

迭代器類iterator和函數(shù)的聲明都位于命名空間std中，可以在頭文件<iterator>中找到：

namespace std { // 取自C++2003標準

// primitives:基礎(chǔ)/原語

template<class Iterator> struct iterator_traits; // 迭代器特征

template<class T> struct iterator_traits<T*>; // 指針的專門化

template<class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&> struct iterator; // 迭代器

struct input_iterator_tag {}; // 迭代器標志（類別）

struct output_iterator_tag {};

struct forward_iterator_tag: public input_iterator_tag {};

struct bidirectional_iterator_tag: public forward_iterator_tag {};

struct random_access_iterator_tag: public bidirectional_iterator_tag {};

// iterator operations:迭代器操作

template <class InputIterator, class Distance> void advance(InputIterator& i, Distance n);

template <class InputIterator> typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);

// predefined iterators:預(yù)定義迭代器（及其比較運算符重載）

template <class Iterator> class reverse_iterator; // 反向迭代器

template <class Iterator> bool operator==(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y);

template <class Iterator> bool operator<(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y);

template <class Iterator> bool operator!=(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y);

template <class Iterator> bool operator>(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y);

template <class Iterator> bool operator>=(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y);

template <class Iterator> bool operator<=(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y);

template <class Iterator> typename reverse_iterator<Iterator>::difference_type operator- (const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y);

template <class Iterator> reverse_iterator<Iterator> operator+(typename reverse_iterator <Iterator>::difference_type n, const reverse_iterator<Iterator>& x);

// 插入器

template <class Container> class back_insert_iterator;

template <class Container> back_insert_iterator<Container> back_inserter(Container& x);

template <class Container> class front_insert_iterator;

template <class Container> front_insert_iterator<Container> front_inserter(Container& x);

template <class Container> class insert_iterator;

template <class Container, class Iterator>

insert_iterator<Container> inserter(Container& x, Iterator i);

// stream iterators:流迭代器

template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t> class istream_iterator;

template <class T, class charT, class traits, class Distance> bool operator==(const istream_iterator<T,charT,traits,Distance>& x, const istream_iterator<T, charT, traits, Distance>& y);

template <class T, class charT, class traits, class Distance> bool operator!=(const istream_iterator<T,charT,traits,Distance>& x, const istream_iterator<T, charT, traits, Distance>& y);

template <class T, class charT = char, class traits = char_traits<charT> > class ostream_iterator;

template<class charT, class traits = char_traits<charT> > class istreambuf_iterator;

template <class charT, class traits> bool operator==(const istreambuf_iterator<charT, traits>& a, const istreambuf_iterator<charT,traits>& b);

template <class charT, class traits> bool operator!=(const istreambuf_iterator<charT, traits>& a, const istreambuf_iterator<charT,traits>& b);

template <class charT, class traits = char_traits<charT> > class ostreambuf_iterator;

}

（4）預(yù)定義迭代器

STL有一個使用方便的預(yù)定義迭代器集合，其中包括正向迭代器、反向迭代器、插入器和流迭代器。

<!--[if !supportLists]-->l         <!--[endif]-->正向迭代器：

template<class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&> struct iterator;

在所有的標準容器類中，都定義了返回iterator對象的成員函數(shù)begin()和end()。例如

namespace std {

template <class T, class Allocator = allocator<T> > class vector {

public:

                     ……

// iterators:迭代器

iterator begin(); // 指向首元素

const_iterator begin() const;

iterator end(); // 指向尾元素后的一個位置

const_iterator end() const;

reverse_iterator rbegin(); // 指向反向序列的首元素

const_reverse_iterator rbegin() const;

reverse_iterator rend(); // 指向反向序列尾元素后的一個位置

const_reverse_iterator rend() const;

                     ……

              }

}

通過在程序中調(diào)用它們，就可以得到正向迭代器 iterator的對象，從而能夠正向遍歷容器。例如：（c為任意標準容器對象，op為某一函數(shù)對象）

for_each(c.begin(), c.end(), op);

<!--[if !supportLists]-->l         <!--[endif]-->反向迭代器：

template <class Iterator> class reverse_iterator;

在標準容器中調(diào)用rbegin()和rend()，就可以得到反向迭代器 reverse_iterator的對象，從而可反向遍歷容器。例如：

// Revers.cpp

#include <fstream>

#include <iostream>

#include <string>

#include <vector>

using namespace std;

 

int main() ...{

  ifstream in("Revers.cpp");

  if(!in) ...{

       cout << " Open file Revers.cpp error ! " << endl;

       return 1;

  }

  string line;

  vector<string> lines;

  while(getline(in, line)) lines.push_back(line);

  for(vector<string>::reverse_iterator r = lines.rbegin();

         r != lines.rend(); r++)

    cout << *r << endl;

}

運行結(jié)果 為將此代碼反序輸出。先輸出最后一行

<!--[if !supportLists]-->l         <!--[endif]-->插入器

如果需要輸出或復(fù)制元素到容器，又不想覆蓋容器中原有的內(nèi)容，還要避免溢出，這就需要插入器來幫忙。STL提供了三種插入器，分別對應(yīng)于后插、前插和中插：

template <class Container> class back_insert_iterator; // 在尾部插入

template <class Container> back_insert_iterator<Container> back_inserter(Container& x);

template <class Container> class front_insert_iterator; // 在頭部插入

template <class Container> front_insert_iterator<Container> front_inserter(Container& x);

template <class Container> class insert_iterator; // 在中間插入

template <class Container, class Iterator>

insert_iterator<Container> inserter(Container& x, Iterator i);

例如：

// Insert.cpp

#include <iostream>

#include <vector>

#include <deque>

#include <list>

#include <iterator>

using namespace std;

 

int a[] = ...{ 1, 3, 5, 7, 11, 13, 17, 19, 23 }; // 質(zhì)數(shù)序列

 

template<class Cont> void frontInsertion(Cont& ci) ...{ // 前插

  copy(a, a + sizeof(a)/sizeof(Cont::value_type), front_inserter(ci)); // 插入a

  // 插入空格

  copy(ci.begin(), ci.end(), ostream_iterator<typename Cont::value_type>(cout, " "));

  cout << endl;

}

 

template<class Cont> void backInsertion(Cont& ci) ...{ // 后插

  copy(a, a + sizeof(a)/sizeof(Cont::value_type), back_inserter(ci)); // 插入a

  // 插入空格

  copy(ci.begin(), ci.end(), ostream_iterator<typename Cont::value_type>(cout, " "));

  cout << endl;

}

 

template<class Cont> void midInsertion(Cont& ci) ...{ // 中插

  typename Cont::iterator it = ci.begin();

  ++it; ++it; ++it; // 迭代器指向第4個元素

  copy(a, a + sizeof(a)/(sizeof(Cont::value_type) * 2), inserter(ci, it)); // 插入9/2=4個數(shù)

  // 插入空格

  copy(ci.begin(), ci.end(), ostream_iterator<typename Cont::value_type>(cout, " "));

  cout << endl;

}

 

int main() ...{

  deque<int> di;

  list<int> li;

  vector<int> vi;

  frontInsertion(di);

  frontInsertion(li);

  // frontInsertion(vi); // 對向量不能使用前插

  di.clear();

  li.clear();

  backInsertion(vi);

  backInsertion(di);

  backInsertion(li);

  midInsertion(vi);

  midInsertion(di);

  midInsertion(li);

}

運行結(jié)果為：
23 19 17 13 11 7 5 3 1

23 19 17 13 11 7 5 3 1

1 3 5 7 11 13 17 19 23

1 3 5 7 11 13 17 19 23

1 3 5 7 11 13 17 19 23

1 3 5 1 3 5 7 7 11 13 17 19 23

1 3 5 1 3 5 7 7 11 13 17 19 23

1 3 5 1 3 5 7 7 11 13 17 19 23

<!--[if !supportLists]-->l         <!--[endif]-->流迭代器

一般I/O是通過C++的流庫或C的I/O函數(shù)完成的，也可以通過GUI的對話框等來進行I/O操作。這些I/O接口的基本目標，是讀取各種類型的單個值。

為了使I/O能夠以序列的方式呈現(xiàn)，將流I/O融入容器和算法的通用框架之中，STL還提供了4個流迭代器的模版類：

<!--[if !supportLists]-->n         <!--[endif]-->istream_iterator——用于從輸入流讀取

<!--[if !supportLists]-->n         <!--[endif]-->ostream_iterator——用于向輸出流寫入

<!--[if !supportLists]-->n         <!--[endif]-->istreambuf_iterator——用于從輸入流緩沖區(qū)讀取

<!--[if !supportLists]-->n         <!--[endif]-->ostreambuf_iterator——用于向輸出流緩沖區(qū)寫入

從輸入流讀取的操作，由對輸入流迭代器is的間接引用*is的賦值來進行，在每兩次輸入之間，必須進行一次增量操作，為下一次輸入做好準備。類似地，寫出到輸出流的操作，由對輸出流迭代器os的間接引用*os的賦值來進行，在每兩次輸出之間，也必須進行一次增量操作，為下一次輸出做好準備。

例如：

// Stream.cpp

#include<iostream>

#include<iterator>

using namespace std;

int main() ...{

       ostream_iterator<int> os(cout); // 將int通過os輸出到cout

       *os = 5; // 輸出5（用cout << 5;）

       os++; // 準備好下一次的輸出

       *os = 80;

       istream_iterator<int> is(cin); // 通過is從cin讀入int

       int i1 = *is; // 輸入到i1

       is++; // 準備好下一次的輸入

       int i2 = *is; // 輸入到i2

       cout << "i1 = " << i1 << ",  i2 = " << i2 << endl;

}

 

運行結(jié)果如下：

580

78          

56

i1 = 78, i2 = 56

又例如：

// StreamIt.cpp

#include <fstream>

#include <iostream>

#include <iterator>

#include <string>

#include <vector>

using namespace std;

int main() ...{

  ifstream in("StreamIt.cpp");

  istream_iterator<string> begin(in), end;

  ostream_iterator<string> out(cout, " ");

  vector<string> vs;

  copy(begin, end, back_inserter(vs));

  copy(vs.begin(), vs.end(), out);

  *out++ = vs[0];

  *out++ = "That's all, folks!";

}

（5）指針與迭代器

既然迭代器是廣義的指針，那么指針本身是不是迭代器呢？其實，指針滿足所有迭代器的要求，所以，指針就是一種迭代器。

迭代器是泛型算法的接口，而指針是迭代器。所以，各種STL算法，也可以使用指針，來對非標準容器（如數(shù)組）進行操作。即，利用指針做迭代器，可以將STL算法用于常規(guī)數(shù)組。

例如排序函數(shù)sort：

sort(Ran first, Ran last); // Ran表示隨機訪問迭代器

對容器c為：

sort(c.begin(), c.end());

對數(shù)組a可以改為：（const int SIZE = 100; float a[SIZE];）

sort(a, a + SIZE);

又例如復(fù)制函數(shù)copy：

copy(In first, In last, Out res); // In和Out分別表示輸入和輸出迭代器

對容器c<int>可為：（ostream_iterator<int> out_iter(cout);）

copy(c.begin(), c.end(), out_iter);

對數(shù)組a可以改為：（const int SIZE = 100; float a[SIZE];）

copy(a, a + SIZE, c.begin());