配列

この記事では、コンピュータ・プログラムにおいて配列（はいれつ、英: array）と呼ばれているデータ構造およびデータ型について説明する。計算機科学の分野ではベクトルと呼ぶ場合もある。また、リストも参照。一般に、添え字（インデックス）で個々の要素を区別する。

配列とは

複数の要素（値）の集合を格納・管理するのに用いられるデータ構造が配列である。数学のベクトルおよび行列に近い概念であり、実際にベクトルおよび行列をプログラム上で表現する場合に配列が使われることが多い。同様に複数要素の集合を管理するデータ構造（コレクションあるいはコンテナ）には連結リストやハッシュテーブルなどがあるが、通常はメモリアドレス上での連続性の違いなどから配列とは区別される。1次元の配列は特に線形配列 (linear array) とも呼ばれる。通例、配列のデータ領域はメモリ空間上で連続していることから、他のデータ構造と比べて空間効率が高く、隣接するデータがまとめてプロセッサのキャッシュに載りやすいという特徴を持つ。

C言語やC++のような静的型付け言語における配列は、連続したメモリ領域を占有する、同じデータ型のオブジェクトのシーケンス（並び）である。ある型Tの配列に、Tとは異なるデータ型のオブジェクトを直接格納することはできないが、ポインタやスマートポインタを要素型とする配列を利用することで、間接的に異なるデータ型のオブジェクトを含む配列を実現することができる。JavaやC#といった言語では、何らかの参照型の配列を利用することで、任意の派生型（サブクラス）のオブジェクトを含む配列を実現することができる。

一方、JavaScriptのような動的型付け言語では、変数ではなく値自身が型を持ち、配列にはあらゆるデータ型の値を格納することができるが、内部的には共通の基底オブジェクトへの参照を要素型とすることによって実現されている。これは柔軟性と引き換えに速度や空間効率といったパフォーマンスや保守性などを低下させてしまう。そのため、あえて特定の型しか格納することのできない型付き配列をサポートする動的言語もある。

配列を第一級オブジェクトとして扱うかどうかは言語によって異なる。C/C++の言語組み込み配列（Cスタイル配列）は第一級オブジェクトではなく、構造体やクラスでラップすることによって疑似的な第一級オブジェクトとすることが多い（C++11以降で標準化されたstd::arrayクラステンプレートなど）。一方、Javaの配列はjava.lang.Objectクラスから派生する第一級オブジェクトである。

文字列は文字の配列によって実現される。文字列の具体的な実装は言語やエンコーディング方式によっても異なる。Cの文字列は配列中のヌル文字を使って終端を表すヌル終端文字列であり、また第一級オブジェクトではない。C++の標準ライブラリでは、C文字列との相互運用性を持つ可変長文字列クラステンプレートstd::basic_stringが規定されている。一方、Javaの文字列は変更不可能（イミュータブル）なUnicode（UTF-16）文字配列によるバッファと長さを併せて管理するjava.lang.Stringクラスのインスタンスであり、また第一級オブジェクトである。

簡単な例

ここでは例示にC言語 (C99) を使う。

例えば、6人の生徒の平均点を計算するプログラムを書くとする。配列を使わない方法では、それぞれの生徒に対応する変数を、次のように個別に用意することだろう。

int score1;
int score2;
int score3;
int score4;
int score5;
int score6;
// 例えば標準入力経由で各生徒の得点を各変数に読み込んだとする。
double mean = (double)(score1 + score2 + score3 + score4 + score5 + score6) / 6;

しかし、この方法では生徒数が増減したときに、変更や拡張が大変になってしまう。より良い解は6要素の配列を使うことである。

int score[6]; // 6要素の配列が作られる。
// 例えば標準入力経由で各生徒の得点を配列scoreに読み込んだとする。
double mean = 0;
for (int i = 0; i < 6; ++i) {
  mean += score[i]; // 配列の各要素へは、変数scoreを通してscore[0]からscore[5]のようにしてアクセスする。
}
mean /= 6;

配列を用いることで、添え字演算子 (array subscript operator) による統一的なアクセスおよび一括処理が可能となる。また、処理すべきデータ個数が増減したときにも対応しやすくなる。

配列の動的確保

→「動的メモリ確保」も参照

前述の例では、プログラム中で宣言時に指定した固定のサイズ（整数定数）による配列確保（静的確保）であった。実用的には、配列の要素数が宣言時（あるいはコンパイル時）に静的に決まってしまうよりも、実行時に要素数を動的に指定して配列を確保できたほうが便利なことがある。例えば、縦横任意サイズの画像ファイルから全画素情報を読み出す場合や、コンピュータで利用可能な空きメモリ量に合わせて扱うデータ個数上限を変化させたい場合などである。

多くのプログラミング言語では、配列のサイズをプログラム実行時に指定して配列を生成する（動的に確保する）手段が用意されている。例えばC言語ではmalloc関数やcalloc関数を利用する。確保に成功するとメモリブロック（配列先頭要素）へのポインタが返却され、このポインタ経由で配列を操作する。

int numStudents;
// 例えば標準入力経由でnumStudentsに生徒数 (> 0) を読み込んだとする。
int* score = calloc(numStudents, sizeof(int)); // 要素数がnumStudents、各要素のサイズがint型のサイズであるような配列を動的に確保し、0で初期化する。
// 例えば標準入力経由で各生徒の得点を配列scoreに読み込んだとする。
double mean = 0;
for (int i = 0; i < numStudents; ++i) {
  mean += score[i]; // 動的に確保した場合でも、配列の添え字シンタックスは同じ。
}
mean /= numStudents;
free(score); // 使い終わった配列のメモリ領域を解放する。

C++などの後発の言語では、動的メモリ確保のために通例new演算子が用意されていることが多く、配列の動的確保には型と要素数を指定するnew[]演算子を使用する。

int numStudents;
// 例えば標準入力経由でnumStudentsに生徒数 (> 0) を読み込んだとする。
int* score = new int[numStudents](); // 要素数がnumStudentsであるようなint型の配列を動的に確保し、0で初期化する。
// 例えば標準入力経由で各生徒の得点を配列scoreに読み込んだとする。
double mean = 0;
for (int i = 0; i < numStudents; ++i) {
  mean += score[i]; // 動的に確保した場合でも、配列の添え字シンタックスは同じ。
}
mean /= numStudents;
delete[] score; // 使い終わった配列のメモリ領域を解放する。

いずれにせよ、C/C++ではmallocあるいはnewによってヒープ領域から確保したメモリは明示的に解放する必要があり、解放を忘れるとメモリリークの原因となる。プログラミングの煩雑さを解消するため、C++ではコンストラクタ・デストラクタを使ったメモリ寿命管理手法 (RAII) が使われることが多い。Javaなどの後発の言語ではガベージコレクションによる自動解放を導入していることが多く、また配列の確保に関して静的確保・動的確保といった区別をしない（配列の確保はすべて動的確保である）ことが多い。

通例、上記のようにして「動的に確保された配列」は、後述の「動的配列」とは異なり、要素の追加時に自動的にサイズを増加させるようなことはできない。

なお、C言語には後述する可変長配列も言語機能として備わっているが、メモリの生存期間などの面で違いがある。

計算量

「配列」という語は、抽象データ型というよりも、添え字をオフセットとしてメモリのアドレスにマップすることで、定数時間（ランダウの記号を用いてO(1)と書かれる）でアクセスできる具象あるいは実装を特に指す場合がある（その意味では、次節の連想配列などは「配列」ではない、ということになる）。

配列に要素を挿入／削除する際、要素間に「隙間」が無いようにするには、線形リストと異なり、挿入／削除位置から後ろの領域にあるすべてのデータの移動（コピー）が必要となる。そのため、挿入／削除にかかる時間はO(n)となる。さらに配列は連続領域を必要とするため、挿入時に領域が不足した場合に拡張する際のメモリ再確保のコストが高い。

探索は一般的には線型探索になるためO(n)だが、データがソート済みであれば二分探索を使うことでO(log n)に軽減することもできる（抽象データ型としては、sorted array などの名前で別のデータ構造と考える場合もある。en:Sorted array を参照）。

さまざまな配列

連想配列

→詳細は「連想配列」を参照

一般的な配列の添え字（インデックス）は整数型であり、有効な値は0または1始まりの非負整数値である。配列の要素数をnとしたとき、とりうる値の範囲は、0始まりの場合は[0, n - 1]、1始まりの場合は[1, n]となる。一方、負数あるいは浮動小数点数を含む任意の数値型や、文字列あるいはユーザー定義の任意のデータ型などを添え字のように使用できる配列を連想配列という。連想配列のインデックス値は連続している必要はなく、飛び飛びであってもかまわない。

静的配列

決まった要素数しか格納できない配列を、静的配列 (static array) あるいは固定長配列 (fixed-length array) と呼ぶ。変数の宣言時あるいはオブジェクト構築の際に長さ（要素数）を指定し、以降は要素を追加あるいは削除することができない。この文脈における「静的」および「固定長」とは、配列の確保時に要素数が決まり、以降は変化しないという意味であり、メモリ確保が静的であるかどうか（記憶域期間が静的であるかどうか）、また要素数が静的に決まるかどうか（要素数がコンパイル時定数であるかどうか）ということは無関係である。JavaやC#の言語組み込みの配列は常にヒープ領域に動的メモリ確保され、また確保する際に指定する要素数にはコンパイル時定数だけでなく動的に値が決まる変数も使用できるが、確保した後は要素の追加や削除ができない静的配列である。

動的配列

長さが固定的に決まっておらず、実行時に必要に応じて要素を追加あるいは削除できる配列を、動的配列 (dynamic array) あるいは可変長配列 (variable-length array) と呼ぶ。メモリが許す限り、要素の末尾追加や途中挿入がいくらでもできる。標準ライブラリで提供されるもの（C++のstd::vector、Javaのjava.util.ArrayList、.NETのSystem.Collections.Generic.Listなど）と、言語に組み込まれているもの（Perl、D、JavaScript、Pythonのlistなど）がある。またPerlなど、言語によっては、最初に配列を生成する際に指定されたサイズからはみ出してアクセス（範囲外アクセス）しても、自動的に拡大されるような配列を持っているものもある。

Visual Basic、Visual Basic for Applications (VBA)、Visual Basic .NET (VB.NET) では、配列をReDimステートメントによって後からリサイズすることができる。そのため、可変長配列 (variable length array) とも呼ばれている。リサイズ時に配列内の既存のデータ内容を維持したままにするにはオプションとしてPreserveキーワードを付ける。FreeBASICでも同様の可変長配列がサポートされている。

一般的に動的配列は内部的には静的配列により実装されているものであり、最初にある程度余裕を持たせた領域を確保しておいて、足らなくなった場合は新しい領域を確保してそこにデータを移し替えることで実現されている。ジェネリックプログラミングをサポートする言語では、任意のデータ型を要素型とする動的配列をサポートするが、そのようなコンテナ（コレクション）を必要に応じてユーザー定義することもできる。特にC++はテンプレートおよび演算子オーバーロードをサポートするため、組み込みの配列型と同じ記法を模倣したクラス型をユーザー定義しやすく、std::vectorに類似の機能を持つクラス型を自前で実装しているライブラリもある。

動的配列の拡大などの場合には、最悪の場合、メモリ上の別の場所が確保されて、そこに全体をコピーする、というような時間のかかる操作が起きる可能性があるものもある（そのシステムの設計次第で、配列の内部にあるものが他からポインタで指されていて、それを更新できないなど、そういうことができない場合もある）。最悪ではなく償却計算量でO(n)にならなければ良い、という考え方もある。

Cの可変長配列

→詳細は「可変長配列」を参照

C言語では、下記のように、実行時に（整数定数式ではない）要素数を指定して自動変数として確保することのできる静的配列を可変長配列 (variable-length array, VLA) と呼んでいる。GCCに拡張として実装されていたが、C99以降で標準化された。Cの可変長配列は動的配列ではなく、後から要素を追加したり削除したりすることはできない。また、静的記憶域期間を持つ配列の要素数は、従来通りコンパイル時定数でなければならない。C11以降では、VLAは必須機能ではなくオプション機能に格下げとなっている。

void func(size_t n) {
  int data[n];
}

Linuxなどの一部の環境では、言語組み込みの機能ではなくランタイムライブラリによって同等の機能を提供するalloca()関数がサポートされている。Microsoft Visual C++では言語組み込みの機能としてはサポートされていないが、ランタイムライブラリに_alloca()関数が用意されている。

Cの可変長配列は指定されるサイズが小さい場合に限って利用すべきである。自動変数は通例スタック領域に確保されるため、うかつに大きなサイズを指定するとスタックオーバーフローを引き起こす危険性がある。

多次元配列

1次元だけではなく2次元・3次元などの多次元配列 (multidimensional array) を備える言語もある。 マトリックスやグリッドのような矩形構造を持ったデータ構造であることから、矩形配列 (rectangular array) と呼ばれることもある。

C#やFORTRANなど、一部の言語には「真の」多次元配列があり、a[i, j] などといったような構文でアクセスする。

C#による多次元配列の例を示す。

int[,] array2d = {
  {0, 1, 2, 3},
  {4, 5, 6, 7},
  {8, 9, 10, 11},
};
System.Console.WriteLine(array2d[2, 3]);

C#には、後述するジャグ配列となる「配列の配列」もある。

C言語の場合

C言語は規格で多次元配列に関する言及があるが、実際にサポートされているのは「配列の配列」であって、真の多次元配列ではない。次のようなコードのことを考えてみればわかる。

void f(int (*p_arr3)[3]) {
  ……
}

int main(void) {
  int arr5_arr3[5][3];
  f(arr5_arr3);
  return 0;
}

ここで arr5_arr3 は「『intの3要素の配列』の5要素の配列」である。そして、関数fに渡される際には、C言語の「配列は引数として渡される際は、その先頭要素を指すポインタに縮退する」というルールにより、その先頭の「intの3要素の配列」を指すポインタがp_arr3に渡される。

もし仮にC言語で真の多次元配列がサポートされているならば、それぞれ「intの5x3要素の配列」「『intの5x3要素』を指すポインタ」（あるいは、単にintを指すポインタに縮退するかもしれない）などがサポートされるはずだが、実際にはサポートされない。

Javaの場合

Javaの「配列の配列」はC言語よりもさらに緩く、Javaの型システムにおける「配列の配列」では、外側の配列は、内側の配列のサイズを固定しない（C言語では、内側の配列のサイズは固定である）。さらに、Javaにはプリミティブ型と参照型があり、参照型は一種のポインタだが、配列は参照型であるので、Javaの「配列の配列」は後述の「ジャグ配列」になっており、やはり真の多次元配列がサポートされているとは言えない。もちろん、1次元配列に対し多次元配列風にアクセスする機能を提供するようなクラスを実装することはできるが、それでは言語レベルで真の多次元配列がサポートされているとは言えない。

ジャグ配列

ジャグ配列のイメージ

「配列の配列」の場合、内側の配列について、要素数が揃っていることを要求しないデータ構造であることもある。ジャグ配列 (jagged array)、不規則配列などと言う。これに対し、内側の配列の要素数が揃った配列を矩形配列 (rectangular array) などと言う。Javaにおける配列の配列はジャグ配列である。C#には前述の通り、「真の多次元配列」もあるが、それとは別に配列の配列もあり、そちらはJavaと同様のジャグ配列である。

Javaによるジャグ配列の例を示す。

int[][] numArr = new int[3][];
numArr[0] = new int[]{1, 2, 3};
numArr[1] = new int[]{4, 5, 6, 7};
numArr[2] = new int[]{8, 9};
System.out.println(numArr[1][1]);

C#によるジャグ配列の例を示す。

int[][] numArr = new int[3][];
numArr[0] = new int[]{1, 2, 3};
numArr[1] = new int[]{4, 5, 6, 7};
numArr[2] = new int[]{8, 9};
System.Console.WriteLine(numArr[1][1]);

要素のアドレスを指定するための参照の展開は、ジャグ配列では次元の数だけ必要なのに対し、矩形配列では1回で済む。また配列の領域を確保する際、ジャグ配列では次元ごとに領域確保を繰り返す必要があるのに対し、矩形配列では1回のnew演算子の使用で領域が確保できる。ただし矩形配列は全要素が収まる連続領域を確保しなければならず、疎行列などのまばらな配列には空間的オーバーヘッドが大きくなってしまうことから向いていない。また、.NET Frameworkの中間言語には1次元配列の要素アクセスに関する専用命令が存在するため、矩形配列よりもジャグ配列のほうが速度性能面で有利になるケースも存在する。

C言語では、配列を指すポインタは、その配列のサイズを固定しなければならない。配列を指すポインタではなく、「『配列の先頭要素を指すポインタ』の配列」によって、次のようにしてジャグ配列のようなデータ構造を作ることができる。

int *numArr[3];
int tmp0[] = {1, 2, 3};
int tmp1[] = {4, 5, 6, 7};
int tmp2[] = {8, 9};
numArr[0] = tmp0;
numArr[1] = tmp1;
numArr[2] = tmp2;
printf("%d\n", numArr[1][1]); // print "5"

例示したように、「配列の配列」と同様の構文でアクセスできるが、データ構造としては異なっている。当然、（生成されるコードを読めばわかるが）意味的に違うものであって、混同してはならない。ましてや「多次元配列がサポートされていると考えるべき」などと考えるのは、混乱の元でしかない。

Iliffe vector

→「en:Iliffe vector」を参照

Iliffe Vectorのイメージ

「ジャグ配列と同様な構造で実装された、多次元配列」という意味の、Iliffe vector という語がある（"Iliffe" は、人名 John K. Iliffe に由来）。それに対し、連続した領域を多次元配列として扱うデータ構造を指す dope vector（en:Dope vector）という語がある。

脚注