Iteratorについて

前の例会の講座でIteratorについての説明を端折ったのでここで説明しておく。

Iteratorとは、その名の通り、反復(iterate)するものである。といっても何が何だか分からないので、具体的な例で見てみることにする。

次のような関数を考える。

// 区間[first, last)に存在する要素をresultにコピーする。
void Copy(int* first, int* last, int* result)
{
    while (first != last) {
        *result = *first;
        ++first;
        ++result;
    }
}

単にint型の配列の要素をコピーするだけの関数である。firstやlastの型は本来constにすべきだが後の説明の都合により、ここではconstを付けない。*1

さて、次のような単方向リストがあるとする。

struct Node {
    Node* next;
    int data;
};

このリストに対してCopyのような関数を書くとすると次のようになる。

void CopyList(Node* first, Node* last, Node* result)
{
    while (first != last) {
        result->data = first->data;
        first = first->next;
        result = result->next;
    }
}

上のCopy関数とほとんど同じように書ける。違いは

• int*の代わりにNode*を使う
• *pの代わりにp->dataを使う
• ++pの代わりにp = p->nextを使う

の3つだ。では、この3つを配列とリストで揃えてやれば、同じ関数を配列とリストに対して適用できそうだ。

そこで次のようなクラスを定義する。

class ListIterator {
    Node* p;

public:
    ListIterator(Node* node): p(node) {}
    int& operator*() { return p->data; }
    ListIterator& operator++() { p = p->next; return *this; }
    bool operator!=(const ListIterator& rhs) const { return p != rhs.p; }
};

これを使ってCopyListを次のように書きなおす。

void CopyList(ListIterator first, ListIterator last, ListIterator result)
{
    while (first != last) {
        *result = *first;
        ++first;
        ++result;
    }
}

ListIteratorは、p->dataやp = p->nextの形から*p、++pの形にもっていく役割を果たしている。これで上の3つの違いの内、2つは解決できた。残ったひとつはテンプレートを使って解決できる。

template <typename Iterator>
void Copy(Iterator first, Iterator last, Iterator result)
{
    while (first != last) {
        *result = *first;
        ++first;
        ++result;
    }
}

これで配列にもリストにも適用できるCopy関数が手に入った。

// array1の先頭から10要素をarray2にコピーする
Copy(array1, array1 + 10, array2);

// first_nodeからlast_nodeまでをlist2にコピーする
Copy(first_node, last_node, list2);

ところで、このCopy関数はさらに一般化することができる。first, lastの型とresultの型が同じである必要はないからだ。

template <typename Iterator1, typename Iterator2>
void Copy(Iterator1 first, Iterator1 last, Iterator2 result)
{
    while (first != last) {
        *result = *first;
        ++first;
        ++result;
    }
}

こうしておけば、配列からリストに要素をコピーしたり、逆に、リストから配列に要素をコピーするといったことができる。

さらに、イテレータが必ずしもコンテナの要素をiterateしなければならないわけではない。例えば、次のような変なイテレータ作ることができる。

class EvenIterator {
    int n;

public:
    EvenIterator(int n0): n(n0) {}
    int& operator*() { return n; }
    EvenIterator& operator++() { n += 2; return *this; }
    bool operator!=(const EvenIterator& rhs) const { return n != rhs.n; }
};

そして、次のように呼び出すと

Copy(EvenIterator(0), EvenIterator(14), array);

arrayには 0, 2, 4, 6, 8, 10, 12 が代入される。意味のない例に見えるかもしれないが、状況によってはイテレータのこういった使い方が便利なときもある。実際に、C++の標準ライブラリにはistream_iteratorやostream_iteratorというものがあって、これらは入出力ストリームをイテレータ化したものである。

このように、ListIteratorのようなイテレータを用意してやれば、次の要素に移動できて、要素を参照できて、要素に代入できる集合ならなんでも同じ関数を使うことができる。

実はここで述べてきたイテレータはForwardIteratorという種類のもので、他にも--ができるBidirectionalIteratorや、ランダムアクセスができるRandomAccessIteratorなどがある。さらに、代入ができないInputIteratorや、参照のできないOutputIteratorのように、ForwardIteratorよりも制限のきついイテレータもある。

最後に、ここに挙げたコードがちゃんと動くかどうかは確認していないので、もし動かないことを発見した人がいればこっそり教えてほしい。

*1:constなイテレータの説明を書くのが面倒なので