c - 在 C 中实现可变字符串的最有效方法是什么？

Question

我目前正在用 C 实现一个非常简单的 JSON 解析器，我希望能够使用可变字符串(我可以在没有可变字符串的情况下做到这一点，但是我想学习最好的无论如何做它们的方式)。我目前的方法如下:

char * str = calloc(0, sizeof(char));
//The following is executed in a loop
int length = strlen(str);
str = realloc(str, sizeof(char) * (length + 2));
//I had to reallocate with +2 in order to ensure I still had a zero value at the end
str[length] = newChar;
str[length + 1] = 0;

我对这种方法很满意，但它让我觉得效率有点低，因为我总是每次只添加一个字符(为了论证，我没有做任何事情先行查找我的字符串的最终长度)。另一种方法是使用链表:

struct linked_string
{
    char character;
    struct linked_string * next;
}

然后，一旦我完成处理，我就可以找到长度，分配适当长度的 char *，并遍历链表以创建我的字符串。

但是，这种方法似乎内存效率低下，因为我必须为每个字符和指向下一个字符的指针分配内存。因此我的问题有两个方面:

• 创建链表然后创建 C 字符串是否比每次都重新分配 C 字符串更快？
• 如果是这样，获得的速度是否值得更大的内存开销？

Answer 1

无论您是存储 char 还是其他内容，动态数组的标准方法是在增长时加倍容量。 (从技术上讲，任何倍数都有效，但加倍很容易，并且在速度和内存之间取得了很好的平衡。)您还应该放弃 0 终止符(如果需要返回 0 终止字符串，请在末尾添加一个)并跟踪分配的大小(也称为容量)和实际存储的字符数。否则，由于重复使用 strlen ( Shlemiel the painter's algorithm )，您的循环具有二次时间复杂度。

通过这些更改，时间复杂度是线性的(每个追加操作的分摊常数时间)并且由于各种丑陋的低级原因，实际性能相当不错。

理论上的缺点是你使用的内存是严格必要的两倍，但链表需要至少五倍的内存来处理相同数量的字符(64 位指针、填充和典型的 malloc 开销，更像是 24 或 32 次)。这在实践中通常不是问题。