同じ要素内容でも固定長配列の方が可変長配列よりメモリを使わない理由は何故ですか？

Question

一般に固定長配列の方が可変長配列よりメモリを使わないといわれている理由を教えて頂けないでしょうか。

直感的には結局同じ要素数を格納するのであれば、固定長でも可変長でも要素の格納に必要なメモリの大きさは同じの気がします。可変長の場合は格納されている要素の情報以外にも何か情報を持っているのでしょうか？

よろしくお願い致します。

Answer 1

可変長配列というと「コンパイル時には長さが決まっていないが実行時に長さが確定される配列」という意味と、「長さを変更できる配列(要素の追加や削除が可能な配列)」という意味との二つの意味でつかわれてます。

前者の意味の可変長配列では長さに関する情報が追加で必要になる程度でほとんど関係ありません。
後者の意味の可変長配列では長さが変更された時のメモリの再確保が頻繁に行われないように余分にメモリを確保する場合があります(必要量の1.5倍や2倍など)。

Answer 2

一度作った後で長さを変えられる配列で、固定長配列にない記憶というと代表的なのは「長さ」ですね。

あとは、長さを変えること自体が(ビフォーアフターが些細な違いでも)大きな負荷をかけます。
なので Java の ArrayList や C++ の vector は実際の長さよりも多めにメモリを確保します。
この 予約領域を含めた配列全体のメモリ使用量 は capacity と呼ばれ、それっぽいメソッドで問い合わせることができます。

Answer 3

可変長の場合は格納されている要素の情報以外にも何か情報を持っているのでしょうか？

可変長であれば、どこからどこまでがデータなのかを示すために、
・データ長（ないしデータ長が算出できる情報）
・これでデータが終わりだという目印
の少なくともどちらかが必要です。

ただ、これらの情報はそう大きくないので、データ長のばらつきがある場合は、可変長にした方がトータルでは小さくて済むことが多いでしょう。
あなたに「一般に固定長配列の方が可変長配列よりメモリを使わない」と言った人に真意を確認した方が良いでしょうね。

Answer 4

可変長配列というのがCの文法上の用語として出てくる可変長配列であるなら、まさに「固定長でも可変長でも要素の格納に必要なメモリの大きさは同じ」でしょう。

しかし、それでは質問が成立しませんから、そうではなくてメモリ領域をmalloc等で(一般にはヒープ上に)確保してそこに配列を割り当てて使用していることを「可変長配列と呼んでいる」のではないでしょうか? それはCの文法でいう可変長配列とは違うものを誤ってそう呼んでいるということなので、まずはそこの区別をしっかりして頂きたいと思います。

後者の場合、ヒープ領域からメモリを取得すると、システム上そのメモリ領域を使用中だとして扱うための管理領域が必要になり、その分のメモリが必要になります(これはC言語ライブラリ内の話)。そして、取得した領域を今度はC言語のプログラムから利用するための確保した領域へのポインタを保持する必要があり、ポインタを保持するための領域が必要になります。
このように、実際に要素を格納するための領域の他に、管理のための領域がいくらか必要になります。
多分そのことを言っているのではないか、と想像します。
(ただし、繰り返しになりますが、それは「可変長配列」とは違うものかと思います。