Dokusyo-nissi Bessitu 2006-02-26 φ(-_-) ■[lang]はじめての C ポインタ配列とダブルポインタとがよくわかってないので、下の page を少しずつ訳し てみることにした。 http://www.ibiblio.org/pub/languages/fortran/append-c.html C における配列とポインタ (Steve Summit のたくさんの明解なコメントと、Ilana Zommer のすてきなコメント に感謝) これは、C における配列とポインタ、それも多次元配列の使い方に重点を置いた短 いテキストです。 ここでは、関連がないように思われる配列とポインタという C の規則を、ひとつの まとまりとして説明するよう試みています。 それは配列を、新しい表し方と特別のルールにより、基本的な配列等式 array equation に変換することです。 このテキストの目標を、次の 3つに分けてみました。 1) プログラムの中で、C のモジュールを適合させることでポインタ表記を理解し、 また FORTRAN と C の配列の橋渡しを助けること。 2) 整合配列 adjustable array をもたないという、 C の設計上の欠点を回避する 可能なやり方を示すこと。 3) 配列を実装させる、興味ある方法を示すこと。 移植可能なアセンブラとしての C かつてオペレーションシステムやその他のシステム用ソフトウェアは、アセンブリ 言語で書かれていました。 CPU は遅くメモリもとても小さかったので、アセンブリ言語は必要とされるギリギ リのコードから成っていました。 しかし、アセンブリは移植することを前提としていないので、その保持が困難です 。 そこでは、高級言語によるシステムプログラミング設計の有利さははっきりしてい ます。 ハードウェアやコンパイラ技術の改良が、C を成功へと導いたのです。 2006-02-28 φ(-_-) ■[lang]はじめての C Arrays and Pointers in C ポインタとポインタ演算子 FORTRAN では、プログラマに対して一つ大きな制限が強いられます。つまり、 FORTRAN 変数という指定されたメモリの場所しか参照ができません。 ポインタを使うと、アセンブリのように、どのメモリの場所でも、ある便利な方法 で参照することができます。 ポインタは、他の変数のメモリアドレスを保持するのに適した変数です。ポインタ に割り当てられる値は、他の変数 (または他のポインタ) のメモリアドレスなので す。 科学的なプログラミングで、ポインタがどのくらい役立つのでしょうか ? 多分それは、C の愛好者たちが思ってる以上に、ポインタが必要とされるいくつか のアルゴリズムで科学的に使用されています。 プログラミング言語において、制限が課せられていないポインタだと、コンパイラ にとって、効率的なコードを生成させるのが困難だ、ということはよく知られてい ます。 C のポインタは、その値とデータ型に特色があります。 値とは、ポインタが指す先のメモリ場所のアドレスです。そしてその型によって、 ポインタ (または添字) 演算でそのポインタをどのように 1つ進ますか、または戻 るかを決定しています。 2006-03-02 φ(-_-) ■[lang]はじめての C Arrays and Pointers in C C の配列と配列等式 以下のテキストでは一般的な n次元配列のかわりに、2次元配列を使用します。それ により、C の配列とポインタを使った複雑で細かな点を説明することができ、また その計算がより扱いやすくなります。 C の 2次元配列では、その要素が 1次元配列 (列 row) であるような、1次元配列と して処理されます。 たとえば、T (この T はあるデータ型) 4x3 の配列は、T mat[4][3] のように宣言 することができます。 それは下の図のように説明されます。 +-----+-----+-----+ mat == mat[0] ---> | a00 | a01 | a02 | +-----+-----+-----+ +-----+-----+-----+ mat[1] ---> | a10 | a11 | a12 | +-----+-----+-----+ +-----+-----+-----+ mat[2] ---> | a20 | a21 | a22 | +-----+-----+-----+ +-----+-----+-----+ mat[3] ---> | a30 | a31 | a32 | +-----+-----+-----+ 配列の要素が列 row の後ろの列としてメモリに記録されるので、T型の配列 mat[m] [n] の要素に対する配列等式は、 address(mat[i][j]) = address(mat[0][0]) + (i * n + j) * size(T) = address(mat[0][0]) + i * n * size(T) + j * size(T) = address(mat[0][0]) + i * size(row of T) + J * size(T) 2006-03-03 φ(-_-) ■[lang]はじめての C Arrays and Pointers in C いくつかの注意点 1) 配列等式は、抽象的なデータ型とそれの実行とを結びつける重要なものです。 FORTRAN (や他の言語) では、それはプログラマからは「隠されて」いて、配列参照 がなされるときに、コンパイラが自動的に、いつでもその必要とされるコードを「 移植する」のです。 2) より多次元の配列では、その等式がずっと複雑になります。 いくつかのプログラミング言語では、その次元 dimension に対し、任意の制限が課 せられていて、例えば FORTRAN では最大が 7次元になっています。 3) 注意するのは、配列等式では、カッコ ( ) をとり除く分割法 distributed law (ちょうど、前の例の配列等式で、はじめの 2つの説明での、算術演算を計算したよ うな) は使わず、「反復的に iteratively」計算するのが、より効果的だというこ とです。 K&R 方式では、反復的に作動しています。 これから、例えば多等式を反復演算するホルネル公式の 1つが連想されます。 a * x**2 + b * x + c = (a * x + b) * x + c この方法では、x の乗数がとり除かれています。 4) 列 row の数は、この配列等式には入ってきません。また、要素のアドレスを計 算する必要もないのです。 その理由は - ちょうど FORTRAN の assumed-size 配列のように - 2次元配列に渡 されるルーティンでは、最初の次元を指定する必要がないからです。 2006-03-06 φ(-_-) ■[lang]はじめての C Arrays and Pointers in C K&R の、配列をポインタへ変換する方式 K&R では、コンパイラのコードで配列等式を隠すよりもそれを表にだして、配列と ポインタがまとまって処理されるよう設計を試みました。 そこでは、少しわかりにくいけれど、一つの適切な解決法を見つけました。 この「面倒な」配列等式は、その構成を 4つのルールに取り換えられます。 1) N次元の配列は、(N - 1)次元の配列を要素とする 1次元配列である。 2) ポインタの付加は、このように定義される。 ptr # n = ptr + n * size(type-pointed-into) "#" は、通常の付加分との混乱を避けるため、ここでは、ポインタの付加を表しま す。 関数 size() は、オブジェクトサイズを返しています。 3) 有名な「減算変換 decay convention」 配列は、その配列の最初の要素を指すポインタとして処理される。 減算変換は、同じオブジェクトには、再度適用されることはありません。 4) 添字に i の値をとることは、次の操作 - i をポインタに加え、次に型を間接参 照して type-dereference 合計する - に等しい、つまり、 xxx[i] = *(xxx # i) ルールの (4) と (3) が、同時に再帰的に適用される (これは多次元配列の場合で す) ときには、最後のステップを除けば、ポインタの値でなく、単にデータ型が間 接参照 dereference されるだけです。 2006-03-08 φ(-_-) ■[lang]はじめての C Arrays and Pointers in C K&R のルールは配列等式を意味する それでは、2次元配列の場合に、上のルール (再帰的に適用する) の結果が配列等式 であることを示してみましょう。 mat[i] = *(mat # i) (ルール 4) mat[i][j] = *(*(mat # i) # j) (ルール 4) "mat" は明らかに T型の 2次元配列であり、ルール 3 に従って、「T型の列 row へ のポインタ」へと減算 decay される。そして、配列等式の最初の 2つの項が得られ る。 mat[i][j] = *(*(mat + i * sizeof(row)) # j) Pointer to row of T (mat # i) の型を間接参照することで、「T型の列 row」が得られる。 mat[i][j] = *((mat + i * sizeof(row)) # j) Row of T このとき、ポインタ付加分を 1つ左にもっているので、再び「減算変換」を用いて 、1次元配列の「T型の列」をその最初の要素、つまり「T へのポインタ」にしてい く。 このポインタ付加を実行すれば、配列等式の 3つ目の項が得られる。 mat[i][j] = *(mat + i * sizeof(row) + j * sizeof(T)) Pointer to T address(mat[i][j]) = mat + i * sizeof(row) + j + sizeof(T) Pointer to T "mat" が実際にその配列の最初の要素を指していることを覚えていれば、これは次 のように書くことができる。 address(mat[i][j]) = address(mat[0][0]) + i * sizeof(row) + j * sizeof(T) これは正確な配列等式である。証明終わり。 2006-03-12 φ(-_-) ■[lang]はじめての C Arrays and Pointers in C なぜダブルポインタは、2次元配列として使えないのか ? 宣言としてはまちがいなので、たぶんコンパイラはクレームをつけますが、これは その 1つのいい例です、 "int **mat" として、"mat" を 2次元配列に用いる。 この 2つはまったく違ったデータ型なので、使用すると、メモリ上の異なる場所に アクセスします。 すぐれたマシン (例えば VAX/VMS のような) では、このまちがいでは、「不正なメ モリアクセス」とエラーをだして強制終了します。 こうしたまちがいはよく目にします。というのも、減算変換は同じ配列へは (2度以 上は) 再帰的に適用されることはなく、2次元配列がダブルポインタと同じで「ない 」ことを、すぐに忘れてしまうからです。 「T型のポインタへのポインタ」は「T型の 2次元配列」としての役割は果たすこと ができません。 2次元配列は「T型の列 row へのポインタ」と「同じ」ですので、それは「T型のポ インタへのポインタ」とはまったく異なるのです。 ダブルポインタが配列の最初の要素を指すとき、"ptr[0][0]" という添字表記とし て使われていて、それは確実に 2回、間接参照されるのです (ルール 5 を参照)。 きちんと 2度間接参照した後、生成されるオブジェクトのもつアドレスは、どんな ときも配列の最初の要素の「内部を」指す値と同じになります。 最初の要素にはデータも含まれるので、デタラメなメモリにアクセスすることにな るのです。 「T型へのポインタ」という中継ぎをもつ特別な間接参照に、注意を向けて見ましょ う。 type mat[m][n], *ptr1, **ptr2; ptr2 = &ptr1; ptr1 = (type *)mat; でも、どちらもうまく動かないでしょう。配列の "width 幅" (n) の中の情報が失 われ、右側のそれだけが得られて、再びデタラメなメモリにアクセスすることにな ります。 ダブルポインタを 2次元配列のように動かす可能な方法の 1つは、それぞれが元の 行列 matrix の列 row を指すような、補助となるポインタ配列をもつことです。 type mat[m][n], *aux[m], **ptr2; ptr2 = (type **)aux; for (i = 0; i < m; i++) aux[i] = (type *)mat + i * n; 当然、この補助となる配列は動的なものとなります。 サンプルプログラムは、 #include #include main() { long mat[5][5], **ptr, mat[0][0] = 3; ptr = (long **)mat; printf("mat %p\n", mat); printf("ptr %p\n", ptr); printf("mat[0][0] %d\n", mat[0][0]); printf("&mat[0][0] %p\n", &mat[0][0]); printf("&ptr[0][0] %p\n", &ptr[0][0]); return; } VAX/VMS での、出力の結果は、 mat 7FDF6310 ptr 7FDF6310 mat[0][0] 3 &mat[0][0] 7FDF6310 &ptr[0][0] 3 "mat" と "ptr" とは同じ値にもかかわらず、"mat[0][0]" と "ptr[0][0]" が (異 なるアドレスをもつ) 別のオブジェクトだということがわかります。 (追記) ぼくの環境では、出力は次のようになりました、 mat 0xbffff868 ptr 0xbffff868 mat[0][0] 3 &mat[0][0] 0xbffff868 &ptr[0][0] 0x3 (ちょっと訂正) VMS って DEC の製品名だったのか ... 2006-03-25 φ(-_-) ■[lang]はじめての C Arrays and Pointers in C 2次元配列をサブルーチンに渡す方法は、どうすれば可能なのか ? C において、FORTRAN プロシージャや別の C のルーティンから渡される配列を処理 するための選択肢には、下の 5つがあります。 /* ここで さまざまな 方法で 宣言し 用いられる 配列には、short型 3x3 (整数 2組) の 配列を、例として あげています。 これら 5つ すべての 方法は、DEC の VAX/VMS 機で 作動します。 */ #include #include int func1(); int func2(); int func3(); int func4(); int func5(); main() { short mat[3][3], i, j; for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) { mat[i][j] = i * 10 + j; } printf("Initialized data to:"); for (i = 0; i < 3; i++) { printf("\n"); for (j = 0; j < 3; j++) { printf("%5.2d", mat[i][j]); } } printf("\n"); func1(mat); func2(mat); func3(mat); func4(mat); func5(mat); } /* 方法 1 (トリックは 用いない。最初の 次元が 空の 配列) 最初の 次元を 指定することは 絶対厳禁 ! */ int func1(short mat[][3]) { register short i, j; printf("Declare as matrix, explicitly specify second dimension:"); for (i = 0; i < 3; i++) { printf("\n"); for(j = 0; j < 3; j++) { printf("%5.2d", mat[i][j]); } } printf("\n"); return; } /* 方法 2 (配列への ポインタ。 2つ目の 次元を 明示的に 指定) */ int func2(short (*mat)[3]) { register short i, j; printf("Declare as pointer to column, explicitly specify 2nd dim:"); for (i = 0; i < 3; i++) { printf("\n"); for (j = 0; j < 3; j++) { printf("%5.2d", mat[i][j]); } } printf("\n"); return; } /* 方法 3 (シングルポインタを 使用。配列は "flattened" に) この方法では、広い 用途をもつ ルーティンを つくることができる。 宣言の どこにも 次元が あらわれないため、引数の リストを 式に とり込むことで、それらを つけ加えることが できる。 manual での 配列インデックスは、多分 その実行が 遅れるはず。 */ int func3(short *mat) { register short i, j; printf("Declare as single-pointer, manual offset computation:"); for (i = 0; i < 3; i++) { printf("\n"); for (j = 0; j < 3; j++) { printf("%5.2d", *(mat + 3 * i + j)); } } printf("\n"); return; } /* 方法 4 (ダブルポインタ。 ポインタ配列を 補助で 使用) この方法は、インデックスを ランタイムに 割り当てることで、 広い 用途をもつ ルーティンを つくることができる。 次元は、引数のリストを 式に とり込むことで つけ加える。 */ int func4(short **mat) { short i, j, *index[3]; for (i = 0; i < 3; i++) index[i] = (short *)mat + 3 * i; printf("Declare as double-pointer, use auxiliary pointer array:"); for (i = 0; i < 3; i++) { printf("\n"); for (j = 0; j < 3; j++) { printf("%5.2d", index[i][j]); } } printf("\n"); } /* 方法 5 (シングルポインタ。 ポインタ配列を 補助で 使用) */ int func5(short *mat[3]) { short i, j, *index[3]; for (i = 0; i < 3; i++) index[i] = (short *)mat + 3 * i; printf("Declare as single-pointer, use auxiliary pointer array:"); for (i = 0; i < 3; i++) { printf("\n"); for (j = 0; j < 3; j++) { printf("%5.2d", index[i][j]); } } printf("\n"); return; } コンパイルして実行させると、mat[row][column] の結果はすべて次のようになります。 matrix +----+----+----+ | 00 | 01 | 02 | +----+----+----+ | 10 | 11 | 12 | +----+----+----+ | 20 | 21 | 22 | +----+----+----+ 2006-04-01 φ(-_-) ■[lang]はじめての C 基本に戻って、K&R 2nd を再チェック、 http://www4.kcn.ne.jp/~yoitiro/hatena/knr2nd_6.txt 2次元配列を関数に渡す場合は、列の数 number of columns がなければならない。 渡されるのは行 row の配列のポインタだから、行の数 number of rows は無関係で ある。 func(int daytab[][13]) { .... } あるいは func(int (*daytab)[13]) { .... } と書ける。これは 13個の配列のポインタであることを示している。(p136-137) 下のような定義が与えられたとする、 int a[10][20]; /* 2次元配列 */ int *b[10]; /* ポインタ配列 */ このとき a[3][4] と b[3][4] とは両方とも構文としては規則にかなったある単一 の int を参照している。 しかし a は本物の 2次元配列なので 200個の int サイズの場所 location が別に 確保されていて、a[row][column] の要素 element を求めると、 20 x row + column というお約束の直交的な添字計算が実行される。 b では、しかしながら 10個のポインタが割り当てられるだけで、それら - location - は初期化されていない。 初期化は、static あるいはコードによって明確に行わないといけない。 b のそれぞれの element が 20個の要素を指すためには、200個の int プラス、ポ インタ用の cell が別に確保されることになる。 ポインタ配列の有利な点で重要なのは、配列に含まれる行 row が異なった長さでも かまわないことである。 つまり、b のそれぞれの element が 20個の element をもつ vector を (すべて) 指す必要がない。 (ある行 row では) 2つの element を指し、あるものは 50個、またまったく何も指 さなくてもかまわない。(p138) これが、「index (補助のポインタ配列) を実行時 runtime に割り当てる」ための理由 か ... 2次元配列をダブルポインタに渡す場合では、 #include #include int func(); main() { short mat[3][4], i, j; for (i = 0; i < 3; i++) for (j = 0; j < 4; j++) mat[i][j] = i * 10 + j; func(mat); } int func(short **mat) { short i, j, *index[4]; for (i = 0; i < 3; i++) index[i] = (short *)mat + 4 * i; for (i = 0; i < 3; i++) { printf("\n"); for (j = 0; j < 4; j++) printf("%5.2d", index[i][j]); } printf("\n"); return; }