rookの日記： Heap and Linked List

研究してるアルゴリズムの検証プログラムのために
Linked list の要素を沢山 allocate するルーチンが必要で
頭を悩ませてましたが, ふと, 実は簡単にできる事が判明.

沢山の要素を使用するので,
ひとつひとつ malloc(3) するのは論外なのですが,
使用する量が最初には分からないけれど上限は分かってるので
最初は必要な最大量を目一杯, 配列の形で確保して
heapとして使っていました.
でもとにかく沢山メモリを喰うので, なんとか節約したい!
(平均で確保した量の半分位しか使用しないし)

で, どうやって必要に応じて領域を増やせるか
(かつ, 開放された分を再利用できるか)悩んでたわけです.

領域の大きさを変えるのって realloc だっけ?
でも, 再配置されるかも知れないんだっけ?
その領域自身へのポインタが入ってるから
それって多分駄目だよねー? 困ったなー.
とか, アホな事考えてたわけです.

気付いてしまえばすごく簡単な方法があった!
...と行っても普通に, 必要に応じてブロック単位で領域を確保しつつ
それらを Linked-List でつなげて管理するだけなのですけれど.
(普通ぢゃん)
てか, 自分で管理する, ってところに思い到らなかった.

きっと慣れた人なら一瞬で思い付くんでしょうが,
普段プログラミングしないから...

アルゴリズムばっかり考えてないで,
実装のことも勉強しなきゃ役に立たないかもってお話でした(?)