第６章　イテレータ

イテレータのコンセプトを紹介しています。
走査の種類としてシングルパス単一方向、マルチパス単一方向、双方向、ランダムアクセスを扱っています。
イテレータのコンセプトとして、有界区間と算入区間の2つの面から逐次アルゴリズムに対する
インターフェイスを柔軟に定義しています。

6-1 読み込み可能性
　ポインタはオブジェクトにアクセスするときの重要な概念だが、これを抽象化してコンセプトとしたものが
読み込み可能性です。読み込み可能型でデータにアクセスするための関数sourceはポインタにおける
間接参照演算子「*」に当たります。

6-2 イテレータ
　DistanceTypeと擬似変換 $\rm successor$ から最も弱いイテレータを定義しています。

6-3 区間
　イテレータの集合となる区間を定義しています。また、 $\rm successor$ の機能的定義から
イテレータと整数間の足し算、イテレータ間の引き算が定義されます。

半開算入区間 $[[f, n|) \equiv {\rm counted}$ - ${\rm range}(f, n) \wedge ([[f, n|) = \{{\rm successor}^k(f) \mid 0 \leq k < n\})$

6-4 読み込み可能区間
　イテレータからなる区間について、区間のすべてのイテレータが読み込み可能ならば
区間は読み込み可能と呼びます。
読み込み可能区間に対して、述語を条件とする検索や、部分結合的演算に対する簡約アルゴリズム、
区間の比較などについて考察しています。

6-5 増加区間
　順序が与えられた時に増加していく区間に関するアルゴリズムについて記述しています。

6-6 順方向イテレータ
　successorに正則性を仮定することで、一つの区間に２つ以上のイテレータを保持することができます。
このイテレータを順方向イテレータと呼びます。successorの正則性により、２分探索が有効に働きます。

6-7 インデックス付きイテレータ
　イテレータへの整数の加算、およびイテレータ～イテレータの減算が高速なイテレータです。

6-8 双方向イテレータ
　逆方向に進むpredecessoprを持つイテレータです。

6-9 ランダムアクセスイテレータ
　インデックス付きイテレータと双方向イテレータの両方の性質をもつイテレータを
ランダムアクセスイテレータと呼びます。
　ランダムアクセスイテレータはインデックス付きイテレータで代用できます。

6-10結論
　代数学において半群、モノイド、群といったコンセプトの階層があるように、イテレータにも
イテレータ、順方向イテレータ、インデックス付きイテレータといったコンセプトの階層が存在
します。

補題6.1 $0 \leq k \leq j$ に対し、仮定より $0 \leq k \leq i$ となることから。

補題6.2 帰納法により $f + n = {\rm successor}^n(f)$ をまず示す。これと補題3.1より。

補題6.3 ${\rm successor}({\rm successor}^n(f)) = {\rm successor}^{n + 1}(f)$ と半開区間、閉区間の定義より。

補題6.4　 $[f, l) = [[f, l - f|)$ より ${\exists}k(0 \leq k \leq l - f), i = {\rm successor}^k(f)$ 。
よって $[f, i)$ は有界区間。 $[i, l)$ についても同様。

補題6.5　 $[[i, 0|)$ は ${{\rm successor}^k(f) \mid 0 \leq k < 0} = \emptyset$ より明らか。
後半は $[[i, 0|) = [i, i)$ から従う。

補題6.6, 6.7　自明。

補題6.8
１行目
$\forall{m}\in{[f, l)}\wedge\forall{j}\in{[f, m)}\Rightarrow{j}\in{[f, l)}$ より
２行目も同様

タグ：

+ タグ編集

最終更新：2013年07月18日 22:13

プログラミング原論／Elements of Programming Wiki