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

Question

尽管我热爱C和C ++，但我还是忍不住选择以null结尾的字符串：在C之前存在长度前缀（即Pascal）的字符串长度前缀的字符串允许进行恒定的时间长度查找，从而使几种算法更快。前缀字符串的长度使导致缓冲区溢出错误更加困难。即使在32位计算机上，如果允许字符串成为可用内存的大小，则带前缀的长度字符串也只比以空终止的字符串宽3个字节。在16位计算机上，这是一个字节。在64位计算机上，4GB是一个合理的字符串长度限制，但是即使您希望将其扩展为机器字的大小，64位计算机通常也具有足够的内存，使得多余的七个字节属于null参数。我知道原始的C标准是为极差的机器（就内存而言）编写的，但是效率论点在这里并没有卖给我。几乎所有其他语言（例如Perl，Pascal，Python，Java，C＃等）都使用长度前缀的字符串。这些语言通常在字符串操作基准中胜过C，因为它们在使用字符串时效率更高。C ++使用std::basic_string模板对此进行了一些纠正，但是期望以null终止的字符串的纯字符数组仍然很普遍。这也是不完美的，因为它需要堆分配。空终止的字符串必须保留一个字符（即null），该字符不能存在于字符串中，而长度前缀的字符串可以包含嵌入的null。这些事情中，有几件事比C揭露的要新，因此C不必了解它们是有道理的。但是，在C出现之前，有几个很简单。为什么会选择空终止的字符串而不是明显更好的长度前缀？编辑：由于有些人在上述效率点上要求提供事实（并且不喜欢我已经提供的事实），因此它们源于以下几点：使用空终止字符串的Concat需要O（n + m）的时间复杂度。长度前缀通常只需要O（m）。使用空终止字符串的长度需要O（n）时间复杂度。长度前缀为O（1）。长度和concat是迄今为止最常见的字符串操作。在某些情况下，以null终止的字符串可能更有效，但这种情况发生的频率要少得多。从以下答案中可以看出，在某些情况下以null终止的字符串更有效：当您需要截断字符串的开头并将其传递给某种方法时。即使允许您销毁原始字符串，也无法真正在恒定时间内使用长度前缀来执行此操作，因为长度前缀可能需要遵循对齐规则。在某些情况下，您只是逐个字符地遍历字符串，则可以保存CPU寄存器。请注意，这仅在您没有动态分配字符串的情况下才有效（因为您必须释放它，因此必须使用保存的CPU寄存器保存最初从malloc和friends获得的指针）。以上都不是最常见的长度和连贯性。以下答案中还有一个断言：您需要切断字符串的结尾但这是不正确的-空终止和长度为前缀的字符串的时间相同。（以NULL终止的字符串只是在您希望新的结尾处保留一个NULL，长度前缀只是从前缀中减去。）

Answer 1

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

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

鉴于下面的狂风：

我只想指出，我并不是要说这是一个愚蠢或糟糕的问题，或者表示字符串的C方法是最佳选择。我试图澄清的是，如果考虑到C没有将字符串作为数据类型与字节数组区分开的机制，这一问题将更加简洁。鉴于当今计算机的处理能力和存储能力，这是最佳选择吗？可能不是。但是事后看来总是20/20等等：）