简单文本编辑器的数据结构
先说vim和emacs吧。
vim文本存储采用的是链表，每个节点代表一行。
emacs采用的是间隙缓冲区(Gap buffer)，如： abcdI____efg I是光标，这样在光标处插入删除就变得很快速，缺点是当光标移动距离过大时需要移动大量数据。
这两种方法各有优点，但是有没有更好的方法呢？
Data Structures for Text Sequences
介绍了Piece Table方法，就是使用两个缓冲区，一个只读，一个只能做尾部附加操作。
只读缓冲区的数据是原始文件，用户每次修改添加的数据记录在附加缓冲区中。
然后使用链表来表示当前文档：每个链表的节点有三个域：哪个缓冲区，起始偏移，长度。
插入操作最多让链表长度加2，删除操作最多让其长度加1。
这样链表长度是编辑次数的函数，而不是文档长度。
不妨设编辑次数为 m ， 文本长度为 n，插入操作的长度为p，来分析复杂度，容易得：
时间复杂度：从上次临近位置插入 O(1)，随机位置插入O(m)，删除时间复杂度同插入。获得某个位置字符O(m)，获得长度为l的字符串O(m+l)，遍历所有字符O(n)。
内容占用：约等于S(n+mp)，因为以前插入的内容会被一直保留在附加缓冲区中。
可以看到大部分操作的时间复杂度是与长度无关的，并且只读缓冲区可以根本不载入到内存中来，这样可以支持编辑非常大的文件（几百MB）。
如果采用平衡树而不是链表来表示节点的话，固定位置，随机位置插入/删除时间复杂度变为O(log m),获得某个位置字符O(log m)，获得长度为l的字符串O(log (m) +l)，遍历所有字符O(n)，但是这样实现（撤销/重做等操作）耗费更多内存，实现起来麻烦，并且一般需要用户交互的文档编辑软件的编辑次数不会太多（用户经常就会存盘，也不可能连续几小时编辑）。
因此这样的数据结构才是最适合简单文本编辑器使用的。