イテレータ

C/C++でのプログラミングで避けて通れないのが"ポインタ"です。ポインタは配列の要素を順にアクセスすることができます:
  // 配列の要素をプリントする。
  void print_array(int* a, int N) {
    int* p = a;
    for ( int i = 0; i < N; ++i ) {
      cout << *p << ' ';
      ++p;
    }
    cout << endl;
  }

  int a[10];
  print_array(a,10);
同様に、配列とは異なるデータ構造である単方向リストの内容をプリントするには、
  struct slink_of_int {
    int data;
    slink_of_int* next; // 次のリンク(末端には0を設定)
  };

  // リストの要素をプリントする
  void print_list(slink_of_int* p) {
    while ( p ) {
      cout << p->data << ' ';
      p = p->next;
    }
    cout << endl;
  }

  slink_of_int* lp = listの先頭
  print_list(lp);
コンテナ(データ構造)が異なれば、コンテナ内の要素のアクセスのしかたも異なります。コンテナ内の要素を統一したインタフェースでアクセスできるなら、プリントする関数をひとつ定義すれば配列だろうがリストだろうがその関数に食わせることができます。コンテナ内の要素を統一したインタフェースでアクセスするオブジェクト、それがイテレータです。
  template<class Iterator>
  void print_any(Iterator first, Iterator last) {
    while ( first != last ) {
      cout << *first << ' ';
      ++first;
    }
    cout << endl;
  }
という関数テンプレートが定義されているとき、クラスIteratorが、 という仕様を満足しているものならばなんであれ、print_anyの引数となることができます。様々なコンテナに対して適切なIteratorを定義することで、たったひとつのprint_anyをあらゆるコンテナのプリントに利用できるわけです。

slink_of_intをprint_anyによってプリントするため、上記の仕様を満足するクラスslink_iteratorを以下に示します。

  class slink_iterator {
    slink_of_int* cursor;
  public:
    // コンストラクタ
    explicit slink_iterator(slink_of_int* p =0) : cursor(p) {}
    // '++' 演算子
    slink_iterator& operator++()
      { cursor = cursor->next; return *this; }
    // '*' 演算子
    int operator*()
      { return cursor->data; }
    // '!=' 演算子
    friend bool operator!=(const slink_iterator& x,
                           const slink_iterator& y)
      { return x.cursor != y.cursor; }
  };

  int main() {
    int array[] = { 1, 2, 3 };
    // 配列のプリント
    cout << "array : ";
    print_any(array, array+3);

    // slink_of_intの数珠つなぎをつくる
    slink_of_int s1, s2, s3;
    s1.data = 1; s1.next = &s2;
    s2.data = 2; s2.next = &s3;
    s3.data = 3; s3.next = 0;

    // slinkのプリント
    cout << "slink : ";
    print_any(slink_iterator(&s1),slink_iterator());

    return 0;
  }

  実行結果:
    array : 1 2 3
    slink : 1 2 3
イテレータ(Iterator)はコンテナに格納された要素をアルゴリズムに引き渡すため、あるいはアルゴリズムから得られた結果をコンテナに格納するために用いられます。イテレータの仲介によって、アルゴリズムはコンテナの構造を意識せず、あたかもポインタによるアクセスであるかのようにコンテナ内の要素をアクセスできるわけです。

イテレータ(Iterator)の分類

STLではイテレータを次の5つに分類しています。 InputIterator,Outputiterator,ForwardIterator,BidirectionalIterator,RandomAccessIteratorというクラスが実際に存在するわけではありません。それぞれの条件を満たすオブジェクトがあればそれをたとえば"InputIteratorのカテゴリに属する"などと表現しているのです。

    +--------------------------------+
    |     RandomAccessIterator       |
    +--------------------------------+
    |     BidirectionalIterator      |
    +--------------------------------+
    |        ForwardIterator         |
    +---------------+----------------+
    | InputIterator | OutputIterator |
    +---------------+----------------+
上の階層図で、上位にあるイテレータはそれより下位のイテレータに要求される機能を含むので、上位イテレータは下位イテレータを代替できます。たとえばアルゴリズムreplaceの引数はForwardIteratorですが、それだけでなくより上位のBidirectionalIterator,RandomAccessIteratorであってもreplaceは正しく機能します。

[InputIterator]

コンテナの中から要素を検索するアルゴリズムfindをみてみましょう。
  template<class Iterator, class T>
  Iterator find(Iterator first, Iterator last, const T& x) {
    while ( first != last && *first != x ) {
      ++first;
    }
    return first;
  }
引数firstには検索開始位置、lastには検索終了位置を与えます。アルゴリズムfindはfirstからlastに達しない範囲にあるデータの中からxと最初に一致するデータの位置を返します。このとき、 がIteratorに要求されています。逆にこれらの用件を満たすものならなんでもfindのIteratorとして使えることになります。
  int data[N];
  int* i = find(data,data+N,5);
  if ( i != data+N ) {
    // 見つかった!
  }
このように、データの参照(*i)と次の位置への移動(++i, i++)ができるオブジェクトをInputIteratorといいます。

[OutputIterator]

以下に示すのはコンテナの内容を特定の値で埋め尽くすアルゴリズムfillです:
  template<class Iterator, class T>
  Iterator fill(Iterator first, Iterator last, const T& x) {
    while ( first != last ) {
      *first = x;
      ++first;
    }
    return first;
  }
この例ではoperator*()で参照された要素に対して値を設定しています。すなわちIteratorを介してコンテナ内の要素を書き換えています。
  // a[N] を0で埋める
  int a[N];
  fill(a, a+N, 0);
この仕様(次の要素への移動とデータの変更)を満足するオブジェクトがOutputIteratorです。

[ForwardIterator]

つづいてアルゴリズムreplaceをみてみましょう:
  template<class Iterator, class T>
  void replace(Iterator first, Iterator last, const T& x, const T& y) {
    while ( first != last ) {
      if ( *first == x )
        *first = y;
      ++first;
    }
  }
アルゴリズムreplaceは要素がxと等しければそれをyに置き換えます。このとき、operator*()によって参照(*first == x)と変更(*first = y)が行なわれています。 InputIteratorとOutputIteratorの両方の用件を満たすのがForwardIteratorです。
  // a[N]内の1を0に置き換える
  int a[N];
  replace(a, a+N, 1, 0);

[BidirectionalIterator]

InputIterator,OutputIterator,ForwardIteratorは次の位置へ移動することができます。BidirectionalIteratorは前の位置に移動(後戻り)することができます。次に示すのはコンテナ内の要素の並びをひっくり返すアルゴリズムreverseです:
  template<class Iterator>
  void reverse(Iterator first, Iterator last) {
    while ( first != last ) {
      --last;
      if ( first != last )
        swap(*first++, *last);
    }
  }

  template<class T>
  void swap(T& a, T& b) { T tmp = a; a = b; b = tmp; }
BidirectionalIteratorはForwardIteratorの持つ操作に後戻り(operator--())を加えたものです。
  // a[N] の要素の並びを反転する
  int a[N];
  reverse(a, a+N);

[RandomAccessIterator]

BidirectionalIteratorはoperator++()/--()によって前進/後退できますが移動できる距離は'1'です。BidirectionalIteratorの持つ操作に任意の距離で前進/後退できる操作を加えたのがRandomAccessIteratorです。ソートされたコンテナに特定の値を持つ要素があるかを調べるアルゴリズムbinary_searchの引数に与えるイテレータはRandomAccessIteratorです:
  template<class Iterator, class T>
  bool binary_search(Iterator first, Iterator last, const T& x) {
    while ( first < last ) {
      Iterator mid = first + (last - first)/2;
      if ( x < *mid )
        last = mid;
      else
      if ( *mid < x )
        first = mid + 1;
      else
        return true;
    }
    return false;
  }
いわゆるポインタはRandomAccessIteratorに属することになりますから、binary_serchの引数としてポインタを渡すことができます。
  // ソートされたint配列array[]の中に5はあるか?
  int array[6] = { 0, 3, 4, 4, 5, 7 };
  bool result = binary_seatch(array,array+6,5);
  if ( result ) {
    // 見つかった!
  }

STLが提供するイテレータ

後述するSTLコンテナはそれぞれに対応するイテレータを返すメンバ関数を持っています。それ以外にもSTLはコンテナとは独立した"便利なイテレータ"を提供します。

[reverse_iterator]

reverse_iteratorは進行方向が通常の逆、すなわちoperator--で次の要素へ、operaotr++で前の要素へ移動します。
  // a[N] の内容を逆順に出力する
  int a[N];
  typedef reverse_iterator<int*> rit;
  rit first(a+N); // 末尾から
  rit last(a);    // 先頭に向かって...
  while ( first != last ) {
    cout << *first << ' ';
    ++first; // ++でひとつ戻る
  }

[istream_iterator,ostream_iterator]

入力ストリームistreamはoperator>>によってストリーム内のデータを取り出すことができます。
  int n;
  cin >> n;
istream_iteratorはoperator*がストリームのoperator>>を呼び出すことによってストリームからデータを取り出します。入力ストリームをInputIterator化したクラスです。
  cout << "input some integers:" << flush;
  typedef istream_iterator<int> input;
  input first(cin); // cinから読み出す
  input last;       // 引数なしでコンストラクトするとEOFのマーカとなる
  // cinから入力された数値の合計を求める
  int sum = 0;
  while ( first != last )
    sum += *first++;
  cout << "total=" << sum << endl;

  実行結果:
    input some integers:
    1
    2
    3
    4
    5
    ^Z
    total=15
同様に出力ストリームをOutputIterator化したのがostream_iteratorです。
  // a[N]の内容をプリントする。
  int a[N];
  // ostream_iteratorのコンストラクタには
  // 出力先、および要素間の区切り文字列(デリミタ)を指定する。
  copy(a, a+N, ostream_iterator<int>(cout," "));

[insert_iterator,front_insert_iterator,back_inssert_iterator]

コンテナに要素を挿入するメンバ関数insert,push_front,push_backを使ってコンテナへの要素の挿入操作をOutputIterator化したのがinsert_iterator,front_insert_iterator,back_insert_iteratorです。
  // a[N] の内容をvectorにコピーする
  int a[N];
  vector<int> v;
  copy(a, a+N, back_insert_iterator< vector<int> >(v));
ヘルパ関数inserter,front_inserter,back_inserterを使うとコードが簡単になります。
  // a[N] の内容をvectorにコピーする
  int a[N];
  vector<int> v;
  copy(a, a+N, back_inserter(v));

[イテレータの作り方]

operator*,operator++などを適切に定義すれば、ユーザ定義のイテレータを作ることができます。イテレータを作るときは、ヘッダ<iterator>に定義されているstruct iteratorの派生クラスとしてください。
  template<class Category, class T, class Distance = ptrdiff_t,
           class Pointer = T*, class Reference = T&>
  struct iterator {
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
};
struct iteratorのテンプレート引数は5つあります。 それぞれの意味は上記のとおりですが、CategoryとT以外は
  Distanse  = ptrdiff_t
  Pointer   = T*
  Reference = T&
とデフォルトが定められています。

operator=,==,!=,(),++,--などのメンバ関数を"ポインタと同様にふるまう"ように実装すればイテレータのできあがりです。

  /*
   * ユーザ定義イテレータのひな型
   *
   * - このひな型はイテレータを定義する際のヒントとして作成した。
   *   必ずしもこのひな型に従う必要はない。
   *
   * - 各関数の末尾のコメント[...]は、その関数を定義しなければ
   *   ならないイテレータが:
   *     I --- InputIterrator
   *     O --- OutputIterator
   *     F --- ForwardIterator
   *     B --- BidirectionalIterator
   *     R --- RandomAccessIterator
   *   であることを表す。
   */
  class ITER
    : public iterator<Category,T,Distance,Pointer,Reference> {
         // Distance, Pointer, Referenceはほとんどの場合省略可能
  public:
    // コンストラクタ
    ITER();                                     // [IOFBR]
    ITER(const ITER&);                          // [IOFBR]

    // コピー演算子
    ITER& operaotr=(const ITER&);               // [IOFBR]

    // 要素のアクセス
    T& operator*();                             // [IOFBR]
    T& operator[](Distance);                    // [R]

    // 移動
    ITER& operator++();                         // [IOFBR]
    ITER  operator++(int);                      // [IOFBR]
    ITER& operaotr+=(Distance);                 // [R]
    ITER& operator--();                         // [BR]
    ITER  operator--(int);                      // [BR]
    ITER& operaotr-=(Distance);                 // [R]
  }

  /*
   * グローバル関数
   */
  // 比較
  bool operator==(const ITER&, const ITER&);    // [IOFBR]
  bool operator!=(const ITER&, const ITER&);    // [IOFBR]
  bool operator< (const ITER&, const ITER&);    // [R]
  bool operator<=(const ITER&, const ITER&);    // [R]
  bool operator> (const ITER&, const ITER&);    // [R]
  bool operator>=(const ITER&, const ITER&);    // [R]

  // 演算
  ITER operator+(const ITER&, Distance);        // [R]
  ITER operator+(Distance, const ITER&);        // [R]
  ITER operator-(const ITER&, distance);        // [R]
  Distance operator-(const ITER&, const ITER&); // [R]
例として、string(文字列)を区切り文字単位に分割し、部分文字列を取り出すイテレータtokenizerを作ってみましょう。
  #include <algorithm>
  #include <string>
  using namespace std;

  class tokenizer : public iterator<input_iterator_tag,string> {
    string src_; // 分割対象となる文字列
    string sep_; // 区切り文字の集合
    string tok_; // 切り出された部分文字列
    string::size_type first_;
    string::size_type last_;
    void get_value();
  public:
    // コンストラクタ
    tokenizer() : first_(string::npos), last_(string::npos) {}
    explicit tokenizer(const string& sep) : sep_(sep) {}
    explicit tokenizer(const char* sep)   : sep_(sep) {}
    tokenizer(const string& sep, const string& src)
      : sep_(sep), src_(src) { last_ = 0; get_value(); }
    tokenizer(const char* sep, const char* src)
      : sep_(sep), src_(src) { last_ = 0; get_value(); }
    tokenizer(const tokenizer& t)
      : src_(t.src_), sep_(t.sep_), tok_(t.tok_),
        first_(t.first_), last_(t.last_) {}

    tokenizer& operator=(const tokenizer& t) {
      src_ = t.src_; sep_ = t.sep_; tok_ = t.tok_;
      first_ = t.first_; last_ = t.last_;
      return *this;
    }

    // 分割対象文字列を設定
    tokenizer& operator=(const string& src)
      { src_ = src; last_ = 0; get_value(); return *this; }
    tokenizer& operator=(const char* src)
      { src_ = src; last_ = 0; get_value(); return *this; }

    // 要素(部分文字列)の参照
    const string& operator*() const  { return tok_; }
    const string* operator->() const { return &tok_; }

    // 次の要素(部分文字列)へ
    tokenizer& operator++()
      { get_value(); return *this; }
    tokenizer  operator++(int)
      { tokenizer tmp = *this; get_value(); return tmp; }

    // 比較演算
    friend bool operator==(const tokenizer x, const tokenizer& y)
      { return x.first_ == y.first_ && x.last_ == y.last_; }
    friend bool operator!=(const tokenizer x, const tokenizer& y)
      { return !(x == y); }
  };

  void tokenizer::get_value() {
    if ( last_ == string::npos ) { first_ = string::npos; return; }
    first_ = src_.find_first_not_of(sep_,last_);
    if ( first_ == string::npos ) { last_ = string::npos; return; }
    last_  = src_.find_first_of(sep_,first_);
    string::size_type n =
      (last_ == string::npos) ? last_ : last_-first_;
    tok_ = src_.substr(first_, n);
  }

  /*
   * お試し
   */
  int main() {
    string in = "this string will be separated into tokens";
    tokenizer first(" ",in); // inを" "を区切りとして分割する
    tokenizer last;          // デフォルトインスタンスはエンドマーカ
    while ( first != last )
      cout << *first++ << ',';
    cout << endl;
    return 0;
  }

  実行結果:
    this,string,will,be,separated,into,tokens,
イテレータはデータのアクセス手段としてだけではなく、データの生成メカニズムとして定義することもできます。
  /*
   * ユーザ定義 イテレータの例
   *
   * regression<T> 等差数列を生成する
   */
  #include <iterator>

  template<class T>
  class progression
    : public std::iterator<std::input_iterator_tag,T> {
    T curr_;  // 現在値
    T delta_; // 公差
  public:
    progression(const T& c, const T& d)
      : curr_(c), delta_(d) {}
    explicit progression(const T& c)
      : curr_(c) {}
    progression()
      {}
    progression(const progression& p)
      : curr_(p.curr_), delta_(p.delta_) {}
    progression& operator=(const progression& p)
      { curr_ = p.curr_; delta_ = p.delta_; return *this; }
    progression& operator++()
      { curr_ += delta_; return *this; }
    progression  operator++(int)
      { T tmp = curr_; curr_ += delta_; return progression(tmp,delta_); }
    T operator*() const
      { return curr_; }
    friend bool operator==(const progression& x, const progression& y)
      { return x.curr_ == y.curr_; }
    friend bool operator!=(const progression& x, const progression& y)
      { return x.curr_ != y.curr_; }
  };

  /*
   * お試し
   */
  #include <iostream>
  using namespace std;

  int main() {
    // 0 2 4 ... 18 を出力する
    progression<int> first(0,2);
    progression<int> last(20);
    while ( first != last )
      cout << *first++ << ' ';
    return 0;
  }

  実行結果:
    0 2 4 6 8 10 12 14 16 18