イテレータ | Programming Place Plus　C++編【標準ライブラリ】　第１４章

この章の概要

この章の概要です。

• イテレータ
• 配列にとってのイテレータ
• イテレータのカテゴリ
• advance関数
• distance関数
• iter_swap関数
• イテレータの変換
• 練習問題
• 参考リンク
• 更新履歴

イテレータ

イテレータ（反復子）は、コンテナに含まれる複数の要素に対する反復処理を行うためのオブジェクトです。反復処理というのは、各要素に順番に何らかの処理を行っていく操作のことを言い、走査とも呼ばれます。

STLコンテナの場合、イテレータは、コンテナが持つ beginメンバ関数 と endメンバ関数 によって取得できます。beginメンバ関数は、コンテナの先頭要素を指すイテレータを、endメンバ関数は、コンテナの末尾要素の１つ先を指すイテレータを返します。

beginメンバ関数や endメンバ関数が返す型は、コンテナごとに別個に定義された型であり、たとえば、vector にとってのイテレータと、map にとってのイテレータとでは別の型になります。このように別の型になっているのは、走査の方法はデータ構造の種類によって異なるものだからです。

beginメンバ関数や endメンバ関数が返す型は、具体的には、std::Container<>::iterator型、あるいは std::Container<>::const_iterator型です（Container には、vector や map などのコンテナクラス名が入る）。

以降、std::Container<>::iterator型を iterator型、std::Container<>::const_iterator型を const_iterator型と表記します。

非const関数版の begin/endメンバ関数の場合は、iterator型を返し、const関数版のbegin/endメンバ関数の場合は、const_iterator型を返すということですが、iterator型から const_iterator型へは、暗黙的に型変換できるので、つねに、const_iterator型で受け取ることは可能です。

逆に、const_iterator型から iterator型への暗黙の型変換はできません（明示的な型変換を行う方法について、「イテレータの変換」の項で取り上げます）。

イテレータは、ポインタを真似て作られているので、使用感はポインタと似ています。指し示す先の要素の型を T とすると、iterator が T*型のようなものであり、const_iterator は const T*型にあたります。そのため、const_iterator の場合は、指し示している先の要素を書き換えることができません。

iterator や const_iterator がどのように定義・実装されているかは、標準ライブラリの実装者に裁量に任されています。vector の場合、本当に iterator が T* の typedef であり、const_iterator が const T* の typedef であることがあり得ますが、そうでないこともありますから、イテレータを本当にポインタのように扱ってはいけません。使用感が似ているのであって、同一のものではありません。

一例として、イテレータを使って、list を走査する例を示します。

#include <iostream>
#include <list>

int main()
{
    typedef std::list<int> IntList;

    const int table[] = {0, 1, 2, 3, 4};

    IntList lst(table, table + 5);

    IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::flush;
}

実行結果

0
1
2
3
4

list の代わりに、vector や deque、set や map といった、他の STLコンテナを使っても同じです。

配列にとってのイテレータ

配列は、STLコンテナではないですし、そもそもクラスですらないので、beginメンバ関数や endメンバ関数はありませんが、ポインタをイテレータとみなして、同等の処理を行うことが可能です。

beginメンバ関数や endメンバ関数が使わなくても、次のように、イテレータと同じ形のままプログラムを書けます。

#include <iostream>

int main()
{
    const int table[] = {0, 1, 2, 3, 4};

    const int* const itEnd = &table[5];
    for (const int* it = table; it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::flush;
}

実行結果

0
1
2
3
4

イテレータのカテゴリ

STLコンテナから得られるイテレータについて、その使い方を考えても分かるように、対象のデータ構造によって、イテレータが持つ機能には違いがあります。

たとえば、vector に対するイテレータであれば「ｎ個先の要素を指すように一気に進ませる」ことができます。一方、set に対するイテレータでは、「１つ先の要素へ進ませる」ことはできますが、「ｎ個先」となると直接的には実現できず、「１つ先へ」をｎ回繰り返すしかありません。この例は、添字を使ったランダムアクセスができる構造と、できない構造の違いから来ています。

結局、set でも「ｎ個先の要素を指すように進ませる」ことはできている訳ですが、その効率には大きな差があります。vector では「１個先」でも「1000個先」でも、その効率に違いがありませんが、set では 1000倍違う訳です。

STL では、イテレータの機能性を、５つのカテゴリで表現しています。

• 入力イテレータ
• 出力イテレータ
• 前方イテレータ
• 双方向イテレータ
• ランダムアクセスイテレータ

while (true) {
    *it = 999;
    ++it;
}

while (it != container.end()) {
    *it = 999;
    ++it;
}

advance関数

std::advance関数を使うと、イテレータを任意の要素数分だけ、先へ進めたり（その機能を持ったカテゴリのイテレータであれば）前に戻したりできます。advance関数は、<iterator> という名前の標準ヘッダに含まれています。

advance関数は、第１引数にイテレータを指定し、第２引数に進めたい要素数を指定します。戻り値はなく、第１引数に指定したイテレータ自体が変更されることで、結果を得ます。

第１引数に指定できるのは、入力イテレータカテゴリおよびそこから派生しているカテゴリに属するイテレータです。なお、この引数は参照になっており、渡したイテレータ自体が変更されます。

第２引数には負数を指定できますが、実際に手前側に移動できるのは、その機能を持っている双方向イテレータと、ランダムアクセスイテレータに限られます。

#include <iostream>
#include <list>
#include <iterator>

int main()
{
    typedef std::list<int> IntList;

    const int table[] = {0, 1, 2, 3, 4};

    IntList lst(table, table + 5);

    IntList::const_iterator it = lst.begin();
    std::advance(it, 3);
    std::cout << *it << std::endl;
    std::advance(it, -1);
    std::cout << *it << std::endl;

    const int* p = table;
    std::advance(p, 3);
    std::cout << *p << std::endl;
    std::advance(p, -1);
    std::cout << *p << std::endl;
}

実行結果

3
2
3
2

advance関数は、イテレータがコンテナの末尾を超えるかどうかを判断できないので、末尾を超えてしまうような移動は、未定義の動作になることに注意してください。当然、先頭よりさらに手前側への移動も同様です。

advance関数は、イテレータのカテゴリを判断して、それに応じた実装が使用されるようになっています。

たとえば、第１引数に、ランダムアクセスイテレータ以外のイテレータを指定し、第２引数に、1 より大きい値（または -1 より小さい値）を指定した場合、++演算子や –演算子を繰り返し実行することによって、指定した要素数分の移動を実現します。そのため、効率面では大きく劣ることに注意してください。advance関数を使うことで、イテレータカテゴリの違いを気にせず、移動という処理を汎用化できますが、特別、性能がよくなるわけではありません。

【上級】これを実現するために、特性という仕組みが利用されています。

distance関数

std::distance関数を使うと、２つのイテレータ間の距離を調べられます。distance関数は、<iterator> という名前の標準ヘッダに含まれています。

distance関数には、２つのイテレータを指定しますが、ともに同じコンテナの要素を指す、入力イテレータ（派生カテゴリでも良い）で無ければなりません。

また、第１引数で指定したイテレータの方が、第２引数で指定したイテレータより手前側または同じ位置を指している必要があります。この要件を満たしていない場合、未定義の動作になります。

#include <iostream>
#include <list>
#include <iterator>

int main()
{
    typedef std::list<int> IntList;

    const int table[] = {0, 1, 2, 3, 4};

    IntList lst(table, table + 5);

    IntList::const_iterator it = lst.begin();
    const IntList::const_iterator itEnd = lst.end();
    std::advance(it, 3);
    std::cout << std::distance(it, itEnd) << std::endl;

    const int* p = table;
    std::advance(p, 3);
    std::cout << std::distance(p, table + 5) << std::endl;
}

実行結果

2
2

distance関数は、イテレータのカテゴリを判断して、それに応じた実装が使用されるようになっています。

ランダムアクセスイテレータの場合は、単に「it2 - it1」とすることで距離を計算できるので非常に効率的ですが、他のカテゴリのイテレータの場合は、it1 が it2 に出会うまで ++演算子を適用し続けるような実装になるので、かなり重い計算になり得ます。

iter_swap関数

std::iter_swap関数を使うと、２つのイテレータが指す先にある要素同士を交換できます。iter_swap関数は、<algorithm> という名前の標準ヘッダに含まれています（この関数は iterator には含まれません）。

２つのイテレータは、前方イテレータカテゴリに属している必要があります。それぞれが、別のコンテナを指すイテレータであっても構いませんが、要素同士は相互に代入できる型でなければなりません。

#include <iostream>
#include <list>
#include <algorithm>

int main()
{
    typedef std::list<int> IntList;

    int table[] = {0, 1, 2, 3, 4};

    IntList lst(table, table + 5);

    IntList::iterator it = lst.begin();
    const IntList::iterator itEnd = lst.end();
    std::advance(it, 3);
    std::iter_swap(lst.begin(), it);
    for (it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    int* p = table;
    std::advance(p, 3);
    std::iter_swap(table, p);
    for (p = table; p != table + 5; ++p) {
        std::cout << *p << " ";
    }
    std::cout << std::endl;
}

実行結果

3 1 2 0 4
3 1 2 0 4

イテレータの変換

iterator から const_iterator へは、暗黙的に型変換できますが、逆はできません。キャストもできません。

「const は積極的に使うべきである」というのが C++ の基本であり、その考え方をイテレータにも適用すれば、const_iterator が使えるのなら、iterator よりも優先して使うべきだと言えます。しかし、STL の関数の中には、変更が必要でないのにも関わらず、引数の型が const_iterator ではなく iterator になっているものがあります。そのため、const_iterator から iterator へ、簡単に変換できることが望ましいのです。

残念ながら、const_iterator から iterator へ変換する分かりやすい方法はありませんが、advance関数と distance関数を利用することで、目的を果たすことは可能です。

#include <iostream>
#include <list>
#include <iterator>

int main()
{
    typedef std::list<int> IntList;

    const int table[] = {0, 1, 2, 3, 4};

    IntList lst(table, table + 5);

    // 4番目の要素を指す const_iterator を作る
    IntList::const_iterator cit = lst.begin();
    std::advance(cit, 3);

    IntList::iterator it = lst.begin();  // 先頭を指す iterator
    std::advance(it, std::distance<IntList::const_iterator>(it, cit));  // const_iterator を iterator に変換

    lst.insert(it, 9);

    const IntList::const_iterator citEnd = lst.end();
    for (cit = lst.begin(); cit != citEnd; ++cit) {
        std::cout << *cit << " ";
    }
    std::cout << std::endl;
}

実行結果

0 1 2 9 3 4

list の insertメンバ関数に渡すイテレータは、const_iterator ではなく iterator です。このプログラムで言えば、it を渡すことはできますが、cit を渡すことはできません。

const_iterator から iterator に変換するには、以下の手順を取ります。

1. 目的の要素を指す const_iterator がある（作る）
2. 先頭の要素を指す iterator を作る
3. distance関数の第１引数に 2 で作った iterator を、第２引数に 1 の const_iterator を指定し、距離を得る
4. 3 で得た距離を指定して advance関数を呼び出し、2 で作った iterator を進める

結果、iterator は、const_iterator と同じ位置を指すようになりますから、変換（というか複製が）できたことになります。

少々厄介なことに、distance関数に渡す２つの引数が、それぞれ iterator と const_iterator になるため、型が一致せず、テンプレート実引数の型推測に失敗します。そこで、明示的にテンプレート実引数を指定する必要があります（このとき、当然 const_iterator の方を指定します）。

なお、advance関数も distance関数も、ランダムアクセスイテレータであれば効率的ですが、他のカテゴリのイテレータの場合は、非効率な処理になることに注意が必要です。そのため、そもそも const_iterator を使うことを諦めることも、有力な手段として検討するべきです。