概要
Boost Range 2.0の作者であるEric Nieblerが range 3.0を継続的に開発している(github)。
Ericによるとrange3.0はC++標準規格入りを目指している。
最近の彼のブログポストによると、Range3.0に大きな変更が入ったらしいので、この機に解説してみる。
ほとんどの内容は彼のブログポストとgithub内のドキュメント、特にC++標準規格へのプロポーザルに依っている。
Rangeの基本設計思想
EricはRangeをC++用に設計するに当たって、いくつかの例、特にD言語のRangeに注目し、その改善すべき点を見いだした。
D言語の最も簡単なRangeは基本的には次のメンバ関数から成る。
front()
empty()
pop()
それぞれの意味は推して図るべし。
重要な事は、D言語のRangeは要素の取り出しやRange範囲の操作はできるが、Rangeの"場所"を参照できない。
Ericは、上に述べた理由から、D言語のRangeはいくつかのアルゴリズムの計算オーダーが大きくなってしまっていると述べている(参照)。
そのために、D言語のRangeを使ってC++のIteratorを同じ計算量を保ったまま実装する事は出来ないとしている（逆はできる）。
以上に述べた理由から、EricはRangeに"場所"の情報を持たせるべきだとした。
現在までのC++について考えると、最も簡単で、後方互換性のあるRangeの作り方はIteratorのbegin/endペアをRangeとする事である。
実際、Boost Range2.0ではネイティブにRangeを作る方法が無い場合はboost::make_iterator_rangeを使ってRangeを作っている。
また、他のRangeの実装として、beginとRangeのサイズのペアや、beginとRangeが空である事を判定するPredicateのペア等があり得る。
Ericはこれらの実装も含めて抽象化すべきだと判断した。
理由はその方が速いコンテナ(Ericはdeque等を挙げている)があるためだ。
また、その様な抽象化したレイヤーでアルゴリズムを実装しても、パフォーマンスが劣化しない事をEricは確認している。
この様な"場所"の情報を持ったRangeの抽象化のために、Ericはbegin/endのIterator/Iterator対の代わりに、Iterator/Sentinel対という考え方を持ち出した。
この考え方の元では、例えば従来のIteratorのbegin/endペアによるRangeの実装は
Iterator = 従来のIterator
Sentinel = 従来のIterator
となり、beginとRangeのサイズのペアでは
Iterator = 従来のIterator + カウンターのラッパー
Sentinel = 空
となる。
まとめ
Rangeは"場所"の情報も持つ。
Iterator/Sentinel対で実装する。