調べ物ついでに訳したものを掲載。
New Iterator Concepts - Boost.Iterator
新たなイテレータコンセプト
動機
直交した2つの問題(横断と、値へのアクセス)を扱う場合、単一の階層構造しか持っていない
標準のイテレータコンセプトとその要件には欠陥がある。
その結果、イテレータカテゴリで表現されるアルゴリズムの多くは要件が厳しすぎることになった。
さらに、実世界の多くのイテレータを正確に分類することができなかった。
例えば、Random Access Traversalを持つプロキシイテレータは単に
Input Iteratorカテゴリを合法に持つだけかもしれない。
したがって、ジェネリックアルゴリズムはランダムアクセスの能力を使うことができなくなる。
現在のイテレータ階層構造は、イテレータ横断(カテゴリ名)に連動するが、値へのアクセスもこっそり入っている。
以下の表は、イテレータカテゴリの現在の値アクセスの要件を要約したものである。
Output Iterator : *i = a
Input Iterator : *iはTへ変換可能
Forward Iterator : *iはT&
Random Access Iterator : i[n]はTに変換可能
イテレータの横断と値アクセスが単一の階層構造で混合されるため、
多くの有用なイテレータをうまく分類することができない。
たとえば、vector
(see issue 96 and Herb Sutter's paper J16/99-0008 = WG21 N1185)。
したがって、vector
これは非常に非直感的なので、C++のこの点は矛盾していると言える。
パラグラフ23.2.4/1では、vectorがRandom Access Iteratorをサポートするシーケンスであると言っている。
他の分類することが困難なイテレータは、イテレータの間接参照された値に
単項の関数オブジェクトを適用するアダプタであるtransform iteratorである。
timesのような単項の関数については、operator*の戻り値の型は明確に関数オブジェクトのresult_typeである必要がある。
それは典型的に参照ではない。transform iteratorでint*をラップした場合、
Random Access Iteratorがoperator*から左辺値を返すことを要求するため、
期待とは異なり、Random Access IteratorではなくInput Iteratorとなる。
3つめの例は、Boost Graphライブラリの頂点と辺のイテレータで見つかる。
これらのイテレータは頂点と辺のディスクリプタを返し、それは進行中に作成された計量のハンドルである。
それは値を返さなければならない。
その結果、それらの現在の標準イテレータカテゴリはinput_iterator_tagとなる。
それは厳密に言えば、min_element()のようなアルゴリズムでこれらのイテレータを使用することができないことを意味する。
暫定処置として、Multi-Pass Input Iteratorコンセプトは頂点と辺のディスクリプタについて
記述するために導入されたが、よりよい解決策が必要であることを概念設計の注記が示唆している。
要するに、現在の標準イテレータカテゴリに入らない多くの有用なイテレータがある。
その結果、以下のような悪いことが起こる：
- イテレータの分類ミス
- 真の参照戻り値型の必要から、ランダムアクセスか双方向かの横断の要件を分けることができないため、アルゴリズムの要件が必要以上に厳密
標準へのインパクト
TR1へのこの提案は純粋な拡張である。
さらに、新たなイテレータコンセプトは古いイテレータの要件に後方互換性がある。
また、古いイテレータは新たなイテレータコンセプトに前方互換性がある。
すなわち、古い要件を満たすイテレータは、新システムでの適切なコンセプトを満たす。
また、新たなコンセプトをモデル化するイテレータは自動的に適切な古い要件を満たす。
Working Paperへの可能(だが提案されなかった)な変更
このpaperの拡張は、我々が次の標準のためにWorking Paperに加えるいくつかの変更を示唆する。
これらの変更はTR1のための提案の形式的な一部ではない。
アルゴリズム要件への変更
中略
変更を要約すると、イテレータの横断コンセプトと、値アクセスコンセプトを分ける。
たとえば、Forward IteratorはForward Traversal Iterator、Readable Iterator、Writable Iteratorに分かれる。
イテレータの値アクセスコンセプトは以下のようになる：
イテレータの横断コンセプトは以下のようになる：
Incrementable Iterator
↑
Single Pass Iterator
↑
Forward Traversal Iterator
↑
Bidirectional Traversal Iterator
↑
Random Access Traversal Iterator
