コンテンツへスキップ
Topos Uranos
日本語

配列

要約

ここまで、このコースのデータはどれも自分の変数に、自分の名前で住んできた。しかし同じ型の多くのデータ、たとえば一週間の気温は、一つひとつが別の名前をもっていてはループで走査できない。このレッスンでは、コースで最初のデータ構造である添字付きの列を紹介する。同じ型の要素がメモリ上の隣り合う位置に並び、零から番号が振られたものである。現代の C++ では std::array で書き、その大きさはコンパイル時に固定される。その宣言、添字の型 std::size_t、そして二つの走査、すなわち添字による走査と範囲 for 文による走査を学ぶ。単元全体を支配する規則も定める。添字は 0 から大きさ引く一までの間にあれば有効であり、ループ内の各アクセスでは、その有効性を不変条件で正当化する。規則が守られないと何が起こるか、すなわち未定義動作を示し、[] と範囲チェック付きアクセス .at() を比べる。最後に、他人のコードを読むために C 言語の配列を紹介する。

学習目標

  1. std::array を宣言し、初期化し、添字と範囲 for 文で走査できる。
  2. ループの不変条件によって、各アクセスで添字が範囲内にあることを正当化できる。
  3. 規格が検査しない [] によるアクセスと、つねに検査される .at() によるアクセスを区別し、それぞれがどんなときに適切かを説明できる。
  4. C 言語の配列を使ったコードを読み、std::array と比べたときの欠点を説明できる。

添字付きの列

多くのデータに一つの名前

ここまでに学んだことで一週間の気温の平均を計算するなら、monday、tuesday、と続けて sunday までの七つの変数と、七項の和が必要になる。一年分の気温なら変数は 365 個になり、どんなループもそれらを走査できない。ループの本体では変数の名前はつねに同じだからである。足りないのは、全体に対する一つの名前と、各要素に対する一つの番号であり、その番号をループが進める変数にできればよい。

添字付きの列とは、まさにそれである。同じ型の nn 個の要素の集まりで、メモリの隣り合う区画に次々と格納され、その位置によって指定される。この位置を添字という。数学はこの対象を知っている。有限数列 (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1}) であり、そこで aia_i は位置 ii にある要素を表す。あるいはベクトルであり、コース「代数と幾何 I」のベクトルがそれにあたる。C++ では a[i] と書き、添字には任意の整数式を使える。2、i、i + 1 などである。

なぜ零からなのか

C++ では、現在の大多数の言語と同じく、最初の要素の添字は 0、最後の要素の添字は n−1n - 1 である。理由は気まぐれな取り決めではなく、要素を見つける方法にある。列がメモリのある番地から始まり、各要素が ss バイトを占めるなら、添字 ii の要素は、先頭の番地に i⋅si \cdot s を足した番地にある。したがって添字はオフセット、つまり最初の要素から数えて飛び越すべき要素の個数である。最初の要素は自分自身から飛び越し零回の位置にある。

ここから、この単元全体を支配する定義が導かれる。nn 個の要素の列において、添字 ii が有効であるのは 0≤i<n0 \leq i < n のとき、かつそのときに限る。右側の不等式は狭義であり、列を扱うときに最も多い誤り、すなわち1 ずれのエラーの源になる。i≤ni \leq n と書いてしまうこと（正しくは i<ni < n）、あるいは 1 から始めてしまうこと（正しくは 0 から）である。nn に等しい添字は最後の要素を指すのではなく、列の直後にあって列に属さない区画を指す。