【C++】テキストエディタのバッファ データ構造・アルゴリズム【第３回】 | TECH PROjin

目次 gap_buffer<char> gap_buffer<char> 前章でも言及したように、テキストエディタにおいてはテキストの参照・編集箇所は局所化されている。 この性質を利用し、vector を高速化したものが gap_buffer （ギャップバッファ、gap vector とも呼ばれる）だ。 vector と gap_buffer のデータ構造の違いは少なく、前者がアロケートしたデータ領域の後ろに未使用部分があるのに対して、 後者はデータ領域の途中に未使用部分があるという点だけだ（下図参照）。 この未使用部分を「ギャップ」と呼び、常に編集位置に設定される。 このようにデータ構造を少し変えただけで、なぜ高速化されるのか不思議に思われる方も少なくないだろうが、 高速になる理由は、挿入・削除時に何が起こるかを見てみると納得していただけるはずだ。 編集位置に ‘a’, ‘b’ が挿入さ

[leiqunni]

津田さん以外の人の記事は珍しいなあ。と思ってたら津田さんだった。