空终止字符串的基本原理是什么？

Question

尽管我很喜欢 C 和 C++，但在选择以空字符结尾的字符串时，我不禁摸不着头脑：

• 长度前缀（即 Pascal）字符串在 C 之前存在
• 长度前缀字符串通过允许恒定时间长度查找使几种算法更快。
• 长度前缀字符串使得更难导致缓冲区溢出错误。
• 即使在 32 位机器上，如果您允许字符串为可用内存的大小，则以长度为前缀的字符串仅比以空字符结尾的字符串宽三个字节。在 16 位机器上，这是一个字节。在 64 位机器上，4GB 是一个合理的字符串长度限制，但即使您想将其扩展到机器字的大小，64 位机器通常有足够的内存，这使得额外的 7 个字节排序为空参数。我知道最初的 C 标准是为极其糟糕的机器编写的（就内存而言），但效率的论点并没有在这里卖给我。
• 几乎所有其他语言（即 Perl、Pascal、Python、Java、C# 等）都使用长度前缀字符串。这些语言通常在字符串操作基准测试中击败 C，因为它们对字符串更有效。
• C++ 使用 std::basic_string 模板稍微纠正了这一点，但期望空终止字符串的纯字符数组仍然普遍存在。这也是不完美的，因为它需要堆分配。
• 以空结尾的字符串必须保留一个字符（即 null），该字符不能存在于字符串中，而以长度为前缀的字符串可以包含嵌入的空值。

其中一些事情比 C 更近一些，所以 C 不知道它们是有道理的。然而，在 C 出现之前，有几个很简单。为什么会选择以空结尾的字符串而不是明显优越的长度前缀？

编辑：由于有些人在上面的效率点上要求提供 _事实_（并且不喜欢我已经提供的事实），因此它们源于以下几点：

• 使用空终止字符串的 Concat 需要 O(n + m) 时间复杂度。长度前缀通常只需要 O(m)。
• 使用空终止字符串的长度需要 O(n) 时间复杂度。长度前缀为 O(1)。
• Length 和 concat 是迄今为止最常见的字符串操作。在某些情况下，以空结尾的字符串可能更有效，但这种情况发生的频率要低得多。

从下面的答案中，这些是空终止字符串更有效的一些情况：

• 当您需要切断字符串的开头并需要将其传递给某个方法时。即使您被允许破坏原始字符串，您也不能在恒定时间内使用长度前缀真正做到这一点，因为长度前缀可能需要遵循对齐规则。
• 在某些情况下，您只是逐个字符地循环遍历字符串，您也许可以节省 CPU 寄存器。请注意，这只适用于您没有动态分配字符串的情况（因为您必须释放它，因此必须使用您保存的 CPU 寄存器来保存您最初从 malloc 和朋友那里获得的指针）。

以上都不像长度和连接那样常见。

在下面的答案中还有一个断言：

• 你需要切断字符串的末端

但这一个是不正确的——空终止和长度前缀字符串的时间相同。 （以空结尾的字符串只需在您希望新结尾的位置粘贴一个空值，长度前缀只需从前缀中减去。）

原文由 Billy ONeal 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

从 马的嘴里

BCPL、B 或 C 语言中没有一个强烈支持字符数据；每个都将字符串视为整数向量，并通过一些约定补充一般规则。在 BCPL 和 B 中，字符串字面量表示静态区域的地址，该地址使用字符串的字符初始化，并打包到单元格中。在 BCPL 中，第一个压缩字节包含字符串中的字符数；在 B 中，没有计数，字符串以特殊字符结尾，B 拼写为 *e 。进行此更改的部分原因是为了避免将计数保存在 8 位或 9 位插槽中导致的字符串长度限制，部分原因是根据我们的经验，维护计数似乎不如使用终止符方便。

Dennis M Ritchie， C 语言的开发

原文由 Hans Passant 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

C 语言中没有字符串。 C 中的“字符串”只是一个指向 char 的指针。所以也许你问错了问题。

“省略字符串类型的理由是什么”可能更相关。对此我要指出，C 不是面向对象的语言，只有基本的值类型。字符串是一个更高级别的概念，必须以某种方式组合其他类型的值来实现。 C 处于较低的抽象级别。

鉴于下面的狂风：

我只想指出，我并不是要说这是一个愚蠢或糟糕的问题，或者表示字符串的 C 方式是最佳选择。我试图澄清如果考虑到 C 没有将字符串作为数据类型与字节数组区分开来的事实，这个问题会更简洁。鉴于当今计算机的处理和存储能力，这是最佳选择吗？可能不是。但事后诸葛亮总是 ²⁰⁄₂₀ 之类的 :)

原文由 Robert S Ciaccio 发布，翻译遵循 CC BY-SA 4.0 许可协议