[解決済み] 多次元配列の正しい配置方法

私はプログラミングの先生/本/チュートリアルから、多次元配列を動的に割り当てる正しい方法は、ポインタからポインタへを使用することだと教えられてきました。

しかし、現在 SO で高い評価を得ている何人かのユーザーは、これは間違っており、悪い習慣であると教えてくれました。彼らは、ポインタ ツー ポインタは配列ではなく、私は実際に配列を割り当てておらず、私のコードは不必要に低速であると言います。

これは、多次元配列を割り当てるように私が教えられた方法です。

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int** arr_alloc (size_t x, size_t y)
{
  int** pp = malloc(sizeof(*pp) * x);
  assert(pp != NULL);
  for(size_t i=0; i<x; i++)
  {
    pp[i] = malloc(sizeof(**pp) * y);
    assert(pp[i] != NULL);
  }

  return pp;
}

int** arr_fill (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      pp[i][j] = (int)j + 1;
    }
  }

  return pp;
}

void arr_print (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", pp[i][j]);
    }
    printf("\n");
  }
}

void arr_free (int** pp, size_t x, size_t y)
{
  (void) y;

  for(size_t i=0; i<x; i++)
  {
    free(pp[i]);
    pp[i] = NULL;
  }
  free(pp);
  pp = NULL;
}


int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int** pp;

  pp = arr_alloc(x, y);
  pp = arr_fill(pp, x, y);
  arr_print(pp, x, y);
  arr_free(pp, x, y);

  return 0;
}

出力

1 2 3
1 2 3

このコードは問題なく動作します! どうして間違っているのでしょうか？

どのように解決するのですか？

質問に答えるために、まずいくつかの概念をクリアにする必要があります。配列とは何か、どのように使用できるのか。そして、もし配列でないなら、質問のコードは何でしょうか？

配列とは何ですか？

配列の正式な定義は、C言語規格にあります。 ISO 9899:2011 6.2.5/20 型 .

配列型は、要素型と呼ばれる特定のメンバーオブジェクト型を持つ、連続的に割り当てられた空でない オブジェクトの集合を表します。

わかりやすく言うと、配列は隣接するメモリセルに連続的に割り当てられた同じ型のアイテムの集合体です。

例えば、3つの整数からなる配列は int arr[3] = {1,2,3}; はこのようにメモリ上に確保されます。

+-------+-------+-------+
|       |       |       |
|   1   |   2   |   3   |
|       |       |       |
+-------+-------+-------+

では、多次元配列の正式な定義はどうでしょうか。実は、上で引用した定義と全く同じです。再帰的に適用されます。

2次元配列を割り付けるとしたら int arr[2][3] = { {1,2,3}, {1,2,3} }; のようにメモリに確保されます。

+-------+-------+-------+-------+-------+-------+
|       |       |       |       |       |       |
|   1   |   2   |   3   |   1   |   2   |   3   |
|       |       |       |       |       |       |
+-------+-------+-------+-------+-------+-------+

この例で持っているのは、実際には配列の配列です。2つの項目を持つ配列で、それぞれは3つの整数の配列です。

配列は他の型と同じです。

C言語の配列は、しばしば通常の変数と同じ型システムに従っています。上に示したように、他の型の配列を持つことができるように、配列の配列を持つことができます。

また、同じようなポインタ演算を n -次元配列に対しても、通常の1次元配列と同様のポインタ演算を適用することができます。通常の1次元配列では、ポインタ演算を適用することは些細なことであるはずです。

int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.

for(size_t i=0; i<3; i++)
{
  printf("%d ", *ptr); // print contents.
  ptr++; // set pointer to point at the next element.
}

これは "array decay" によって実現されました。このとき arr が式の中で使われたとき、それは最初の要素へのポインタに "decayed"されました。

同様に、配列の配列を反復するために、まさに同じ種類のポインタ演算を使用することができ、そのために 配列ポインタ :

int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.

for(size_t i=0; i<2; i++)
{
  printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
  ptr++; // set pointer to point at the next element
}

ここでも配列の崩壊がありました。変数 arr 型であった int [2][3] は最初の要素へのポインタに分解されました。最初の要素は int [3] と宣言され、そのような要素へのポインタは int(*)[3] - という配列ポインタを宣言します。

配列ポインタと配列減衰を理解することは、多次元配列を扱う上で必要なことです。

配列が通常の変数と同じように動作するケースは他にもあります。それは sizeof 演算子は、(VLAでない)配列に対しても通常の変数と同じように動作します。32 ビット システムの例です。

int x; printf("%zu", sizeof(x)); プリント 4 .

int arr[3] = {1,2,3}; printf("%zu", sizeof(arr)); プリント 12 (3*4=12)

int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr)); プリント 24 (2*3*4=24)

他の型と同様に、配列はライブラリ関数と汎用APIで使用することができます。配列は連続的に割り当てられるという条件を満たすので、例えば、配列のコピーには memcpy :

int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));

連続的なアロケーションは、他の類似の標準ライブラリ関数である memset , strcpy , bsearch と qsort が動作します。これらは、連続的に配置された配列に対して動作するように設計されています。したがって、多次元配列がある場合、効率的に検索やソートを行うには bsearch と qsort のように、バイナリサーチやクイックソートを自分で実装して、プロジェクトごとに車輪を再発明するような手間を省くことができます。

配列と他の型の間の上記のすべての一貫性は、特にジェネリックプログラミングを行うときに、利用したい非常に良いものです。

配列でなくて、ポインタからポインタというのは何ですか？

さて、質問のコードに戻りますが、これはポインタートゥポインタを使った別の構文を使っていました。それについて何も不思議なことはありません。それは型へのポインタへのポインタであり、それ以上でも以下でもありません。これは配列ではありません。2次元配列でもありません。厳密に言えば、配列を指すために使用することはできませんし、2次元配列を指すために使用することもできません。

しかし、ポインタ間のポインタは、配列全体を指すのではなく、ポインタの配列の最初の要素を指すために使用することができます。そしてそれは、質問において、配列ポインタをエミュレートする方法として、どのように使用されるかということです。問題では、2つのポインタからなる配列を指すために使用されています。そして、2つのポインタはそれぞれ3つの整数の配列を指すために使用されています。

これはルックアップテーブルと呼ばれるもので、抽象データ型（ADT）の一種であり、プレーン配列の下位概念とは異なるものです。主な違いは、ルックアップテーブルをどのように割り当てるかです。

+------------+
|            |
| 0x12340000 |
|            |
+------------+
      |
      |
      v
+------------+     +-------+-------+-------+
|            |     |       |       |       |
| 0x22223333 |---->|   1   |   2   |   3   |
|            |     |       |       |       |
+------------+     +-------+-------+-------+
|            | 
| 0xAAAABBBB |--+
|            |  | 
+------------+  |  
                |
                |  +-------+-------+-------+
                |  |       |       |       |
                +->|   1   |   2   |   3   |
                   |       |       |       |
                   +-------+-------+-------+

この例の32ビットアドレスは作り物です。そのため 0x12340000 ボックスはポインタからポインタを表します。これには、アドレス 0x12340000 へのアドレスが含まれています。その配列の各ポインターは順番に、整数の配列の最初の項目を指すアドレスを含んでいます。

そして、ここからが問題の始まりです。

ルックアップテーブル版での問題点

ルックアップテーブルはヒープメモリ上に散らばっています。隣接するセルに連続的にメモリが割り当てられているわけではなく、各呼び出しが malloc() を呼び出すたびに新しいメモリ領域が生成され、必ずしも隣接して配置されるとは限らないからです。このことは、今度は多くの問題を引き起こします。

• 期待されたポインタ演算を使用できない。ルックアップテーブルの項目のインデックス付けとアクセスにポインタ演算の形式を使用することはできますが、配列ポインタを使用してそれを行うことはできません。

• sizeof 演算子を使用することはできません。pointer-to-pointerに使用すると、pointer-to-pointerのサイズを与えることになります。最初に指されたアイテムに使用すると、ポインタのサイズが表示されます。どちらも配列のサイズではありません。

• 配列型を除く標準ライブラリ関数が使えない( memcpy , memset , strcpy , bsearch , qsort など)。このような関数はすべて、入力として配列を得ることを想定しており、データは連続的に割り当てられる。ルックアップテーブルをパラメータとしてそれらを呼び出すと、プログラムがクラッシュするなど、未定義の動作バグが発生します。

• の繰り返しの呼び出しは malloc を繰り返し呼び出し、複数のセグメントを割り当てることで、ヒープ 断片化 になり、その結果 RAM メモリの使用率が低下します。

• メモリが散在しているため、CPU はルックアップテーブルを反復するときにキャッシュメモリを利用できません。データ キャッシュを効率的に使用するには、メモリの連続したチャンクを必要とし、上から下へと反復されます。つまり、ルックアップテーブルは、設計上、実際の多次元配列よりも大幅に遅いアクセス時間を持つということです。

• への各呼び出しに対して malloc() を呼び出すたびに、ヒープを管理するライブラリのコードはどこに空き領域があるかを計算しなければなりません。同様に free() を呼び出すたびに、実行されなければならないオーバーヘッドのコードがあります。したがって、これらの関数の呼び出しはできるだけ少なくすることが、性能の点から望ましい場合が多い。

ルックアップテーブルは悪いものばかりですか？

見てわかるように、ポインタベースのルックアップテーブルには多くの問題があります。しかし、それらはすべて悪いわけではなく、他のツールと同じです。ただ、正しい目的のために使用する必要があります。例えば、多次元配列を配列として使用したい場合、ルックアップテーブルは明らかに間違ったツールです。しかし、他の目的に使用することは可能です。

ルックアップテーブルは、すべての次元が個々に完全に可変なサイズを持つ必要がある場合に正しい選択となります。そのようなコンテナは、たとえば、C 言語の文字列のリストを作成するときに便利です。その場合、メモリを節約するために、上記の実行速度のパフォーマンスの損失を取ることがしばしば正当化されます。

また、ルックアップテーブルには、多次元配列全体を再割り当てする必要なく、実行時にテーブルの一部を再割り当てできるという利点があります。これを頻繁に行う必要がある場合、ルックアップテーブルは実行速度の点で多次元配列より優れている可能性さえあります。例えば、連鎖したハッシュテーブルを実装する場合にも、同様のルックアップテーブルを使用することができます。

多次元配列を動的に割り当てるにはどうすればよいのでしょうか？

最近のC言語では、単純に可変長配列(VLA)を使うのが一番簡単な形です。 int array[x][y]; ここで x と y は，配列宣言の前に実行時に値を与える変数である．しかし、VLAはローカルスコープを持ち、プログラムの期間中ずっと持続するわけではなく、自動的に保存期間が設定されます。そのため、VLAは一時的な配列に使用するには便利で高速かもしれませんが、問題のルックアップテーブルに代わる万能のものではありません。

多次元配列を本当に動的に割り当てるには、その配列が 割り当てられたストレージの期間 を得るためには malloc() / calloc() / realloc() . 以下、一例を挙げます。

現代のC言語では、VLAへの配列ポインタを使用します。このようなポインタは、実際のVLAがプログラム中に存在しない場合でも使用することができます。これらを使うことの利点は、単なる type* または void* とすることで、型安全性を高めています。また、VLAへのポインタを使用することで、配列を使用する関数へのパラメータとして配列の次元を渡すことができ、変数と型安全性を一度に実現することができます。

残念ながら、VLAへのポインタを持つことの利点を利用するためには、そのポインタを関数の結果として返すことができません。そのため、呼び出し元に配列へのポインタを返す必要がある場合、それはパラメータとして渡されなければなりません (詳細は 動的メモリアクセスは関数内部でしか動作しない ). これはC言語では良い習慣ですが、コードが少し読みづらくなります。以下のような感じでしょうか。

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

この構文に へのポインタは、配列ポインタ を使ったこの構文は少し奇妙で威圧的に見えるかもしれませんが、次元を増やしてもこれ以上複雑になることはないでしょう。

void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
  *aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
  assert(*aptr != NULL);
}

さて、このコードと、ルックアップテーブル版に次元を一つ追加するコードを比較してみましょう。

/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
  int*** ppp = malloc(sizeof(*ppp) * x);
  assert(ppp != NULL);
  for(size_t i=0; i<x; i++)
  {
    ppp[i] = malloc(sizeof(**ppp) * y);
    assert(ppp[i] != NULL);
    for(size_t j=0; j<y; j++)
    {
      ppp[i][j] = malloc(sizeof(***ppp) * z);
      assert(ppp[i][j] != NULL);
    }
  }

  return ppp;
}

現在 その は、quot;three-star programming" の読めない混乱です。そして、4 次元は考慮しないことにしましょう...。

真の2次元配列を使用したバージョンのフルコード

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

void arr_fill (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      array[i][j] = (int)j + 1;
    }
  }
}

void arr_print (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", array[i][j]);
    }
    printf("\n");
  }
}

int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int (*aptr)[x][y];

  arr_alloc(x, y, &aptr);
  arr_fill(x, y, *aptr);
  arr_print(x, y, *aptr);
  free(aptr); // free the whole 2D array

  return 0;
}