c++ - 文本编辑器中的行管理

Question

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

         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

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

我当时想的是让每一行相互独立。但是，当现有线路分为两条线路时，这会导致复杂化。所以我想知道解决这个问题的好方法是什么？

编辑: 澄清一下，我使用的是一种称为 Piece Table 的数据结构。我没有使用字符数组。这是一 block 表数据结构: http://www.cs.unm.edu/~crowley/papers/sds.pdf

Answer 1

许多编辑使用的经典数据结构是“Gap Buffer”。这基本上有一个工作空间，它位于光标周围，在那里发生事件，以便快速进行本地操作。然后，当光标移动时，假设发生变化，间隙将随之移动。

就线计算而言，现代系统足够快，您几乎可以简单地扫描缓冲区并查找线。好处是您不需要在大多数操作中执行此操作，因此您可以避免一直执行此操作。此外，缓冲区中的物理行(即以 EOL 标记结尾的字符集合)和软行(ala 换行等)之间存在差异。考虑一个现代的文字处理器，其中段落通常是一个“行”但换行到页边距。当然，您可以采用任何一种方式处理。

最后，对于键盘上的大多数操作，您可以简单地使用相对位置(即，如果您插入一个新行，则可以直接向一个行数组添加一个新行标记，因为您已经知道您所在的位置缓冲区内)。但是，当您执行多行的大型粘贴操作时，将其全部塞入并重新计算整个缓冲区可能会更快(作为替代方案，您总是可以将粘贴分成几行，然后逐行插入它们一个在幕后，就像一条普通线)。

对于巨大的缓冲区或缓慢的计算机，您可能需要考虑不要太担心全局状态(缓冲区中到底有多少行，您可能在哪一行，等等)在任何一个指向并在后台启动那种重新计算。停顿很可能是轻微的(但如果您正在打字，这会很烦人)，并且只要人们停下来捕捉他们的想法就会 catch 来。显然，这会使设计复杂化，您暂时可以在现代硬件上使用蛮力。