memory - 在内存中表示格式化文本的最佳方式？ C++

Question

我正在编写一个基本的文本编辑器，它实际上是一个编辑控件框，我想在其中为我的主程序编写代码、数值和表达式。

我目前的做法是将字符串输入编辑控件。在编辑控件中，我有一个类将字符串分解为“字形”，如单词、数字、换行符、制表符、格式标记等。例如，字形包含一个表示文字单词的字符串和一个表示文字的短整数尾随空格的数量。字形还包含绘制文本和计算换行时所需的信息。

例如，文本行“My name is Karl”相当于一个字形链接列表，如下所示:NewLineGlyph → WordGlyph(“My”，1 个空格)→ WordGlyph(“name”，1 个空格)→ WordGlyph(“is”，1 个空格)→ WordGlyph(“Karl”，0 个空格)→ NULL。

因此，不是将字符串作为连续的字符 block (或 WCHAR)存储在内存中，而是将其存储在可能有大量小分配和释放的小块中。

我的问题是；这样做时我应该关心堆碎片吗？你有什么提高效率的建议吗？还是一种完全不同的方式？ :)

附言。我在 Win7 上使用 C++ 工作。

Answer 1

您应该担心碎片化吗？答案可能取决于您的文档有多大(例如，字数)、将进行多少编辑以及这些编辑的性质。您概述的方法对于静态(只读)文档可能是合理的，您可以在其中“解析”文档一次，但我想在幕后需要进行大量工作以保持数据结构处于正确的状态，因为用户正在进行任意编辑。此外，您还必须决定什么是“词”，这在每种情况下都不一定是显而易见的/一致的。比如“勤奋”是一两个字吗？如果是一个，是否意味着您永远不会在连字符处自动换行？或者，考虑一个“单词”不能放在一行中的情况。在那种情况下，您是简单地截断单词，还是想强制跨行断开单词？

我的建议是将文本存储为一个 block ，并单独存储换行符(作为文本 block 中的偏移量)，然后在每次发生更改时根据需要重新计算换行符。如果您关心碎片和最小化分配/解除分配的数量，您可以分配固定大小的 block ，然后自己管理这些 block 内的内存。这是我过去所做的:

• 文本存储为字符 block ，但我没有为整个文档使用一个连续的 block ，而是维护一个始终分配 4KB 的 block 的链接列表(即 4K 单字节字符，或 2K WCHAR)。换句话说，文本存储为数组的链接列表，其中每个数组都分配了一个常量大小。

• 每个 block 都会跟踪该 block 中已使用/空闲的空间(即字符)数量。

• 插入一个或多个字符时，如果当前 block 中有空间，我可以简单地在该 block 内移动内存(不需要分配/释放)。如果当前 block 中没有可用空间，但相邻 block 中有可用空间，那么我可以再次在现有 block 之间移动内存(不需要分配/取消分配)。如果两个 block 都已满，我才分配一个新的 4KB block 并添加到链表中的适当位置。

• 删除一个或多个字符时，我只需要移动内存(最多 4KB)而不是整个文档文本。我可能还必须取消分配并移除任何完全空的 block 。

• 我还会进行一些“垃圾收集”，以便在适当的时候合并可用空间。这相当简单，涉及将字符从一个 block 移动到另一个 block ，以便某些 block 变为空并可以被删除。

从操作系统和/或运行时库的角度来看，所有分配/分配的大小都相同 (4KB)，因此没有碎片。由于我管理该内存的内容，因此我可以通过移动内存内容来消除空间浪费，从而避免在分配的空间内产生碎片。另一个优点是它最大限度地减少了 alloc/dealloc 调用的次数，这可能是一个性能问题，具体取决于您使用的分配器。所以，这是对速度 和 大小的优化——that 多久发生一次？ :-)