ポインタ虎の巻

多次元配列の実現

多次元配列とC言語

C言語では、Fortran や BASIC でおなじみの多次元配列を扱う手段が、厳格に言えば存在しない。二次元座標の個々の値を保存する手段として、int x[10][10]; のような表現でデータを確保したいのはどのプログラミング言語でも同じである。しかし、C言語では他の言語で一般的な「多次元配列」という考え方自体が存在しないのである。あるのは正確には「配列の配列」だけである。

しかし、これは普通には欠陥ではない。その代わりのデータ構造として、「ディスプレイ」と呼ばれるデータ構造を定義できるからである。ディスプレイは「配列へのポインタ配列」である。つまり、配列への参照を持つポインタ配列を定義できるのである。この様子を見てみよう。

int x[10][10];

という定義は、10×10=100個の int 型データを持つ領域を確保する。そして x というシンボルは、その確保されたメモリの先頭をポイントするポインタのような役割を果たすが、ただし明白にポインタとは区別されて宣言される。

しかしプログラムの上では、100個のintを連続的に確保しているかどうかは関係がなく、10個のintづつ10個確保されているだけでも良い。このモデルは次の通り。

int D0[10];
int D1[10];
.....
int D9[10];
int *D[10] = { D0, D1, ...., D9 };

D[5][5] = 55;

このとき、ダブルポインタは二次元配列とは、別なものであるにも関わらず、参照の方法である D[5][5] = 55; は二次元配列の参照と、まったく区別できない。だからこれら2つを区別して呼ぶことが大変重要である。以下では「二(多)次元配列」とは「int x[10][10];」のように宣言されたものだけを呼び(変数名としては x を固定して使う)、ポインタを使ったものを「ディスプレイ」と呼ぶ(変数名としては D を固定して使う)ことにする。だから、宣言方法と実際のデータの構成は異っていても、「二次元配列」と「ディスプレイ」は同じように参照できる。この事実は大変混乱を引き起こしやすい。なぜならば、コンパイラは両者を完全に区別しているのである。

さらに参照だけではなく、両者とも宣言を int *x[10]; があたかも宣言されているかのように、ばらしてやることができるのである。しかし「二次元配列」と「ディスプレイ」では次のように違う。

多次元配列では、
x[5] は、int * 型を持つかのように、x の中の50番目の要素を参照するポインタとしてコンパイルされる。
ディスプレイでは、
D[5] はすでに確保されたポインタ配列の5番目のものを参照し、それが結果として、50番目に当る要素が先頭になっている配列へのポインタである。

つまり両者はまったく違うのである。だからディスプレイからの類推(に加えて一次元からの類推)で、x があたかもダブルポインタであるかのように感じられるが、これは誤りである。次のプログラムはコンパイル時に警告が出て、しかも参照されたポインタが正しいものを指さない。

int **p;
p = x;
printf( "%d\n", p[5][5] );

二次元配列に対するポインタは次の形になる。

int (*p)[10];
p = x;
x[5][5] = 55;
printf( "%d\n", p[5][5] );  /* 二次元配列と同等に参照 */
printf( "%d\n", (*p)[55] ); /* 驚くべきことに、これも可能である */

int (*p)[10] は、10個の要素を持つ「配列へのポインタ」である(≠ポインタへの配列 *p[10])。つまり、トップレベルのものだけを、ポインタ化できるわけである(「配列の配列」→「配列へのポインタ」)。このとき、配列サイズ10も宣言に含まれているので、p[5], p[5][5] は以下のように正しく計算可能である。

  1. p は配列へのポインタであり、たとえばアドレスが 1000 とする。
  2. 配列のサイズは int データで10個である。つまり、4 * 10 = 40 である。
  3. だから、配列5個目に対するポインタである p[5] は、1000 + 5 * 40 = 1200 となり、計算可能である。
  4. それならば、配列5個目のものの5つめの int データ p[5][5] も、アドレスは 1200 + 5 * 4 = 1220 となり、アドレスを計算できる。
  5. ゆえに、参照可能である。

しかし、p はポインタである。だから、即時に (*p) と参照すると、これは「配列へのポインタを参照」→「配列」となる。(*p)[55] という参照も可能になるのである。これは次の通り。

  1. p は配列へのポインタであり、たとえばアドレスが 1000 とする。
  2. (*p) は配列へのポインタに対する参照である。つまり、「配列」を表す。だから(*p)は、アドレス 1000 から始まる配列を示す。
  3. 代入されている対象は、二次元配列(一次元と確保の仕方は変わらない)である。だから、(*p)[55] は、アドレス 1000 の int 配列に対する、その 55 番目のものへの参照である。
  4. ゆえに、これも参照可能である。

しかし、次のように配列サイズを省略して「配列へのポインタ」を宣言できる。

int (*p)[] = x;
x[5][5] = 55;
printf( "%d\n", p[5][5] );  /* こっちは参照できない */
printf( "%d\n", (*p)[55] ); /* こちらはOK */

なぜなら、p[5][5] を参照するには、p[5] が計算可能でなくてはならない。しかし、現在の p は「サイズが未知の配列へのポインタ」であるから、p[5] は「サイズが未知の配列の5つめのもの」のアドレスとなって、計算不能である。それゆえ p[5][5] は参照可能ではない。しかし、後のアクセス (*p)[55] では、(*p) はすでに「配列」の先頭を指している。だからその55番目の要素は参照可能なのである。

この辺りの状況をポインタのアドレス値を見てみることで、もう一度整理してみよう。

 (*p)[10](*p)[]
p 1000 1000
(*p) 1000 1000
p[5] 1000 + 5 * 10 * 4計算不能
p[5][5]1200 + 5 * 4p[5]が計算不能
だから計算不能
(*p)[55] 1000 + 55 * 41000 + 55 * 4

面白いことに、p == *p である。これはポインタが指す対象が配列でありポインタではないから、間接参照が生成されないのである(逆に言えばポインタの場合には、*p が間接参照をして、p != *p になる)。

上の表の結果と、二次元配列のシンボル x は、実質上一次元配列であることから、次のキャストは成功することになる。

int *p = (int *)x;

だから次のように書ける。

int x[10][10];
int i;
int *p = (int *)x;

for( i = 0; i < 100; i++ ) {
   *p++ = i;
}
printf( "x[5][5] = %d\n", x[5][5] );

これは x が実質上一次元のポインタであることを示している。

この事情は関数引数の場合も同様である。二次元配列とポインタは混同されず、しかし int (*p)[10] とは一致する。

void sub1( int p[][10] ) {
  ............
}

void sub2( int **p ) {
  ............
}

void sub3( int (*p)[10] ) {
  ............
}

int main(void)
{
   int x[10][10];

   sub1( x );  /* OK */
   sub2( x );  /* Warning が出て、結果もセグメンテーションフォルト */
   sub3( x );  /* OK */
}

二次元配列の宣言で、データが連続して確保されるということと、配列へのポインタにばらして使えることから、次のプログラムは合法的である。

int x[10][10];
int i;
int *p = x[0];  /* x[0] は、最初のデータへのポインタである。 */
                /* だからその型は int * なので、代入できる。 */
for( i = 0; i < 100; i++ ) {
    p[i] = i;
}
for( i = 0; i < 10; i++ ) {
    printf( "%d: %d\n", i + 50, x[5][i] );
}

このとき、正しく 50〜59 の値が表示される。

配列とポインタの「混同」

配列はその実現に関して、今まで見てきたように、ポインタと深い関わりを持っている。そのために、両者は「文脈によって混同される」ことがある。これは前章「extern宣言の罠」で見たように、非常に微妙な問題を持っている。

配列とポインタを「積極的に混同する」最大の場面は、関数の引数である。つまり、

int x[10];
int *p = x;

sub( x );  /* 両方ともOK */
sub( p );

このとき、関数sub() の宣言は次のどれでも良く、まったく同じコードが生成される。つまり、ポインタと配列とは「混同されて」同じものである。

void sub( *p );
void sub( p[] );
void sub( p[10] );

以上の関係は、一次元配列とポインタの互換性を示すのである。しかし、二次元配列とダブルポインタの間には、今まで見てきたように、このような互換性はない。

int x[10][10];
int **p = x; /* 代入不能 */

sub( x );  
sub( p );  /* エラー */

この時、関数 sub() の引数の宣言は、「要素数10の配列へのポインタ」でなくてはならないが、次のどれでもよい。関数sub()に関して生成されるコードはまったく同じである。

void sub( int p[10][10] );
void sub( int p[][10] );
void sub( int (*p)[10] );   

しかし、次のものは関数内部で p[5][5] のような参照ができないので、問題がある。

void sub( int p[][] );
void sub( int (*p)[] );

また、当然ダブルポインタの引数宣言は間違いである。

void sub( int **p );

これは呼び出し側で見てみると、配列とポインタとでは、実は違う実体を渡しているのである。

/* sub( x ); */
MOV AX, xの先頭アドレス  /* x というシンボルが示すアドレスが、AX に入る */
PUSH AX
CALL sub

/* sub( p ); */
MOV AX, p    /* 変数p の値を取得し、AX に入れる */
PUSH AX
CALL sub

つまり、受け側(関数)で同一に扱うことが出来るように、あえてC言語では配列とポインタとを、言語構文として混同しているのである。これを忘れてはならない。

配列サイズ宣言の問題

「配列へのポインタ」を宣言するときに、その配列サイズを省略することもできることは見てきた。しかし、この宣言ではもうお分かりのように p[5][5] のような参照はすることができない、という大きなデメリットがある。つまり、「配列サイズ」は重要な機能を持っているのである。

void sub( int *p[10] );
int x[5][10];

sub( x );  /* 配列サイズが矛盾している */

今まで見てきたように、配列サイズは int * の型を持つx[5]を生成する時の計算に使われる。そのために、コンパイラは「どういうサイズの配列を指しているのか」に神経質に対応する。コンパイラはこの矛盾を指摘するのである。

しかし、宣言で配列サイズを固定してしまうと、問題があることもある。例えば行列演算をする時など、さまざまな配列サイズで計算ができると良い。しかし、C言語ではこれが難しいのである。なぜならば、配列サイズの不一致が常に問題となり、これを回避する手段は実質上存在しない。

だから、プログラマはあまり多次元配列を使わない傾向がある。この事情を解明して見よう。

とはいえ、型チェックを回避するための、「キャスト」という重大な技巧がある。当然、配列サイズを含んだ配列へのポインタでも「キャスト」が可能である。こんなこともできる。

int x[3][4] 
    = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };
int (*p)[6] = (int (*)[6])x;
int i;
for( i = 0; i < 6; i++ ) {
    printf( "%d\n", p[1][i] );
}

これは配列サイズに関してキャストを行い、強引に3×4配列を2×6配列に読み換えている。コンパイラは何も文句を言わず、正しい結果が得られる。

ということは次のように、一次元の配列を二次元の配列に読み換えることだって可能である。

int x[12] 
    = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
int (*p)[4] = (int (*)[4])x;
int i;
for( i = 0; i < 4; i++ ) {
    printf( "%d\n", p[2][i] );
}

ここまで来ると、かなり邪悪である。しかし、このキャストは邪悪なわりにメリットがほとんどない。なぜならば、「キャストであるから」、「動的にサイズを変更できない」のである。ホントはこういう風に、動的に配列サイズを変更したいのである。

int n;
int x[3][4] 
    = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };
int (*p)[n] = (int (*)[n])x;
int i;
for( i = 0; i < n; i++ ) {
    printf( "%d\n", p[1][i] );
}

もしこれが可能ならば、多次元配列のサイズ問題は一挙に解決されるのだが、静的なコンパイラ言語であるC言語は、これを許さない。「常にコンパイル時において、配列サイズは固定していること」がC言語の設計なのである。まあ、これを実現するためには、変数確保についての動的機構が必要となり、C言語の本質に対する変更が要るので、実現される可能性はまったくない。それゆえ、C言語では多次元配列の実現には、大変汚いことをしないと出来ないことになる。

汚い技の例として、次のようなことをやってみよう: 一次元配列として、汎用に使われるバッファを定義しておいて、それにセットされたデータを二次元配列を要求する関数に渡す。

まず、今までやってきたように、配列サイズの固定したサブルーチンに、キャストでバッファを渡してみよう。

void sub( char array[3][10] )
{
  int i;
  for( i = 0; i < 3; i++ ) {
    printf( "%d: %s\n", i+1, array[i] );
  }
}

char Buffer[30] 
= "abcdefghi\0" "bcdefghij\0" "cdefghijk\0";
/* 隣接する文字列は、コンパイル時に結合される */

int main()
{
  /* キャストで渡す */
  sub( (char (*)[10])Buffer );
}

しかし問題の本質は、サブルーチンで配列サイズが固定されていることにある。文字列なので、終了は「\0」によってマーキングがされており、配列サイズの情報とはダブっていると見ても良い。だから、これを回避したい。

それゆえ、サブルーチンでは配列ポインタを引数に取るのではなくて、ダブルポインタを引数に取るようにし、それにあわせて呼び出すことをする。つまり、呼び元で一次元のバッファをダブルポインタの構造に変換するのである。そして、配列サイズと配列数に相当するデータも引数として渡してやることになる。

void sub( char **dp, int row )
{
  int i;
  for( i = 0; i < row; i++ ) {
    printf( "%d: " );
    for( j = 0; dp[i][j] != '\0'; j++ ) {
       putchar( dp[i][j] );
    }
  }
}

char Buffer[30] 
= "1234567\0" "1234567890\0" "cdefghijk\0";
/* 隣接する文字列は、コンパイル時に結合される */

int main()
{
  /* ダブルポインタを作る */
  char *dp[3] = { &Buffer[0], &Buffer[8], &Buffer[19] };
  sub( dp, 3 );
}

とはいえ、この例はかなり技巧的でもある。任意の複数の文字列をバッファにセットして、それらを文字列の配列として扱いたい(一つ一つの文字列の長さが異なる)時には有効であろう。実際には argv[][] を作成する時などこういう処理がされる。それに対して、よく数学的なサブルーチンを書く時に、任意の二次元配列とその行列サイズを渡してやりたいこともある。いわゆる「行列演算」などがその典型であろう。この時には列の数は固定であって行によって変ることはないので、今のようなテクニックを使うのも手であるが、実質的にはやりすぎである。素直に一次元配列として処理した方が良かろう。

int *MatAdd( int *a, int *b, int row, int col )
{
    int i, j;
    for( i = 0; i < row; i++ ) {
        for( j = 0; j < col; j++ ) {
            a[i * col + j] += b[i * col + j];
            /* 勿論次のようでも良い */
            /* *a++ += *b++; */
        }
    } 
    return a;
}

int main()
{
    /* 3x3 行列で作る */
    int MatA[] = { 0, 1, 0, 1, 2, 1, 0, 1, 0 };
    int MatB[] = { 1, 0, 1, 0, 2, 0, 1, 0, 1 };
    int *MatAdded;
    int i;

    MatAdded = MatAdd( MatA, MatB, 3, 3 );
    for( i = 0; i < 3; i++ ) {
        printf( "%d %d %d\n", MatAdded[i * 3], 
                              MatAdded[i * 3 + 1], 
                              MatAdded[i * 3 + 2] );
    }
}

このように面倒な多次元配列は、Cではそれほど使われない。使われる場合も、グローバル変数として定義し、面倒な引数渡しを回避することがほとんどである。

多次元配列のサンプル

多次元配列の実例として、カレンダーの構造を考えてみよう。一年365日は、12ヵ月、最大5週、最大31日になる。各日がそれぞれ最高気温(0度以上)を保存するとする。しかし、月ごと、週ごとの集計をスピードアップするために、日曜から始まる週ごとにデータを構造化するとするのならば、このデータ構造は以下のようになる。

int Kion[12][5][7];

この時、月ごとで考える週の中には、日曜日から始まらず、1日が金曜日というような月始めの週もある。1月がこういう場合ならば、

int Kion[12][5][7] = { { 
        { -1, -1, -1, -1, -1, 10, 8 },

というように、無効なデータとして出現しない適当な値として -1 を入れておく。同様に、1月の日数は28日から31日までの範囲で変動するから、日がなくなれば、やはり -1 を終了マーカとして入れておく。この終了マーカの使い方は、文字列の場合とまったく同じである。

とはいえ、2月は28日しかなく、もし2月1日が日曜の場合は、2月は4週しかないことになる。この時、

int Kion[12][5][7] = { 
        { 
           /* 1月の初期化データ */
        },
        {  /* 2月の初期化データ */
                { 10, 5, 7, 8, 1, 4, 5 },
                { 7, 5, 3, 2, 4, 4, 1 },
                { 2, 5, 7, 8, 3, 1, 1 },
                { 1, 4, 7, 2, 1, 2, 5 },
                { -2 }
        },
        ..................
};

という風に週自体を無効にする特別なデータ -2 を使って、無効な週を表現することも可能である。初期化データを欠いている配列データはどうせ 0 で初期化されるので問題はない。



copyright by K.Sugiura, 1996-2006