尽管我喜欢C和C++,但我还是忍不住在选择空终止字符串时不知所措:
- 在C之前存在长度前缀(即Pascal)字符串
- 通过允许恒定时间长度查找,长度前缀字符串使得几种算法更快.
- 长度前缀字符串使得更容易导致缓冲区溢出错误.
- 即使在32位机器上,如果允许字符串为可用内存的大小,则长度前缀字符串仅比空终止字符串宽三个字节.在16位机器上,这是一个字节.在64位机器上,4GB是一个合理的字符串长度限制,但即使你想将它扩展到机器字的大小,64位机器通常有足够的内存使额外的七个字节排序为null参数.我知道最初的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和朋友那里获得的指针).
以上都不像长度和连续那样常见.
在下面的答案中还有一个断言:
但这个不正确 - 它与null终止和长度前缀字符串的时间相同.(Null终止字符串只是在你希望新结束的地方粘贴一个空值,长度前缀只是从前缀中减去.)