在内存中表示格式化文本的最佳方式是什么？C++

Question

我正在编写一个基本的文本编辑器，实际上它是一个编辑控件框，我想在其中为我的主程序编写代码、数字值和表达式。目前的做法是将字符串输入到编辑控件中。在编辑控件中，我有一个类，可以将字符串分解成“字形”，如单词、数字、换行符、制表符、格式标记等。例如，单词字形包含一个表示文字的字符串和一个表示尾随空格数的短整数。这些字形还包含绘制文本和计算换行所需的信息。

例如，文本行“My name is Karl”将等于一个字形的链接列表： NewLineGlyph → WordGlyph (“My”, 1空格) → WordGlyph (“name”, 1空格) → WordGlyph(“is”, 1空格 ) → WordGlyph (“Karl”, 0空格) → NULL。

因此，与将字符串存储在内存中作为连续的字符块（或WCHARs）相比，它以小块存储，并且可能有许多小的分配和释放。

我的问题是：当这样做时，我应该担心堆碎片吗？您有任何使其更有效率的建议或完全不同的方法吗？ :)

PS. 我正在Win7上使用C++。

- Karl Hansson

---

我很好奇：为什么你需要存储尾部空白字符的数量？ - Rudy Velthuis

其实只是为了方便，我觉得它们不值得拥有自己的字形。这样，如果有很多空格，我可以用一个与wchar相同大小的数字来表示它们。 - Karl Hansson

@Karl，请记住你已经在进行简化。许多编程语言支持许多不同的字符。例如，在C#中，空格是（除了空格之外）：任何具有Unicode类Zs的字符，水平制表符（U+0009），垂直制表符（U+000B），换页符（U+000C）。 - xanatos

嗨xanatos。那是一个好观点，我没有意识到。当我说空格时，我特指空白的“空格”字符。水平制表符和其他空格通常会有自己的字形。 - Karl Hansson

Answer 1

你是否担心碎片化？答案可能取决于你的文档有多大（例如，字数），以及将进行多少编辑和这些编辑的性质。你提出的方法可能适用于静态（只读）文档，在这种情况下，您可以“解析”文档一次，但我想在幕后需要进行相当多的工作，以保持数据结构处于正确状态，因为用户正在进行任意编辑。此外，您还必须决定“单词”的含义，在每种情况下并不明显/一致。例如，“hard-working”是一个单词还是两个单词？如果是一个单词，这是否意味着您永远不会在连字符处换行？或者，考虑一个“单词”无法适合单行的情况。在这种情况下，您只是截断它，还是要强制打破跨越几行的单词？

我的建议是将文本存储为块，并将换行符分别存储（作为文本块中的偏移量），然后根据需要重新计算换行符。如果您担心碎片化并最小化分配/释放的数量，则可以分配固定大小的块，然后自己管理这些块内存。以下是我过去所做的：

- 文本存储为字符块，但与整个文档的单个连续块不同，我维护一个链表，其中始终分配4KB的块（即4K个单字节字符或2K个WCHAR）。换句话说，文本存储为数组的链接列表，其中每个数组都分配给一个恒定大小。 - 每个块跟踪该块内使用/空闲的空间（即字符）量。 - 插入一个或多个字符时，如果当前块中有空间，则可以在该块内部简单地移动内存（无需分配/释放）。如果当前块中没有空间，但相邻块中有空间，则可以再次在现有块之间移动内存（无需分配/释放）。如果两个块都已满，则仅在链接列表中的适当位置分配一个新的4KB块。 - 删除一个或多个字符时，只需要移动内存（最多4KB），而不是整个文档文本。我还可能必须处理并删除任何完全为空的块。 - 我还进行了一些“垃圾回收”操作，以在适当的时间合并可用空间。这非常简单，涉及将字符从一个块移动到另一个块，以使某些块变为空，并且可以删除。

从操作系统和/或运行时库的角度来看，所有分配/释放的大小都相同（4KB），因此没有碎片。由于我管理该内存的内容，可以通过移动内存内容以消除浪费空间来避免在我的分配空间内出现碎片。另一个优点是它最小化了alloc/dealloc调用的数量，这可能取决于您使用的分配器而成为性能问题。因此，它既是速度优化，也是大小优化 - 这种情况有多少次呢？ :-)

- cbranch

---

嗨cbranch。非常感谢您的回复，您提出了一些非常好的观点。我喜欢您管理内存专用区域的方式，以便于文本处理。我已经开始考虑这个方向的想法，并将寻找相关信息。 :) - Karl Hansson

@cbranch。继续：我的文本框的主要目的是存储和显示表达式和代码样式文本，因此我目前并没有考虑创建一个完整的富文本编辑器。尽管我希望拥有语法高亮等功能，并在文本中使用不同的字体和颜色。由于它是代码，我首先想要显示；只有当单词不适合单行时，才会出现换行。但再次，既然我正在编写这个文本框，我可能会做得更好，提前规划，以便稍后添加更高级的富文本功能。 - Karl Hansson

Answer 2

我不会担心堆碎片问题；现代堆管理器在处理这个问题方面非常出色。

但是，我可能会担心数据局部性差的问题。由于每个字形都是一个单独的分配，存储在链表中（特别是像std::list这样的非侵入式链表），任何对文档的遍历都可能以一种非缓存友好的方式跳跃到内存中的各个位置。

文本编辑器比起初看来要难得多。有很多专门的数据结构用于表示文本块和结构化文档。它们都针对不同类型的操作进行了优化。我建议搜索并了解它们的解释，然后考虑您将要执行的操作类型。

这篇论文虽然有些旧，但包含了很多有用的信息：http://www.cs.unm.edu/~crowley/papers/sds.pdf

- Adrian McCarthy

---

嗨Adrian。感谢您的回复。我有点担心数据局部性不佳。我正在寻找将文本存储在更连续的块中的方法。我的文本编辑器将更像是代码编辑器，因此语法高亮、括号匹配以及代码易于解析等方面是我主要关注的问题。性能也是一个重要问题。我会尝试寻找与此相关的示例数据结构。另外感谢提供有关文本数据结构的论文，我已经开始阅读它了。 :) - Karl Hansson