C
C++
初心者

配列のインデックスは0,1,どちらから始まる方が良い?


「配列のインデックスってなんで0から始まるの?」という疑問

長さ$n$の配列の最後の要素を$a[n-1]$と書いていたが、 「$a[n]$の方が間違えにくいのになぁ」と思ったので、

多くの言語で配列のインデックスが$0$から始まる理由について調べ、$0$で始まるものと$1$で始まるものの利点や欠点を比較した。


TL;DR

0-based indexing について

・時間や距離に関するベクトルとして利用するには便利

・配列の個数を使ったインデックスの計算で間違い(Off-by-oneエラー)が起きやすいので、注意する必要がある

・$a[-i]$のように逆順でのアクセスができるとき、 $(-2≦k<2)$のように連続した値でアクセスできる。(1-basedでは$a[0]$が不正になる)

1-based indexing について

・通常の「数や文字の列」として利用するには便利

・配列の個数を使ったインデックスの計算で間違い(Off-by-oneエラー)が起きにくい

以下は、配列のインデックスが0から始まる理由について、調べてみたもの


1. 言語に依る・歴史的経緯より

そもそも配列(みたいなデータ構造)のインデックスが0から始まる言語もあれば、1から始まる言語もある。

例を挙げると、COBOL, PL/I, RPG, FORTRAN, BASIC, R, Lua, Julia など、は1から始まる

C/C++の場合、配列の設計にポインタ演算を直接利用しているので、0-based indexing

(配列は「連続したメモリ空間の先頭アドレス」で実装され、配列へのアクセス演算子[]は「アドレスへの足し算」で実装されている)


2. 自然数が0から始まるから

え、自然数って1からじゃないの?よくわかんない。

集合によって自然数を定義する際に、0から始めるとなんかうれしいらしい。

配列の要素へアクセスするための関数(もしくは文法)で、インデックスの型が自然数と定められている言語はあまりない気が......

あと、ほとんどの言語がインデックスの型がintなのに負の数をとれないよね......


3. ダイクストラ先生の「Why numbering should start at zero」より

Why numbering should start at zero

より、二つの主張がされている。

1. 自然数の部分列は$(m≦i<k)$と表記するとわかりやすい(ただし、 $m≦k$)

2. 1.の表記を採用するとき0-based indexing にすると、長さ$n$の列が$(0≦i<n)$と表記できるのでわかりやすい

例を挙げてみる。

・まずは普通の例

$2,3,4,...12 ⇔ (2≦i<13)$

・隣り合う部分列について、1.の表記では上限と下限が一致する

$(2,3),(4,5,6) ⇔ (2≦i<4),(4≦i<7)$

$2,3,4,5,6 ⇔(2≦i<7)$

・空の部分列∅も表記できる

$∅ ⇔(k≦i<k)$

1.の記法は便利!

2.の主張がいまいち。1-based indexing にしても$(1≦i<n+1)$と特に不自然ではない気がする。


ex1. offsetとcountの違い(Off-by-oneエラーについて)

ものの数え方には、りんごを1,2,3...と、1から順に個数=countを数える方法と、ある地点を0と決めてそこからどれだけ離れているか距離=offsetで数える方法がある。

offset(距離)とcount(個数)の2つを混同して計算すると、Off-by-oneエラーという計算間違いが起こる。

Learning How to Count (Avoiding The Fencepost Problem)

そして、Off-by-oneエラーは、0-based indexing で起きやすい。

例えば、$n$個の要素を持つの配列$a$最後の要素$last$を求めたいとき、$last=a[n]$は配列の範囲外に出てしまう。


n=6の配列aの例

                     ↓ n=6

count 1 2 3 4 5 6 7
element A B C D E F *
index 0 1 2 3 4 5 6
↑ a[n=6]は配列の範囲外

これは、配列の要素数$n$がcount配列のインデックスがoffsetなのが原因。

正しくは

$offset = count - 1 (ただし1≦count)$

を利用して、$n$をoffsetに変換し

$last = a[n-1]$

1-based indexing では配列のインデックスはcountだから、offset-count変換の計算が必要なくなるぞ!(うれしい)


ex2. 負の数をインデックスにとれる配列について

$a[-i]$は「配列の後ろから$i$番目にアクセス」という意味。

0-based indexing では、

「負のインデックス$(-i)$でアクセス」と捉えることもできる。

例えば、 配列$[A,B,C,D]$は、実質的には下記のような循環した列の一部分であると捉えて、その$index = -i$の要素へのアクセスと考えることができる。

index   -3 -2 -1  0  1  2  3

element B C D A B C D

1-based indexing では、

「負のインデックス$(-i)$でアクセス」と捉えることができない。

もし、無理やりに捉えると$i=0$で穴ができてしまう。


index=0は配列の範囲外

index   -3 -2 -1  0  1  2  3  4

element B C D A B C D


負の数をインデックスにとれる場合は、0-based indexingの方が便利なことがある

例えば、配列 $[A,B,C,D,E,F]$ から配列$[E,F,A,B]$を得たいときは、 $(-2≦i<2)$の範囲を取れば済むからだ。


負のインデックスでアクセスと捉える

index   -5 -4 -3 -2 -1  0  1  2  3  4  5

element B C D E F A B C D E F

1-based indexing では、$i=0$が配列の範囲外となるため、ちょっと面倒。