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

 

就像我喜欢C和C ++一样，我忍不住在选择以null结尾的字符串时抓住我的头：

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

    • 这些东西中有几个比C更早出现，因此C不知道它们是有意义的。 然而，在C成立之前，有几个很清楚。 为什么会选择以null结尾的字符串而不是明显优越的长度前缀？

    编辑 ：由于有些人在上面的效率问题上提出了事实（并且不喜欢我已经提供的那些事实），它们源自一些事情：

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

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

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

    • 以上都不像长度和连续一样普遍。

    在下面的答案中还有一个说法：

  • 您需要切断字符串的结尾

    • 但是这是不正确的 - 对于以空字符结尾和长度为前缀的字符串，这是相同的时间量。 （空终止的字符串只在你想要新结束的地方粘住null，长度前缀只是从前缀中减去。）

    从马的嘴里

    BCPL，B或C都不支持该语言中的字符数据; 每个字符都像整数的向量一样处理字符串，并且通过一些约定来补充一般规则。 在BCPL和B中，字符串文字表示用字符串的字符初始化的静态区域的地址，并被打包到单元格中。 在BCPL中，第一个打包字节包含字符串中的字符数; 在B中，没有计数，并且字符串由一个特殊字符终止，这个特殊字符B拼写*e 。 这种改变是为了避免由于将计数保持在8位或9位槽中而造成的字符串长度限制，部分原因在于，根据我们的经验，维持计数看起来不如使用终止符方便。

    Dennis M Ritchie，C语言的发展

    C没有一个字符串作为语言的一部分。 C中的'字符串'只是一个指向char的指针。 所以也许你问的是错误的问题。

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

    鉴于下面的狂风暴雨：

    我只想指出，我并不是想说这是一个愚蠢或不好的问题，或者C表示字符串的C方式是最佳选择。 我试图澄清，如果考虑到C没有将字符串作为数据类型与字节数组区分的机制这一事实，问题会更简洁明了。 鉴于今天电脑的处理和记忆能力，这是否是最好的选择？ 可能不会。 但事后总是20/20和所有:)

    这个问题被称为Length Prefixed Strings (LPS)与zero terminated strings (SZ)东西，但主要暴露长度前​​缀字符串的好处。 这看起来可能是压倒性的，但说实话，我们也应该考虑LPS的缺点和深圳的优势。

    据我所知，这个问题甚至可以被理解为一种有偏见的方式来问“零终止字符串有什么优点？”。

    零终止字符串的优点（我看到）：

  • 非常简单，不需要在语言中引入新的概念，char数组/ char指针可以做到。
  • 核心语言只包括最小的syntaxic糖，以将双引号之间的内容转换为一堆字符（真的是一堆字节）。 在某些情况下，它可以用来初始化与文本完全无关的事物。 例如，xpm图像文件格式是包含以字符串编码的图像数据的有效C源。
  • 顺便说一下，你可以在字符串文字中加一个零，编译器也会在文字末尾加上另一个： "thisisvalidC" 。 它是一个字符串吗？ 或四弦？ 或者一堆字节......
  • 平面实现，没有隐藏的间接寻址，没有隐藏的整数。
  • 没有涉及隐藏的内存分配（好吧，一些臭名昭着的非标准功能，如strdup执行分配，但这主要是问题的来源）。
  • 对于小型或大型硬件没有具体问题（想象在8位微控制器上管理32位前缀长度的负担，或者限制字符串大小到小于256字节的限制，这是我在Turbo Pascal之前实际遇到的问题）。
  • 字符串操作的实现只是一些非常简单的库函数
  • 有效的主要用于字符串：从已知的开始（主要是消息到用户）按顺序读取常量文本。
  • 终止零并不是强制性的，所有必要的工具都可以像字符串一样处理字符。 在C中执行数组初始化时，您甚至可以避免使用NUL终止符。 只需设置合适的尺寸。 char a[3] = "foo"; 是有效的C（不是C ++），并且不会在a中放置最终的零。
  • 与unix的观点相一致，即“一切都是文件”，包括没有像标准输入，标准输出一样固有长度的“文件”。 您应该记住，开放式读取和写入原语的实施水平非常低。 它们不是库调用，而是系统调用。 并且相同的API用于二进制或文本文件。 文件读取原语获取缓冲区地址和大小并返回新的大小。 你可以使用字符串作为缓冲区来编写。 使用另一种字符串表示形式意味着您不能轻易使用文字字符串作为要输出的缓冲区，或者在将其转换为char*时，必须使其具有非常奇怪的行为。 即不返回字符串的地址，而是返回实际的数据。
  • 非常容易操作从文件中读取的文本数据，而无需使用无用的缓冲区副本，只需在正确的位置插入零就可以了（当然，对于现代C而言，并非如此，因为双引号字符串现在通常保存在不可修改的数据中分割）。
  • 预先考虑一些无论大小的int值都意味着对齐问题。 初始长度应该对齐，但是没有理由为字符数据做这件事（再次强调字符串的对齐意味着将它们视为一串字节时会出现问题）。
  • 在编译时，对于常量字符串（sizeof），长度是已知的。 那么为什么有人希望将它存储在内存中，并将其存储到实际数据中？
  • 以几乎所有其他人的方式C，字符串被视为char数组。 由于数组长度不是由C管理的，因此逻辑长度不受字符串管理。 唯一令人惊讶的是最后添加了0项，但在双引号之间输入字符串时，这只是核心语言级别。 用户可以完美地调用字符串操作函数的传递长度，甚至可以使用普通的memcopy。 深圳只是一个设施。 在大多数其他语言中，数组长度是管理的，对于字符串来说是合乎逻辑的。
  • 在现代，无论如何1字节字符集是不够的，你经常需要处理编码的unicode字符串，其中字符数与字节数非常不同。 这意味着用户可能需要的不仅仅是“大小”，还包括其他信息。 关于这些其他有用的信息，保持长度不会使用任何东西（特别是没有自然的地方来存储它们）。

    • 也就是说，在标准C字符串确实效率低下的罕见情况下，无需抱怨。 Libs可用。 如果我遵循这个趋势，我应该抱怨标准C不包含任何正则表达式支持函数......但是真的每个人都知道它不是一个真正的问题，因为有用于此目的的库。 所以，当需要字符串操作效率时，为什么不使用像bstring这样的库？ 甚至是C ++字符串？

    编辑 ：我最近看了D字符串。 足够有趣的是，选择的解决方案既不是大小前缀也不是零终止。 和C一样，用双引号括起来的文字字符串对于不可变的char数组来说简直就是短手，而且该语言也有一个字符串关键字，意思是（不可变的char数组）。

    但是D阵列比C阵列要丰富得多。 在静态数组的情况下，长度在运行时是已知的，所以不需要存储长度。 编译器在编译时有它。 在动态数组的情况下，长度是可用的，但D文档没有说明它保存的位置。 就我们所知，编译器可以选择将它保存在某个寄存器中，或者存储在远离字符数据的一些变量中。

    在普通的char数组或非literal字符串中，没有最终的零，因此如果程序员想从D调用某个C函数，程序员必须自行放置它。在字符串的特殊情况下，D编译器仍然在每个字符串的末尾（以便于转换为C字符串以使调用C函数更容易？），但是此零不是字符串的一部分（D不会以字符串大小计算）。

    唯一让我感到失望的是字符串应该是utf-8，但是即使使用多字节字符，长度显然仍然会返回大量字节（至少在我的编译器gdc中是这样）。 我不清楚它是编译器错误还是目的。 （好吧，我可能已经知道发生了什么事情，对D编译器说你的源代码使用utf-8，你必须在开始时写一些愚蠢的字节顺序标记，我写愚蠢的是因为我知道不是编辑器这样做，尤其是对于UTF- 8应该是ASCII兼容的）。

    链接地址: http://www.djcxy.com/p/73547.html

    上一篇: What's the rationale for null terminated strings?

    下一篇: O2, and bitfields