我正在编写一个基本的文本编辑器，它实际上是一个编辑控制框，我想在其中为我的主程序编写代码，数值和表达式。
我目前正在做的是，我将字符串输入编辑控件。在编辑控件中，我有一个类，它将字符串分解为"字形"，如单词、数字、换行符、制表符、格式标记等。例如，单词符号包含一个表示字面值的字符串和一个表示尾随空格数量的短整数。字形还包含绘制文本和计算换行时所需的信息。
例如，文本行"我的名字是Karl"将等于一个像这样的符号链表:NewLineGlyph→WordGlyph(" My "， 1个空白)→WordGlyph(" name "， 1个空白)→WordGlyph(" is "， 1个空白)→WordGlyph(" Karl "， 0个空白)→NULL。
因此，不是将字符串作为连续的字符块(或WCHARs)存储在内存中，而是存储在具有潜在的大量小分配和释放的小块中。
我的问题是;当我这样做的时候，我应该关心堆碎片吗?你有什么提高效率的建议吗?还是用一种完全不同的方法?:)
p。我在Win7上用c++工作。
应该关注碎片化吗?答案可能取决于您的文档有多大(例如，字数)，需要进行多少编辑以及这些编辑的性质。您所概述的方法对于静态(只读)文档可能是合理的，因为您可以对文档进行一次"解析"，但是我认为，在用户进行任意编辑时，需要在后台进行大量工作，以保持数据结构处于正确的状态。此外，你必须决定一个"词"是什么，这在每种情况下都不一定是明显的/一致的。例如，"勤劳"是一个词还是两个词?如果是1，这是否意味着你永远不会在连字符处换行?或者，考虑一下"单词"不能放在一行上的情况。在这种情况下，您是直接截断，还是强制将单词跨行中断?
我的建议是将文本存储为一个块，并将换行符单独存储(作为文本块中的偏移量)，然后在每次有更改时根据需要重新计算换行符。如果您关心碎片和最小化分配/释放的数量，您可以分配固定大小的块，然后自己管理这些块内部的内存。以下是我过去所做的:
-
Text作为一个字符块存储，但不是为整个文档保留一个连续的块，而是维护一个块的链表，这些块总是分配4KB(即，4K单字节字符或2K wchar)。换句话说，文本被存储为数组的链表，其中每个数组被分配为固定大小。
-
每个块跟踪该块内使用/释放的空间(即字符)。
-
当插入一个或多个字符时，如果当前块中有空间，我可以简单地在该块内移动内存(不需要分配/释放)。如果当前块中没有可用的空间，但相邻块中有可用的空间，那么我可以再次在现有块之间移动内存(不需要分配/释放)。如果两个块都满了，只有这样我才分配一个新的4KB块，并在链表中的适当位置添加。
-
当删除一个或多个字符时，我只需要移动内存(最多4KB)，而不是整个文档文本。
-
我还做了一些"垃圾收集"来在适当的时候合并空闲空间。这是相当直接的，包括将字符从一个块移动到另一个块，以便一些块变为空并可以删除。
从操作系统和/或运行时库的角度来看，所有的分配/释放都是相同的大小(4KB)，因此没有碎片。由于我管理该内存的内容，我可以通过移动内存内容来消除浪费的空间，从而避免分配空间中的碎片。另一个优点是，它最大限度地减少了alloc/dealloc调用的数量，这可能是一个性能问题，具体取决于您使用的分配器。因此，这是对速度和大小的优化——发生的频率是多少?: -)
我不会担心堆碎片;现代堆管理器很擅长处理这个问题。
但是，我可能会担心糟糕的数据局部性。在链表(尤其是像std::list这样的非侵入性列表)中，每个字形都是一个单独的分配，任何通过文档的传递都将以一种可能不适合缓存的方式跳过整个内存。文本编辑器比乍一看要难。有很多专门的数据结构用于表示文本块和结构化文档。它们各自针对不同类型的操作进行优化。我建议你先搜索它们的解释，然后再考虑你最常使用的操作类型。
这篇论文是旧的，但它有很多好的信息:http://www.cs.unm.edu/~crowley/papers/sds.pdf