ヒープ領域はツリーなのですか？

C++ - ヒープ領域って2次元なんですか？｜teratail
上記の質問の解答のコメントでZuishinさんに「ツリーだし断片化されているので一次元というものちょっと違いますね。」と言われました。
ツリーだしとはどういう意味でしょうか？
ヒープ領域はツリーなのですか？
Zuishinさんから解答が無い為、改めて質問させていただきます。
ヒープ領域がツリーなのか知りたい為、Zuishinさん以外からも広く回答を募集します。

退会済みユーザー

2020/08/27 23:27

記事的にもそういうことを示す記事は見つかりませんし、mallocの実装でそういう話も聞いたことはありません。↓googleでmalloc implementationで画像検索 https://www.google.com/search?q=malloc+implementation&tbm=isch どれを見てもリストのイメージです。逆に木構造のヒープツリーという用語がありますが、これと混同するなという記事はありますね。 https://it-trend.jp/development_tools/article/32-0041#chapter-1 本人が回答しない以上、間違いだったのだと思いますよ。認められないのは恥ずかしいですね。

退会済みユーザー

2020/08/27 23:35

やや古いですがglibcのmallocの実装を解説してくださってるスライドも貼っときます https://www.slideshare.net/kosaki55tea/glibc-malloc

fao

2020/09/01 20:29

ですよね〜ちょっと検索した限りでは双方向リストなんではないかと思いましたここについてる3つの回答も推測ばかりで読む価値もないですし、mallocのソースでも読みますかね

行動規範の内容に同意します

回答3件

自分は低能なので，正直，大元の質問が何を問うているのかが正確に把握できません＞＜

大元の質問にて，質問者様は

メモリアドレスは1次元なので、ヒープ領域も1次元かと思ったのですが

と書かれていますので，

「メモリアドレス」と「ヒープ領域」の次元が異なる可能性を考えられていて，
「メモリ上に考えているヒープ領域という概念的空間(?)は果たして何次元の存在であろうか」ということを問うているのだと思いますが，合っていますでしょうか？

ざっくりと，

アドレス空間での値(1次元)
　↑
　写像
　↓
ヒープ領域内の位置(n次元)
　↑
　写像
　↓
メモリ上の記憶素子の並びのうちのどれか(何次元と考えるのか謎だが)

みたいな話があるときの，nの値を知りたい，みたいな．

これは結局のところ，
「ヒープ領域とは１次元の存在である」みたいな文言が言語仕様か何か(?)に明確に存在するか否かを問うておられるということでしょうか．
（→であれば，私は存じ上げません…）

で，

ツリーだしとはどういう意味でしょうか？

というのは，おそらく，
【「ヒープ領域」という"概念"がツリー的なブツであり，故に「何次元」とは表現できない】
的な意味合いではなかろうかと思います．

大元の質問で示されている図では，
「ヒープ領域」という世界を矩形で表現していて，その中に，「使用中」とか「空き」とかいうのをぎっしりと詰め込んでいますが，これは「説明のために２次元的に表現してみただけの概念図」であって，
各「使用中」とか「空き」とかいうやつらは，「ヒープ領域」という世界の各所に点在していて，それらがツリーな管理で扱われている，と．

投稿2020/08/26 02:10