ふと、こんなことを考えた。
うーむ、C++ のイテレータが C# にも欲しくなってきた。
— アエトス・トリスメギストス (@aetos382) 2017年12月27日
そこから始まる、イテレーターについての考察。
Iterator パターン
GoF のデザイン パターンのひとつに、Iterator パターンというのがある。
コンテナ オブジェクトの要素を列挙する手段を独立させることによって、コンテナの内部仕様に依存しない反復子を提供することを目的とする。
だそうである。
上のクラス図でいう、Aggregate が抽象的なコンテナ インターフェイス（コレクション）で、ConcreateAggregate が具体的なコンテナ型。
Iterator が抽象的なイテレータ インターフェイスで、ConcreteIterator が具体的なイテレータ型。
.NET でいうと…
| クラス図 | .NET の場合 |
|---|---|
| Aggregate | IEnumerable<T> |
| ConcreateAggregate | List<T> など |
| iterator() | GetEnumerator() |
| Iterator | IEnumerator<T> |
| ConcreteIterator | List<T>.Enumerator など |
| next() | MoveNext() |
| hasNext() | MoveNext() |
というように、割と素直に対応する。
従って、IEnumerable<T> / IEnumerator<T> は、Iterator パターンの実装である、ということになる。
Java の Iterable<T> / Iterator<T> も、だいたい似たようなものだ。
なお、ややこしいことに、C# では yield return によって IEnumerable<T> を生成するメソッドのこともイテレーターと呼んだりする。
が、本記事中では、イテレーターと言えば IEnumerator<T> のことを指すものとする。
C++ のイテレーター
C++ のイテレーターはちょっと毛色が異なる。
C で、配列の要素を指すポインターを使って、配列を反復処理していたのを高度化させたものが、C++ のイテレーターである。
.NET や Java では、イテレーターを使ってコレクションの要素を書き換えることはできないが、C++ ならばできる。
また、ある要素の前の要素を指し示したり、ポインターと同じように、i + 3 のように数値を足すことで 3 つ先の要素にジャンプできたりもする。
C++ のイテレーターは、それが備える機能によっていくつかのクラスに分けられる。
以下のどのクラスであっても、コレクションのある要素を指しているイテレーターを、次の要素を指すように進める（Iterator パターンでいうところの next()）はできる。
C++ はダック タイピングな言語なので、Iterator パターンでいうところの、すべてのイテレーターが継承すべき抽象的な Iterator クラスのようなものはない。*1
が、強いて言うならば、Input Iterator が、Iterator パターンに相当すると言える。
Random Access Iterator
Bidirectional Iterator の機能に加え、i + 3 で 3 つ先の要素を指すイテレーターを得たり、i += 3 で 3 つ先の要素に進めたりできる。*2
シングル パスとマルチ パス
雑にイテレーターのクラスについて説明したが、もうひとつ、重要な性質がある。
いま調べていて初めて知ったのだが、Input Iterator と Output Iterator には、シングル パスの保証しかなく、Forward Iterator 以上であれば、マルチ パス保証があるのだそうだ。うん、何のことやらわからんね。*3
どうも、「シングル パス保証しかない」ということは、同一のコレクションを指す複数のイテレーターがある時に、そのうちの一つでインクリメント*4をすると、他のイテレーターが無効になる可能性がある（そのような実装が許される）らしいのだ。
ざっくり言うと、シングル パス保証しかないイテレーターでは、イテレーターを保存しておいて後で使うということはしない方がいいみたいだ。
値型と参照型
なんでイテレーターの文脈でこんな話が出てくるんだと思われるかもしれないが、まぁ聞いて頂きたい。
.NET には、値型と参照型がある。int とか DateTime といった構造体や列挙型は値型で、string やインターフェイスやデリゲートや、その他のオブジェクトは参照型である。*5
値型とは、そのオブジェクトの実体そのものを扱うことができる型である。特に禁止されていない限り、コピーすることができる。
参照型とは、そのオブジェクトの実体そのものに触れることはできず、ポインター*6を通して間接的に扱うことしかできない型である。ポインターが指す先のオブジェクトにコピー機能が実装されていない限り、コピーはできない。
ポインター自体は値である。
.NET の IEnumerator<T> はインターフェイスだから参照型である。一般的にコピーはできない。
C++ のイテレーターはポインターの親戚なので値であり、コピーができる。
最初のつぶやきはそういうわけで、.NET でも IEnumerator<T> のある時点の状態をコピーして保存しておいて、そこから再度列挙し直すということをやりたいな、と思ったのであった。
が、IEnumerator<T> は参照型であって、コピーが作れないので、状態を保存しておくということはできないのだ。残念。
なお、「一般的には」コピーできない、としつこく言っている点に注意されたい。
コピーして過去の値を保存しておけるような IEnumerator<T> を作ることは可能である。
が、すべての IEnumerator<T> が過去の状態を保存しておけるわけではない、ということだ。
一方、C++ のイテレーターは、（明示的に禁止されない限り）基本的にはすべてが、コピーして状態を保存しておける（たぶん）。
イテレーターとジェネレーター
これまで、ずっと「イテレーター」と言ってきたのだが、Wikipedia を見ると、どうやらジェネレーターというのもあるらしい。
イテレータ（英語: iterator）とは、プログラミング言語において配列やそれに類似する集合的データ構造（コレクションあるいはコンテナ）の各要素に対する繰り返し処理の抽象化である。
ジェネレータは、プログラムにおいて、数列の各要素の値などを次々と生成（ジェネレート）し他の手続きに渡す、という機能を持っている手続きである。
また、ジェネレーターの記事には、
イテレータは、コンテナに含まれる値ひとつひとつに対して走るジェネレータの一種である。
とも書いてあるので、どうやら、ジェネレーターの方がより抽象的で広い概念であるようだ。
というわけで、今後は「イテレーター」という言葉は「何らかのコレクションの要素を指し示すもの」という意味に限定することにする。
そうしてみると、IEnumerator<T> というのは、必ずしもコレクションに結び付くわけではない（yield return で生成される場合など）ので、これは（一般的には）イテレーターではなくジェネレーターなのだ。
冒頭で挙げた Iterator パターンも、この定義に従えばジェネレーターである。
ジェネレーターだからといってイテレーターではないということではない点に注意されたい。ジェネレーターの中にはイテレーターも含まれる。
対して、C++ のイテレーターは、狭義の意味でのイテレーターであると言ってもよさそうな気がする。
イテレーターは、それ自身の寿命よりも長寿命のコレクションに属している。だから、保存しておいて後で使ったり、前の位置に戻したりすることができる。
ジェネレーターは、それ自体が単一の値を抱え込んでいて、外部の何かに属しているわけではないものがある（yield return なんかはそう）。なので、保存しておいたり、前の位置に戻したりすることは、一般にはできないのだ。「前の値」などというものは、もう消えてしまっていてどこにもない（かもしれない）のだから。
ということは、IEnumerator<T> をラップして、状態を保存しておけるイテレーターを作るとするならば、MoveNext() を呼ぶごとに Current の値を保存しておく必要がありそうだ。
一見、ジェネレーターの方が機能が足りないように見えるが、制約が緩いということは活用の幅が広いということでもある。
もしも .NET の IEnumerator<T> が最初からコピーをサポートしていたら（サポートしなければならないという制約があったとしたら）、こんなに活用されることはなかっただろう。
余談：JavaScript
JavaScript には、イテレーターとジェネレーターの両方がある。
developer.mozilla.org
JavaScript でいうところのイテレーターというのは、前節の定義によれば一般的にはジェネレーターである。
そして、JavaScript のジェネレーターというのは、イテレーターを生成するための関数の糖衣構文である。
つまりは C# で yield return を含むメソッドのこともイテレーターと呼ぶように、JavaScript では yield を含む関数をジェネレーターと呼び、それによって生成されるオブジェクトをイテレーターと呼んでいるのである（C# でも yield return を使わなくても IEnumerable<T> が作れるのと同じように、JavaScript でもジェネレーター機能を使わなくてもイテレーター オブジェクトは作れる）。
そして、ジェネレーター関数によって生成されるイテレーター オブジェクトは、一般的にはジェネレーターと呼ばれることもある、のである。
わけわからんな。
ジェネレーター関数は、イテレーターのファクトリーとして働く、特別な種類の関数です。
なお、JavaScript では、ユーザー定義の値型は作れないので、イテレーターは一般にコピー可能ではない。
で、結局何がしたかったの？
ちょっと、パーサー的なものを作ってみようかと思っている。
