テキスト処理のためのデータ構造 - Rope - A Memorandum

テキストエディタのデータ構造 Rope データ構造とは Rope は Copy on Write の実現が容易 Rope 実装例 Rope の結合と分割 挿入と削除処理 Rope の実行例 まとめ テキストエディタのデータ構造 テキストエディタでよく使われるデータ構造には、Gap Buffer、Piece table、Rope を元にしたものが多いです。 テキストエディタでは、テキストファイルの任意の場所への挿入や削除が繰り返されます。 単純な文字列(ここでは文字配列)をデータ構造として利用した場合、編集の都度メモリのコピーが必要になります。 元のテキスト char[] text に、char[] ins の文字列配列を、index の位置に挿入する場合、以下のような処理となり、テキストが長い場合、メモリのコピー処理がボトルネックになります。 int index = 100; char[]