为文字处理器存储文本的更好方法是什么？

Question

通常的方法是将字符存储在字符串中，但是因为在编写文本时，用户大量删除或添加文本中间的字符，也许最好使用

std::list<char>

来包含字符，然后在列表中间添加字符的操作不昂贵。
    

Answer 1

Http：//www.cs.unm.edu/~crowley/papers/papers/sds.pdf

文本序列的data结构。 查尔斯·克劳利（Charles Crowley），新墨西哥大学，1998年

用于维护字符序列的数据结构是 文本编辑器的重要组成部分。本文调查和评估 文本序列可能的数据结构范围。 adt 检查了与文本编辑器的文本序列组件的接口。 六个常见序列数据结构（数组，间隙，列表，线指针， 固定尺寸的Buers和tables）进行检查，然后是一般 包括所有六个结构的序列数据结构的模型 提出。片段方法详细说明了 提出了优势。序列数据结构的设计空间 检查了上面列出的几种变体 提出。这些序列数据结构是通过实验比较的 并根据许多标准进行评估。实验 比较是通过在编辑中实现每个数据结构来完成的 模拟器并使用成千上万的合成负载对其进行测试 编辑。我们还报告了结果的实验 用于生成合成编辑的参数的变化 负载

第一个单词处理远不及字符串操纵。您将需要丰富的文本数据结构。如果您需要分页，则还需要一些元数据，例如页面设置。对单词进行一些研究，您会得到答案。

对于富文本的部分，您的数据结构必须保存两件事：字符和属性。换句话说，您必须具有某种标记语言。 HTML/DOM是一种选择。但是在大多数时候，由于复杂性，这是过度的杀伤力。

Answer 2

abiword之前使用基于列表的件表，但现在使用基于树的碎片表。转到AbiWord的Wiki页面，您会发现更多。

开机使用不同的方式。基本上，它保留了一段列表，在段落内部，它保留了字符串（或其他更有效的数据结构）和属性列表。我更喜欢这种方式，因为段落是一个自然很小的单位，可以编辑，它比基于树的碎片表容易得多。

SGISTL有一个绳索类，您可能需要检查一下：

Http：//www.sgi.com/tech/stl/rope.html

Answer 3

std::list<char>

的九倍大约需要九倍。这可能不是一个很好的权衡。我的第一个倾向是使用一个std::string，每个

std::vector<std::string>

Answer 4

word处理器使用各种数据结构来优化插入，删除，格式和撤消/重做等操作。常见的包括：

gap缓冲液：

对于光标附近的插入/删除有效。 rope：

非常适合大型文档，支持快速的子字符串操作。

件表：

Answer 5

链接列表：

非常适合基于线路的编辑，快速插入/删除。

array：简单用于小文档，快速阅读操作。

B-trees：为大文件有效，支持搜索和修改。 在实践中，现代编辑通常将这些结构结合在一起，以提高效率。例如：使用件表用于文本存储和绳索进行有效的编辑。