c - 如何管理用于插入和删除内容的内存？

Question

为方便起见，我只使用纯文本示例。例如，对于 sentence I have a cat，我需要malloc13 个char变量槽，以便它存储所有带有 final 的字母\0。

但是，如果现在我想在lovely之前插入cat呢？看来我必须创建一个足够大的新数组并复制所有内容。

更糟糕的是，由于计算机无法预测要添加多少东西，所以每次添加新字母时，我似乎都必须这样做 re-malloc 和 copy 东西，即为每个字母做整个事情l o v e l y，事实证明这不是一个聪明的解决方案。（计算机不会提前知道“可爱”这个词，嗯？）

一个“更好”的解决方案似乎是首先创建一个足够大的数组，以便每次插入一个新字母时，程序只复制并移动它后面的所有内容。但是，这仍然是低效的，尤其是当文档很长并且我从头开始添加内容时。

这同样适用于“删除”，每次删除一个字母时，我都必须复制它之后的所有内容并缩小数组大小，看来。

使用节点而不是数组来存储内容似乎是一个同样糟糕的解决方案，因为现在每次我想在内容中间做某事时，我都必须从头开始走一条路。

那么在这种情况下管理内存的正确或有效方法是什么？我想要在诸如 C 之类的低级别编程的答案，它需要直接分配和取消分配内存，而不需要已经为您处理所有事情的“魔术”函数或库。

Answer 1

使用内存块的链表听起来像是一个很好的中间解决方案。每个节点都是一定大小的内存“页面”。为了加快修改中间页面中的内容，您可以有一个索引数组，其中包含指向整个文档中绝对位置的页面指针。

只应在整个页面为空时执行删除。在那一刻，您应该执行以下操作：

prevPage->next = nextPage;
pageFree(page_to_delete);

Answer 2

鉴于您在澄清用例的评论中回复的内容，我的建议是考虑内容的链接列表，其中在纯文本示例的隐喻中，链接列表的元素是单词或段落或页面，并且单词本身是连续的数组。

虽然它们之间的导航不是超级快，但您的性能要求似乎是快速插入和删除。通过使用小的连续单词，O(n)通过控制 small 来最小化重新分配/缩小和复制内容的成本n。这是通过拥有许多n作为链表元素的 's 来实现的。

这将通过拥有内容空间局部性的“单个”片段来提高性能，同时允许您选择更高级别的列表/树结构来帮助获得时间局部性的好处。

这实际上没有解决的一件事是在处理这些数据之后需要对这些数据执行什么操作，以及真正可以容忍的性能水平。持续的 malloc 调用对延迟不利，因为它是一个阻塞系统调用；因此您可以进一步考虑使用已经提到的另一种解决方案，例如循环缓冲区或管理您自己的更大内存块来将自己分配给这些元素。这样，您只需要在需要更大的内存块来处理时才需要 malloc，并且仍然不必从一个页面到另一个页面重新复制所有内容，而只是一个不适合的较小块。

就像我在评论中所说的那样，人们写关于这种事情的论文，它是操作系统设计和系统理解的主要组成部分。所以，把这一切都放在一粒盐里。有很多事情需要考虑，这里无法涵盖。

Answer 3

如果您想轻松处理字符插入和删除，而无需一遍又一遍地重新分配，我认为最好的解决方案是双向链表。

在这里查看：DoublyLinkedListExample（我在学校学过，但我认为这个教程很简单地解释了它是如何工作的以及如何使用它）

这些只是带有数据的结构（节点），指向前一个元素的指针和指向下一个元素的指针。如果您不了解它是如何工作的，请先查看简单链表的教程，然后对您来说会更容易。

只是练习它，因为一开始很难理解。继续训练，你会达到的:)

Answer 4

目前尚不完全清楚您的用例是什么。

既然您提到了文本操作并具有高效的插入、删除和随机访问操作，我猜您可以使用绳索数据结构，它是一种二叉树，它基本上将短字符串片段存储在其节点中（大致）。有关详细信息，请参阅链接的文章。

Answer 5

一种有效的解决方案是使用循环数组列表。

http://en.wikipedia.org/wiki/Circular_buffer

在预先分配了一些大小的数组之后，您还可以跟踪指向列表“开始”的指针（首先是“c”的索引，然后是“l”的索引）。这样，要在开头插入或删除，您可以添加到内存的物理末尾并更改指针。

要索引到数组，您只需索引到数组[(开始指针 + 索引)%size]。

如果字母数量太大，您仍然需要复制到新数组。就预分配多少而言，不需要太多时间的系统是每次数组变满时将其大小加倍。这不会增加太多开销。

编辑：如果您需要将数据插入列表的中间，则循环数组列表将没有用。但是，它对于将数据添加到列表的开头和结尾以及修改或访问中间很有用。