Gap buffer とは

コンピュータサイエンスのギャップバッファは、同じ場所の近くにクラスタ化された効率的な挿入および削除操作を可能にする動的アレイです。ギャップバッファはテキストエディタで特によく使用されます。テキストエディタでは、テキストのほとんどの変更がカーソルの現在の位置またはその付近で発生します。テキストは2つの連続したセグメントの大きなバッファに格納され、新しいテキストを挿入するためにそれらの間にギャップがあります。カーソルを移動するには、ギャップの片側から別の側にテキストをコピーします(テキストを変更する次の操作までコピーが遅延することがあります)。挿入により、最初のセグメントの最後に新しいテキストが追加されます。削除すると削除されます。
ギャップバッファ内のテキストは、余分なスペースをほとんど必要とせず、リンクリストなどのより洗練されたデータ構造に比べて非常に迅速に検索して表示できる2つの文字列として表されます。しかし、テキスト内の異なる場所での操作や、ギャップを埋める(新しいギャップを作成する必要がある)場合は、ほとんどのテキストをコピーする必要があります。これは、大きなファイルの場合は特に非効率です。ギャップバッファーの使用は、そのような再コピーが、コストがより一般的な安価な操作よりも償却されることがほとんどないという前提に基づいています。これにより、Emacsのようなテキストエディタで使用するロープの代わりに、ギャップバッファが簡単になります。