Tagアルゴリズムは主に長さがバラバラのメモリブロックを一列に並べてリスト化する簡単な方法です。2.5.」という本...ですが、すいません、こんな歴史のある本は持ってません(-_-;。以下はあちこちのWebサイトから集めた情報を元にしています。お隣さんへジャンプするには?例えば、あるメモリブロックを次のように区切ったとしましょう:この時、例えばB3とB2の境界線にいる人がB3のサイズを知るにはどうしたら良いでしょうか?これは簡単で、B3の先頭にB3のサイズを書きこんでおくと、境界線にいる人はそのままそのサイズを読むことができます:先程のメモリブロックの頭にサイズ部分を差し込んだ状態で、その分だけブロックサイズは増えています。すると、いわゆる「単方向リスト」を再現できます。B1の先頭に人がいるとして、まずそこにあるサイズを読みます(8byteとか)。サイズ記入部分が4byteとすると、B1ブロックは全部で12byteある事になります。そこで、B2にジャンプするには、今いる位置から12byte先へ飛べば良いんです:つまり、管理ブロックの頭にサイズを入れておけば、単方向リストのようにある一方方向へぴょんぴょん飛んで読み込みができるわけです。B2とB3の境界にいる人が「B2の先頭に戻る」にはどうしたら良いでしょうか?上の図で考えてみてください。B2のB3の境界線に立っている人がB2方向にちょっとずつ戻って行くことはできます。B1とB2の境界線に気付くのは難しいです。境界線となるマークがちゃんと存在しているわけではないからです。いうマークを付けるでしょうか?これは「否」です。マークに辿りつくまでに牛歩の如く歩かないといけないわけで、あまりにも効率が悪い検索方法です。そこで、次のようにブロックの終端にブロックサイズを記載してしまいます:黄色い部分が終端に付けた各ブロックの全サイズです。B1は元々が8byteでしたが前後にサイズ部(4byte)があるので全部で16byteとなります。すると、B2-B3境界線に立っていた人はすぐ後ろを見ればB2の先頭(境界線)まで飛ぶべきサイズ(12byte)がありますから、そのサイズに従ってピョンとB2へジャンプすることができるようになります。このように、管理したいメモリブロックの前後にジャンプするためのサイズを記載する事で双方向リストと同じような動き方をする事が可能になります。Tagアルゴリズムです。図の前後についたサイズ部は「タグ」と呼ばれています。Tagアルゴリズムのもう一つの利点はブロックのマージが簡単だという事です。ブロックのマージ、つまりお隣さん同士をくっつけて一つのブロックにしてしまうには、くっつけた両端の境界線にあるサイズ部の値を変更するだけです。B2とB3をマージしてみましょう:B2の先頭にいた場合、自分の隣に確実にジャンプできるためその場でB3へアクセスしてそのサイズを得るのは非常に簡単です。22byte)となります。後は前後タグに新規のサイズを書きこむだけです。自分の左ブロックとマージする場合もほぼ同様の作業を行えばOKです。ブロックの分割マージができるならば分割もできます。分割する場合は新規に発生するタグサイズに注意する必要があります。上のB2-B3マージブロックに対して6byteの新規ブロックを作るとしましょう。この場合、管理メモリサイズ6byteにさらに後端タグサイズ(4byte)と右側の前方タグサイズ(4byte)、合わせて14byteが占有されます。前方タグサイズで計算できます。これがマイナスだと分割不可です。メモリアロケータ等で活躍!一続きのメモリ領域に並んだメモリブロック群を付け加えたりマージしたり分割したり、こういう事を頻繁に行うのは「メモリアロケータ」です。Tagアルゴリズムだけでも簡単なメモリアロケータを作る事が出来ます。32byteのメモリ領域を確保する場合は、メモリブロックリストの後端にそのサイズ分の新しいブロックを作ればいいんです。そのブロックを使用中なのか解放中(フリーブロック)かは前方タグにフラグを追加で設けて区別します。これだけですと非常に非効率なメモリアロケータです。実際はこれを基本に効率を高めるための色々な工夫をします。別の応用方法としては、バイナリファイル内に連続した文字列を並べる時などに便利です。その場合は単方向リストで大抵は良いので後端タグはいりません。C言語スタイルのように文字列の後ろに\0をくっつけると、文字列後端の検索が必要になるため、1バイトずつ読む必要があり非効率になります。Tagアルゴリズムですが、これをクラス化する時にはちょっと工夫が必要になります。メモリブロックは管理メモリ部が不定長です。宣言時にサイズが固定されているクラスでは厳密に管理しきれません。するか?「誰にも邪魔されないメモリブロックを確保できている」という大前提を敷きます。メモリブロックを管理するクラスをBlockとします。32byteの管理メモリを保持する場合、最初に「Blockサイズ+管理メモリサイズ+後端タグサイズ」分のメモリを確保してしまいます。次に、そのメモリの頭にBlockオブジェクトを置きます。newBlock->getBlockSize();太文字の部分に注目です。new」と呼ばれる特殊なnewで、引数に渡したポインタ位置にオブジェクトを作ってくれます。Blockクラスの中には前方タグがあります。その他の付加情報(フラグ等)も入れ込む事ができます。実際に管理するメモリは自分のすぐ後ろに続き、その一番最後に後端タグがくっつきます:次にメモリを確保する場合に備えて後端位置をどこかに保存しておいても良いですね。普通は管理クラスを設けて、その中でメモリのやり取りをします。