C++ イテレータ [C++ Reference]

- C++ イテレータ
  - イテレータの分類
  - 補助イテレータ関数

C++ イテレータ

イテレータはシーケンスの要素にアクセスするために用いられ、ポインタと似た用途で用いることができます。たとえばベクタの要素を一つ一つたどるのにイテレータを利用することができます。

次のコードはイテレータを生成し、ベクタとともにイテレータを使用する方法を示しています：

    vector<int> the_vector;
    vector<int>::iterator the_iterator;
 
    for( int i=0; i < 10; i++ ) the_vector.push_back(i);
    int total = 0;
    the_iterator = the_vector.begin();
    while( the_iterator != the_vector.end() ) {
      total += *the_iterator;
      ++the_iterator;
    }
 
    cout << "Total=" << total << endl;

ここで注目したいのは、コンテナ内の要素にイテレータを逆参照することによってアクセスできる点です。

NOTES: 古い値を利用しないのであれば、後置インクリメント演算子（iter++）よりも前置インクリメント演算子（++iter）を用いるべきです。
後置インクリメントは一般的には下記の様に実装されています：

  Iter operator++(int)
  {
    Iter tmp(*this); // store the old value in a temporary object
    ++*this;         // call pre-increment
    return tmp;      // return the old value
  }

明らかに前置インクリメントよりも効率的ではありません。

イテレータの分類

すべてのイテレータが同じ機能を持っているわけではありません。読み込みと書き込みでは求められる機能は異なります。
ランダムアクセスは vector に対しては効果的で便利ですが、一方で list に対しては高負荷な操作です。
このような理由から、イテレータはそれぞれの機能によって5つに分類されます：

イテレータのカテゴリ	内容	提供元
input_iterator	前方向に値を読み込む。イテレータ自身はインクリメント、比較、逆参照可能。	istream
output_iterator	前方向に値を書き込む。イテレータ自身はインクリメント、比較、逆参照可能。	ostream, inserter
forward_iterator	前方向に値を読み書きする。これはinputイテレータとoutputoイテレータの機能を合わせたものにイテレータの値を格納する機能を追加したものである。
bidirectional_iterator	前後方向に値を読み書きする。forwardイテレータと似ているが、インクリメントもデクリメントもできる。	list, map, multimap, set, multiset
random_access_iterator	ランダムアクセスで読み書きする。もっとも強力なイテレータで、両方向イテレータにポインタの演算とポインタの比較の機能を追加したものである。	array, deque, string, vector

STLコンテナは各々一つのイテレータの分類と結びついていて、STLアルゴリズムは特定のカテゴリのイテレータを利用している。

たとえば、ベクタはランダムアクセスイテレータと結びついている。これはベクタではランダムアクセスを必要とするアルゴリズムを利用することができることを意味している。ランダムアクセスイテレータは他のイテレータの機能を包含しているので、ベクタは他のイテレータと結びついたアルゴリズムを利用することもできる。

    vector<int> the_vector(10);
 
    // generate_n requires output_iterator
    generate_n(the_vector.begin(), 5, rand);
 
    // fill requires forward_iterator
    fill(the_vector.begin()+5, the_vector.end(), 100);
 
    // random_shuffle requires random_access_iterator
    random_shuffle(the_vector.begin(), the_vector.end());
 
    // copy requires input_iterator
    copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));
 
    // reverse_copy requires bidirectional_iterator
    reverse_copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));

補助イテレータ関数

<iterator>ヘッダファイルには2つの補助関数が定義されている。

  void advance( input_iterator& pos, Dist n );

advance()ではposがn要素分前方向（または後方向）に移動することができます。
両方向イテレータないしランダムアクセスイテレータではnは後方向に移動するために負になってもかまいません。
ランダムアクセスイテレータでは、advance()は一定時間で動作します。（単純にpos+=nを呼ぶだけ）
他のイテレータではadvance()は線形複雑度で更新されます。（++posがn回呼び出される）

  typename iterator_traits<input_iterator>::difference_type
  distance( input_iterator pos1, input_iterator pos2 );

distance()は2つのイテレータ間の距離を返します。
ランダムアクセスイテレータではdistance()は一定時間で動作します。（単純にpos2 - pos1を返す）
他のイテレータではdistance()は線形時間で動作します。（pos1がpos2に到達するまでインクリメントを繰り返し、インクリメントの回数を返す）