文本编辑器中的行管理

Question

我一直在使用文本编辑器一段时间。我从头开始进行自定义编辑控制，现在我已经掌握了基本知识。我面临的问题是关于生产线管理。因为，我的程序依赖于将输入文本分成行（文本逐行打印），所以行管理非常重要。我正在使用std :: vector来存储行位置。我正在使用Piece Table进行文本处理，但为了简单起见，假设我有一组字符。每次用户按下回车键时，我会在行向量中添加/插入一个元素。问题是每次用户插入角色时，整个结构都会受到干扰。例如：

  0 1 2 3 4 5 6 7 8 9 10 
text = ['h','e','l','l','o','\n','W','o','r','l','d'] 
state of line vector : 
line[0] = 0 
line[1] = 6 

比方说用户的文本[2]之后插入一个字符（“X”）：

  0 1 2 3 4 5 6 7 8 9 10 11 
text = ['h','e','l','x','l','o','\n','W','o','r','l','d'] 
state of line vector : 
line[0] = 0 
line[1] = 6 

由于插入的，我需要更新每个的值元素在当前行之后的行向量中。删除也一样。如果程序中有1000行，并且用户编辑了第一行，那么更新所有999个元素（第一行除外）的效率会非常低。

我在想什么是保持每条线彼此独立。但是，如果将现有的线路划分为两条线路，这会导致复杂化。所以我想知道什么是解决问题的好方法？

编辑： 只是为了澄清，我使用的是一个名为Piece Table的数据结构。我没有使用字符数组。以下是一个表格数据结构： http://www.cs.unm.edu/~crowley/papers/sds.pdf

Answer 1

许多编辑器所使用的经典的数据结构是“Gap Buffer”。这基本上有一个活动周围的工作空间，活动发生的地方，以便本地操作快速发生。然后，当光标移动时，假设发生改变，间隙将随之移动。

就行计算而言，现代系统足够快，您几乎可以简单地扫描缓冲区并查找行。好的是，你不需要在大多数操作上这样做，所以你不要一直这么做。此外，缓冲区中的物理线（即以EOL标记结尾的字符集合）和柔和线（ala文字包装等）之间存在差异。考虑一个现代的文字处理器，其中的段落通常是单一的“行”，但换行到页边距。当然，你可以处理这种方式。最后，对于键盘上的大多数操作，可以简单地使用相对位置（例如，如果插入一条新线，则可以直接将新线条标记添加到线阵列，因为您已经知道了点在缓冲区内）。但是，当你这样做的时候，比如说一个大型的多行代码粘贴操作，它可能会更快地将所有内容填充并重新计算整个缓冲区（作为替代方案，您总是可以将粘贴分隔成行，然后插入一行一个在幕后，就像一条正常的线）。

对于巨大的缓冲区或缓慢的计算机，您可能需要考虑不必担心如此多的全局状态（确切地说，缓冲区中有多少行，您可能在哪一行等等）一点，并开始这种重新计算的背景。最有可能的是暂停会很小（但如果你打字的话会很烦人），并且一旦人类停下来思考自己的想法，就会马上赶上。显然，这可能会使设计复杂化，并且您可能会暂时使用现代硬件上的蛮力。

Answer 2

向量将正常工作。

考虑让该行动态分配，并让该向量存储一个指向该行的指针。将一堆指针移动到行比移动行自己便宜得多。

您也可能要考虑某种Gap Buffer techniques.

Answer 3

如果我理解这个问题，你沿着这些线路跟踪的线位置的一个辅助数据结构：

line offset length 
    0  0  65 
    1  65  30 
    2  95  50 
    3  145  1 
    4  146  13 
... 

如果用d第n行的长度发生变化，那么你有用d来更新所有剩余行的偏移量。当线路很多时，这很慢。

您可以跟踪地标。而不是从序列开始的偏移量，您将它们与某个地标相关联。

假设您为每100行创建一个里程碑。由于第一个地标位于文件的开头，因此前100行的跟踪方式相同。但是接下来的一百行只是有偏移量，而地标具有从第100行文件开始处的绝对偏移量。

所以当你改变一条线的长度时，你只需要更新其余的偏移量该地标中的线条加上其余地标的偏移量。这仍然是O（n），但有一个相当大的除数，它会使它更快。

但是我们可以做得更好。假设我们把它们放在树中，树的叶子是你的线，而根代表整个文件，而不是仅仅维护一个地标列表。要查找给定线的偏移量，请将所有祖先的偏移量加在一起。如果一条线改变了，你只需更新一个节点及其祖先。这给了O（log n），代价是一些簿记。空间开销并不比你已经使用的双向链表更差。