タグ

関連タグで絞り込む (0)

  • 関連タグはありません

タグの絞り込みを解除

algorithmとc++とeditorに関するmasterqのブックマーク (1)

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

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

  • 1