logo标签列表

什么是最适合实现类似记事本编辑器的数据结构？

data-structurestext-editor
14
哪些数据结构用于实现像记事本这样的编辑器。这种数据结构应该是可扩展的，并且应该支持各种功能，如编辑、删除、滚动、选择文本范围等？
6个回答
8
我们曾为一台旧机器编写编辑器（请记住，这是很久以前的事情，大约是1986年左右，所以这是从记忆中得出的，技术水平可能已经有所进步），通过使用自管理池中的固定内存块，我们成功地使其性能飞速提升。
它有两个池，每个池包含一定数量的特定大小的块（一个池用于行结构，另一个用于线段结构）。它基本上是一个链表的链表。
内存是预分配的（对于每个区域）从类似于“malloc()”的调用中，并且我们使用了65535个块（从0到65534，包括块号65535被视为空块，表示列表结束）。
这允许每个65,535行（填充版本为384K或512K）和约1.6G的文件大小（占用2G的分配空间），那在当时相当大。那是理论文件大小限制 - 我认为我们从未在现实中接近过，因为我们从未分配完整套线段结构。
不必为每个小内存块调用“malloc()”为我们带来了巨大的速度增长，特别是因为我们可以为固定大小的块优化自己的内存分配例程（包括在最终优化版本中内联调用）。
两个池中的结构如下，每行为一个字节： 
行结构（6/8字节）     线段结构（32字节）
+--------+                     +--------+
|NNNNNNNN|                     |nnnnnnnn|
|NNNNNNNN|                     |nnnnnnnn|
|PPPPPPPP|                     |pppppppp|
|PPPPPPPP|                     |pppppppp|
|bbbbbbbb|                     |LLLLLLLL|
|bbbbbbbb|                     |LLLLLLLL|
|........|                     |xxxxxxxx|
|........|                     :25 more :
+--------+                     : x lines:
                               +--------+
其中：
  • 小写字母（除了x）指向线段池。
  • 大写字母指向线池。
  • N是下一行的块号（空表示这是文件中的最后一行）。
  • P是前一行的块号（空表示这是文件中的第一行）。
  • b是该行第一个线段的块号（空表示该行为空）。
  • .是保留填充（将结构推出到8个字节）。
  • n是下一行线段的块号（空表示这是该行中的最后一个线段）。
  • p是前一个线段的块号（空表示这是该行中的第一个线段）。
  • L是该线段所在行块的块号。
  • x是该行线段中的26个字符。

线结构被填充的原因是为了加快块号转换为实际内存位置的速度（在那种特定的架构中，左移3位比乘以6要快得多，并且额外使用的内存仅为128K，与总存储相比很小），尽管我们为那些更关心内存的人提供了更慢的版本。

我们还有一个包含100个16位值的数组，大约包含该百分比的线段（以便我们可以快速转到特定行），并且在每个池中维护自由指针的两个指针（这是一个非常简单的单向列表，其中结构中的N或n表示下一个空闲块，并且空闲块从这些列表的前面分配和放回）。

没有必要保留每个线段中的字符计数，因为文件中不允许出现0字节。每个线段允许在末尾拥有被完全忽略的0字节。每当修改时，就会压缩行（即合并线段）。这使得块使用率低（无需频繁和冗长的垃圾回收），并且极大地加快了搜索和替换操作。

使用这些结构允许非常快速的编辑、插入、删除、搜索和导航文本，这是您在简单文本编辑器中可能遇到的大多数性能问题所在。

选择的使用（我们没有实现这一点，因为它是一个使用vi-like命令的文本模式编辑器，例如3d删除3行或6x删除6个字符）可以通过具有{line#/block，char-pos}元组来标记文本中的位置，并使用其中两个元组来表示选择范围。

6

看看Ropes。它可以快速处理字符串的插入/删除/编辑操作。在Rope实现中，通常支持范围操作，并且可以使用倒排索引来进行滚动。

5
维基百科称许多编辑器使用间隙缓冲区。它基本上是一个在中间有未使用空间的数组。光标位于间隙之前，因此在光标处进行删除和插入的时间复杂度为O(1)。实现起来应该很容易。
查看Notepad++的源代码（如Chris Ballance在这里所建议的那样）显示他们也使用了间隙缓冲区。您可以从中获得一些实现思路。
据维基百科介绍，Emacs也使用了这个。 - Hannes de Jager
3

有一篇关于Piece Chains的优秀文章，作者是HexEdit的James Brown。

简而言之：Piece chains允许您记录对文本所做的更改。加载后，您将拥有一个跨越整个文本的piece chain。现在你在中间插入。

与其分配新缓冲区，复制文本等，不如创建两个新的pieces并修改现有的一个：现有的一个现在包含插入点之前的文本（即您只需更改piece的长度），然后有一个包含新文本的piece，再加上一个包含插入点之后所有文本的新piece。原始文本保持不变。

对于撤消/重做，您只需记住添加/删除/更改的pieces。

使用piece chains时最复杂的领域是可见文本中的偏移量与内存结构之间不再具有1:1映射。您可以搜索chain，也可以维护某种二叉树结构。

1

查看Notepad++的实现，您可以在SourceForge上查看源代码

-1
通常的做法是拥有一个字符数组的列表或数组。多年来已经对此进行了大量的研究：您可以查看这个谷歌搜索。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接