プログラミングのテクニック/大きな配列を確保する場合の注意

この項目は、C, C++ について記述しています。Java の場合は、配列を必ず new を用いて確保するため、下に述べるような原因でのスタックオーバーフローは発生しません。

スタックオーバーフローの恐怖

下のコードは非常に怖いコードです。正常に動作しない可能性が高いです。

#include
using namespace std;

int main(){
  int in[2000][2000];
  int N, M;

  scanf("%d%d", &N, &M);
  …
}

このコードの問題は、関数内で非常に大きな配列を確保しているところにあります。関数内で変数を確保する場合、スタック領域に確保されます。スタック領域は、特に指定しない場合は（プログラムが使用できるメモリ量よりも少なく）制限されていることが多いため、スタック領域をたくさん使うのはあまり好ましい方法ではありません。

解決策 1 : static を使う

「int in[2000][2000]; 」を「static int in[2000][2000]; 」に書き換えると、スタックオーバーフローせずに動くようになります。「static」は、変数のメモリを静的に確保させる命令です。但し、関数内の変数に static をつけると、その関数の呼び出しでは static 変数領域は共用となります。ですから、何も考えずに static を付けるのはよい方法ではありません。static をつけると各呼び出しで変数が共用されることに注意して static をつけてください。

解決策 2 : グローバル変数にする

関数の外側に「int in[2000][2000]; 」を持ってくるだけで、スタックオーバーフローしなくなります。関数の外側(グローバル領域)で定義された変数は、スタック領域以外の場所に確保されます。意味的には、1 の static をつける方法とほとんど違いはありません。

解決策 3 : malloc や new を使う

この場合は若干面倒ですが、メモリ領域を malloc, new などを用いて確保すると、スタックオーバーフローは発生しなくなります。malloc, new はヒープ領域から領域を確保してくるので、スタックオーバーフローは引き起こさなくなります。但し、特に複数回呼ばれる関数内でこの手法を利用した場合、メモリリークを引き起こす可能性があります。競技プログラミングにおいて、基本的に入力サイズには上限が定められているので、動的にメモリを確保できる malloc, new の利点は少ないと言えます。

またC++の場合、これらの代わりにSTLのvector<>クラスを使用する事もできます。これはmalloc, newに似ていますが、スコープを抜けた時に自動的に解放してくれるので、メモリリークを引き起こす可能性は少なくなります。