配列を用いたリストでは使用されない領域が発生する？

質問

応用情報技術者試験に絡んだ質問です。
まずは問題をご覧ください：

問題
リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。

正解の選択肢はこれ↓：

リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。

解説：
配列で実現するリストの特徴です。配列を用いる場合は最大の要素数を格納できるだけのメモリ領域をあらかじめ確保する必要があります。1,000要素分確保しても実際の格納数が10要素程度だとすると、残りの990要素分のメモリ領域が無駄になってしまいます。

・・・これって正しいですか？
mallocで動的にメモリを確保して配列を作り、後にreallocで要素数を増やすことで無駄のない運用ができるはずです。自分はそれを知っていたので、この選択肢を選びませんでした。「可能性がある」で逃げてますが、それを言うなら、無駄なく使える可能性もあるわけで…。この問題、納得いかないです。

まずはmallocとreallocで動的に確保できることへの回答をお願いします。それから、この問題の妥当性についてお願いします。

回答No.3

m-take0220 · ベストアンサー

配列とは

int a[5];

のように宣言するもので、メモリの確保や解放は自動で行われるため、スコープからはずれた場合はアクセスしてはならないとされているものです。

一方、mallocやreallocは、指定されたサイズのメモリ領域を確保するもので、それを特定の型のポインタにキャストすることで、配列に近い形で操作できるようになるのですが、言語仕様としては1つのメモリ領域を確保しているだけです。メモリ領域の解放もプログラマーの責任で行う必要があります。

なので、この2つは(特に試験などでは)別物と考えなければけいません。

お礼

ベストアンサーです。
なるほど、私の主張は「配列でも未使用領域を発生させずに使えるじゃないか！」ですが、malloc/reallocを使った動的「配列」は、そもそもポインタ変数を介して作られるので、[ ]を使って配列のようにアクセスはできるとは言え、中身はがっつりポインタですね。よって、そのような動的「配列」を使って作ったリストは配列型と言うよりポインタ型と呼ぶ方が相応しい、そして、仰る通りin a[5];のような純粋な配列であれば、未使用領域が発生する（か、要素数が足りなくなって作り直す）ことになるわけですね。これで納得しました。

それなら動的「配列」と呼ぶのをやめてほしいですね、と世間に喧嘩を売りながら幕を閉じたいと思います（笑）。
ご回答ありがとうございました！

回答No.2

notnot

他の選択肢を見るためにググりましたが、令和4年春の問5ですね。
「どれが正しいか」じゃなくて、「どれが配列か」という質問なので、その解答で正しいです。
他の選択肢はすべてポインターによるリスト構造についての記述です。
それを選んでしまったという事は問題が何を聞いているかを読み違えたか、ポインターによるリスト構造をよく知らないか、どちらかでしょうね。

単独で「配列に関するこの記述は正しいか？」という設問だったとしても、サイズが変わるごとに配列を作り直すのは配列の弱点を回避するための実装上の工夫で、配列にその弱点があることが前提です。
配列にはその弱点があるという記述は間違っていません。

malloc/reallocをご存じならおわかりでしょうが、「最初は最低限のサイズで、それを越えたら1つ要素が増える度に毎回1つ大きなサイズでreallocする」というのは、実行効率も良くないしヒープ領域のフラグメンテーションも大きくなるので、「追加はまず発生しないが念のために追加の機能がある」等よほど特殊なケース以外ではやらないでしょう。
「最初M個で、足りなくなる度にN個ずつ追加」とか、N（N>1） 個ずつ増やすことでrealllocする回数を減らすはずなので、未使用の領域は常時発生します。

お礼

malloc/reallocが補足的な位置付けなのは理解しています。
ただ、IPAともあろう由緒ある天下り団体が「配列型リストだと未使用領域が発生します」と書くのは浅はか・乱暴だなと思った次第です。

他にもいろいろ書きたいことがあったのですが、No.3さんの回答が的を射ていましたので、ここまでに留めておきます。
ご回答ありがとうございました。

回答No.1

cametan_42

ん〜。確かにムズいね。

ただ、ノウハウとしては「多めにメモリを確保する」になるでしょ?
一般的に言うと、ポインタでリストを作成した場合、逆順取るのがラクなんだよ。
と言うか、「逆順が取れないリスト構造」とか使いもんにならんと言うか・・・・・・。
動的配列で「メモリに余りが出た」場合、逆順取るのが難しいんだ。例に書かれた通り、多めに、1000要素ある動的配列領域を確保して、10個しか要素が無い場合、じゃあ逆順のリストをどうやって取る?これ、かなりややこしいだよ。
そんなのもあって、GLibのArray(動的配列)なんかは、逆順を取る関数を実装していない、んだと思う。

GLib(Array):
https://docs.gtk.org/glib/struct.Array.html

でも問題もヘン、っつーか、書き方見てみると動的配列前提じゃないような気が・・・・・・。
「応用情報技術者試験」って特殊な用語使ってるのかね。配列、って言った時には静的配列前提、みてぇな・・・。
う〜む、分からん!

お礼

配列だと逆順取るのが難しいのは納得です。
ただ、「多めに、1000要素ある動的配列領域を確保して、10個しか要素が無い場合」というのは、せっかく動的にメモリを確保できるのに勿体ない使い方ですよね？
GLibでも必要最小限の個数から始めるのかな、と思います。

ご回答ありがとうございました。