Help us understand the problem. What is going on with this article?

[c++,boost] Eric Niebler's range 3.0の基本設計思想

More than 5 years have passed since last update.

概要

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対で実装する。

kktk-KO
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした