テキストエディタのデータ構造

Text Editor: Data Structures – averylaird.com

1998年、Charles Crowleyという人がテキストエディタの実装で使われるデータ構造を研究した論文を出している

He concluded that – from a basis of speed, simplicity, and structure – the piece table was the leading method.

ただpiece tableの実装は複雑で、心がくじけそうになるのも確かだと述べているので、がんばりましょう。


この記事に対する指摘。

Text Editor: Data Structures | Hacker News

  • まずxi editorの作者がコメントをしている。実装にropeを使っている、たしかに単純ではないが、一回作れば実装など気にせず使い回せるのでこれでいいと思っている。もっともgap bufferはシンプルさでは圧勝といえるだろう。あとCrowleyの論文はropeについては考察してない。piece tableについても言及しているが、何を言っているか理解できなかった。
  • 別のコメント。そもそもmemcpy()/memove()は現代的なマシンならGB/sという速度で動く。なので、配列でテキストを保持するのは最悪ではない。テキストエディタのデータ構造を考えるは後回しで構わない。