C ++には、ヒープとスタックの2つの主要なメモリタイプがあります。スタックを使用すると、すべてが私には明らかですが、ヒープに関しては疑問が残ります。
ヒープメモリはどのように構成されていますか？ヒープのデータ構造について読みましたが、C ++では最小値や最大値だけでなく、ヒープから任意のデータにアクセスできるため、ヒープには当てはまらないようです。
だから私の質問は：ヒープメモリはC ++でどのように編成されていますか？「ヒープに割り当てられている」と読むとき、どのようなメモリ構成を念頭に置いていますか？
フリーストアの一般的な（確かに唯一ではありませんが）実装は、メモリの空きブロック（つまり、現在使用されていないブロック）のリンクリストです。ヒープマネージャは通常、オペレーティングシステムからメモリの大きなブロック（たとえば、一度に1メガバイト）を割り当て、これらのブロックを分割して、コードで使用する場合newなどに使用します。を使用するdeleteと、使用をやめたメモリのブロックがそのリンクリストのノードとして追加されます。
これらの無料ブロックをどのように使用するかについては、さまざまな戦略があります。3つの一般的なものは、ベストフィット、ワーストフィット、ファーストフィットです。
最適な方法として、必要な割り当てに最も近いサイズの空きブロックを見つけようとします。必要以上に大きい場合（通常は割り当てサイズを丸めた後）、2つに分割します。1つは割り当てに戻るためのもので、もう1つは他の割り当て要求を満たすためにリストに戻すための新しい（小さい）空きブロックです。これは良い戦略のように思えるかもしれませんが、しばしば問題があります。問題は、最も近いものを見つけたときに、残ったブロックが小さすぎてあまり役に立たないことが多いということです。しばらくすると、空き領域の小さなブロックが大量に発生しますが、どれも何にも適していません。
ワーストフィットは、代わりにフリーブロックの中でワーストフィットを見つけることによってそれと戦います-IOW、フリースペースの最大のブロック。そのブロックを分割すると、残っているものが可能な限り大きくなり、他の割り当てに役立つ可能性が最大になります。
最初の拳は、空きブロックのリストをたどるだけで、（名前から推測できるように）要件を満たすのに十分な大きさの最初のブロックを使用します。
かなりの数が正確な適合の検索から始まり、ブロックを分割するよりもそれを使用します。
かなりの数が、適切なサイズのブロックの検索を最小限に抑えるために、（たとえば）さまざまな割り当てサイズの個別のリンクリストをいくつか保持しています。
かなりの数のケースで、マネージャーは、空きブロックのリストを調べて、隣り合っているブロックを見つけるためのコードも持っています。それらが見つかった場合は、2つの小さなブロックを1つの大きなブロックに結合します。時々これはあなたfree/deleteブロックのときに正しく行われます。多くの場合、同じサイズのブロックを多数使用している場合（かなり一般的です）にブロックを結合して再分割することを避けるために、それは怠惰に行われます。
多数の同じサイズのアイテム（特に小さいアイテム）を処理するときに一般的なもう1つの可能性は、空きまたは使用中のアイテムを指定するビットセットを持つブロックの配列です。この場合、通常、最後の空きブロックが見つかったビットセットへのインデックスを追跡します。ブロックが必要な場合は、最後のインデックスから前方に検索して、ブロックが空いているとビットセットが示す次のインデックスを見つけます。
ヒープには、2つの異なる概念を持つ2つの主な意味があります。
メモリ管理のヒープについての紹介：
ヒープは、malloc/freeとそのバリアントによって割り当て/解放されるもう1つの動的メモリ領域です。
ここでのヒープは、ヒープデータ構造を意味するものではありません。そのメモリは、グローバルな静的変数が格納されるヒープメモリと呼ばれます。また、メモリを動的に割り当てる場合は、ヒープメモリに割り当てられます。
「ヒープに割り当てられた」と読むと、それは通常、C++の「動的ストレージ期間」の実装固有の実装です。これは、以前はnewメモリを割り当てていて、メモリへのポインタを持っていることを意味します。これにより、メモリを追跡する必要がありdeleteますdelete[]。
それがどのように組織化されているかについては、そうするための決まった方法はありません。ある時点で、メモリが機能する場合、「ヒープ」は実際には最小ヒープ（ブロックサイズで編成）でした。ただし、これは実装固有であり、そのようにする必要はありません。どのようなデータ構造でもかまいませんが、特定の状況では他のデータ構造よりも優れている場合があります。