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

Question

尽管我非常喜欢 C 和 C++，但对于选择以空字符结尾的字符串，我还是忍不住摸不着头脑:

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

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

编辑:由于一些人在上述效率点上要求事实(并且不喜欢我已经提供的那些)，因此它们源于以下几点:

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

从下面的答案中可以看出，在某些情况下，以 null 结尾的字符串效率更高:

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

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

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

• 你需要把字符串的结尾剪掉

但是这个是不正确的——对于以空字符结尾和以长度为前缀的字符串来说，它的时间量是一样的。 (以空结尾的字符串只需在您希望新结尾的位置粘贴一个空，长度前缀只需从前缀中减去。)

Answer 1

来自horse's mouth

None of BCPL, B, or C supports character data strongly in the language; each treats strings much like vectors of integers and supplements general rules by a few conventions. In both BCPL and B a string literal denotes the address of a static area initialized with the characters of the string, packed into cells. In BCPL, the first packed byte contains the number of characters in the string; in B, there is no count and strings are terminated by a special character, which B spelled *e. This change was made partially to avoid the limitation on the length of a string caused by holding the count in an 8- or 9-bit slot, and partly because maintaining the count seemed, in our experience, less convenient than using a terminator.

_{Dennis M Ritchie，C 语言的开发}