尽管我喜欢C和C,但我还是忍不住在选择空终止字符串时 grab 了头脑:
-
长度前缀(即Pascal)字符串在C之前存在
-
长度前缀字符串通过允许恒定时间长度查找使几种算法更快 .
-
长度前缀字符串使得更容易导致缓冲区溢出错误 .
-
即使在32位机器上,如果允许字符串为可用内存的大小,则长度前缀字符串仅比空终止字符串宽三个字节 . 在16位机器上,这是一个字节 . 在64位机器上,4GB是一个合理的字符串长度限制,但即使你想将它扩展到机器字的大小,64位机器通常有足够的内存使额外的七个字节排序为空参数 . 我知道最初的C标准是针对极其糟糕的机器(就内存而言)而写的,但效率论证并没有把我卖给我 .
-
几乎所有其他语言(即Perl,Pascal,Python,Java,C#等)都使用长度前缀字符串 . 这些语言通常在字符串操作基准测试中胜过C,因为它们对字符串更有效 .
-
C使用
std::basic_string
模板纠正了这一点,但是期望空终止字符串的普通字符数组仍然很普遍 . 这也是不完美的,因为它需要堆分配 . -
空终止字符串必须保留一个字符(即null),该字符不能存在于字符串中,而长度前缀字符串可以包含嵌入的空值 .
这些事情中有几个最近比C更明显,所以C对于不了解它们是有意义的 . 然而,在C出现之前,有几个很平常 . 为什么选择空终止字符串而不是明显优越的长度前缀?
EDIT :由于有些人在我的效率点上询问了事实(并且不喜欢我已提供的事实),因此它们源于以下几点:
-
使用空终止字符串的Concat需要O(n m)时间复杂度 . 长度前缀通常只需要O(m) .
-
使用空终止字符串的长度需要O(n)时间复杂度 . 长度前缀为O(1) .
-
Length和concat是迄今为止最常见的字符串操作 . 在某些情况下,空终止字符串可以更有效,但这些情况发生得更少 .
从下面的答案中,这些是空终止字符串更有效的一些情况:
-
当您需要切断字符串的开头并需要将其传递给某个方法时 . 即使您被允许销毁原始字符串,也不能在长度前缀的常量时间内执行此操作,因为长度前缀可能需要遵循对齐规则 .
-
在某些情况下,你动态分配字符串(因为那时你必须释放它,因此必须使用你保存的CPU寄存器来保存你最初从malloc和朋友那里得到的指针) .
以上都不像长度和连续那样常见 .
在下面的答案中还有一个断言:
- 你需要切断字符串的结尾
但是这个不正确 - 它与null终止和长度前缀字符串的时间相同 . (Null终止字符串只是在你希望新结束的地方粘贴一个空值,长度前缀只是从前缀中减去 . )
17 回答
空终止允许基于快速指针的操作 .
还有一点尚未提及:当设计C时,有许多机器的'char'不是8位(即使在今天有DSP平台也没有) . 如果确定字符串是长度前缀的,那么应该使用多少'char'的长度前缀值?使用两个会对具有8位字符和32位寻址空间的计算机的字符串长度施加一个人为限制,同时在具有16位字符和16位寻址空间的计算机上浪费空间 .
如果一个人想要有效地存储任意长度的字符串,并且如果'char'总是8位,那么可以 - 在速度和代码大小上花费一些费用 - 定义一个方案是一个以偶数为前缀的字符串N将是N / 2字节长,以奇数值N为前缀的字符串和偶数值M(向后读取)可以是((N-1)M * char_max)/ 2等,并且要求任何声明的缓冲区提供一定量的空间来保存字符串必须允许在该空间之前有足够的字节来处理最大长度 . 然而,'char'并不总是8位的事实会使这种方案复杂化,因为保持字符串长度所需的'char'的数量将根据CPU架构而变化 .
C没有字符串作为语言的一部分 . C中的'string'只是指向char的指针 . 所以也许你问的是错误的问题 .
“遗漏字符串类型的理由是什么”可能更具相关性 . 为此,我要指出C不是面向对象的语言,只有基本的 Value 类型 . 字符串是更高级别的概念,必须通过某种方式组合其他类型的值来实现 . C处于较低的抽象层次 .
鉴于下面的狂风暴:
我只想指出,我并不是说这是一个愚蠢或糟糕的问题,或者表示字符串的C方式是最佳选择 . 我试图澄清,如果考虑到C没有将字符串作为数据类型与字节数组区分开的机制,那么问题会更简洁 . 鉴于当今计算机的处理和内存能力,这是最佳选择吗?可能不是 . 但后见之明总是20/20和所有:)
懒惰,注册节俭和可移植性考虑到任何语言的汇编,特别是C比汇编高出一步(因此继承了许多汇编遗留代码) . 您会同意,因为null char在那些ASCII天中是无用的(它可能和EOF控件字符一样好) .
让我们看看伪代码
共有1个注册用途
案例2
共有2个寄存器
那个时候看起来可能是短视的,但考虑到代码和注册的节俭(当时是PREMIUM,你知道的时候,他们使用穿孔卡) . 因此速度更快(当处理器速度可以以kHz为单位计算时),这种“Hack”非常好并且可以轻松地移植到无寄存器处理器 .
为了论证,我将实现2个常见的字符串操作
复杂度O(n)其中大多数情况下PASCAL字符串是O(1),因为字符串的长度预先设置为字符串结构(这也意味着此操作必须在较早阶段进行) .
复杂度O(n)和前置字符串长度不会改变操作的复杂性,而我承认它需要3倍的时间 .
另一方面,如果你使用PASCAL字符串,你必须重新设计你的API以获取帐户寄存器长度和位端字节,PASCAL字符串得到众所周知的255 char(0xFF)限制,因为长度存储在1字节(8位) ),你需要一个更长的字符串(16位 - >任何东西),你需要考虑代码的一层中的架构,如果你想要更长的字符串,这在大多数情况下意味着不兼容的字符串API .
例:
一个文件是用8位计算机上的前缀字符串api编写的,然后必须在32位计算机上读取,懒惰程序会认为你的4字节是字符串的长度然后分配那么多的内存然后尝试读取那么多字节 . 另一种情况是PPC 32字节字符串读取(小端)到x86(大端),当然如果你不知道一个是由另一个写,那将是麻烦 . 1字节长度(0x00000001)将变为16777216(0x0100000),读取1字节字符串为16 MB . 当然你会说人们应该就一个标准达成一致,但即使是16位的unicode也只能获得很少的大字节 .
当然,C也有它的问题,但是受到这里提出的问题的影响很小 .
Not a Rationale necessarily but a counterpoint to length-encoded
就内存而言,某些形式的动态长度编码优于静态长度编码,这完全取决于使用情况 . 只需查看UTF-8即可获得证明 . 它本质上是一个可扩展的字符数组,用于编码单个字符 . 这对每个扩展字节使用一位 . NUL终止使用8位 . 我认为长度前缀可以通过使用64位合理地称为无限长度 . 你经常看到多余比特的情况是决定因素 . 只有1个极大的字符串?谁在乎你是使用8位还是64位?很多小字符串(即英文单词串)?那么你的前缀成本很高 .
允许节省时间的长度前缀字符串是 not a real thing . 无论您提供的数据是否需要提供长度,您都必须真正提供必须编码为字符串的动态数据 . 这些大小在算法中的某个点计算 . 可以提供用于存储空终止字符串大小的单独变量 . 这使得时间节省的比较没有实际意义 . 一个人在最后只有一个额外的NUL ...但如果长度编码没有't include that NUL then there' s,两者之间几乎没有区别 . 根本不需要算法更改 . 只需要预先通过,您必须手动设计自己,而不是让编译器/运行时为您完成 . C主要是关于手动操作 .
长度 - 前缀是可选的是卖点 . 我并不总是需要算法的额外信息,因此需要为每个字符串执行此操作,这使得我的预计算计算时间永远不会低于O(n) . (即硬件随机数生成器1-128 . 我可以从“无限字符串”中拉出 . 假设它只生成字符这么快 . 所以我们的字符串长度一直在变化 . 但我对数据的使用可能并不关心如何许多随机字节我有 . 它只需要在请求后立即获取下一个可用的未使用字节 . 我可以在设备上等待 . 但我也可以预先读取一个字符缓冲区 . 长度比较是不必要的计算浪费 . 空检查更有效 . )
长度前缀是防止缓冲区溢出的好方法吗?因此,图书馆功能和实施的合理使用 . 如果我传入格式错误的数据怎么办?我的缓冲区长2个字节,但我告诉它的功能是7! Ex: 如果想要将gets()用于已知数据,它可能会进行内部缓冲区检查,测试编译缓冲区和malloc()调用并仍然遵循规范 . 如果它被用作未知STDIN的管道到达未知缓冲区那么显然可以长度为某些流和输入加前缀,你就是不能 . 这意味着长度检查必须内置到算法中,而不是打字系统的神奇部分 . TL;DR NUL终止永远不必是不安全的,它只是通过滥用这种方式结束 .
counter-counter point: NUL终止对二进制文件很烦人 . 你需要在这里做长度前缀或者以某种方式转换NUL字节:转义码,范围重新映射等......这当然意味着更多内存使用/减少信息/更多操作每字节 . 长度前缀主要在这里赢得战争 . 转换的唯一好处是不必编写额外的函数来覆盖长度前缀字符串 . 这意味着在您更优化的子O(n)例程上,您可以让它们自动充当其O(n)等价物,而无需添加更多代码 . 当然,在NUL重弦上使用时,下侧是时间/内存/压缩浪费 . 根据您最终复制以对二进制数据进行操作的库的数量,仅使用长度前缀字符串可能是有意义的 . 也就是说,也可以使用长度前缀字符串执行相同操作... -1长度可能意味着NUL终止,您可以在长度终止内使用NUL终止的字符串 .
Concat:"O(n+m) vs O(m)"我'm assuming your referring to m as the total length of the string after concatenating because they both have to have that number of operations minimum (you can' t只是粘贴到字符串1,如果你必须重新分配怎么办?) . 而且我假设n是一个神秘的操作量,因为预先计算而不再需要做 . 如果是这样,那么答案很简单:预先计算 . 如果你总是有足够的内存来不需要重新分配,并且在字符串1之后's the basis of the big-O notation then the answer is even more simple: do binary search on allocated memory for end of string 1, clearly there'是一个无限零的大样本,我们就不用担心realloc了 . 在那里,很容易得到n到log(n),我几乎没有尝试过 . 如果你还记得log(n)在实际计算机上基本上只有64,这基本上就像是说O(64 m),基本上是O(m) . (是的,逻辑已被用于今天正在使用的实际数据结构的运行时分析 . 这不是废话我的头脑 . )
Concat()/ Len()再次:记住结果 . 简单 . 如果可能/必要,将所有计算变为预计算 . 这是一个算法决策 . 它不是语言的强制约束 .
NUL终止时,字符串后缀传递更容易/可能 . 根据长度前缀的实现方式,它可能对原始字符串具有破坏性,有时甚至无法实现 . 要求复制并传递O(n)而不是O(1) .
对于NUL终止和长度前缀,参数传递/解引用较少 . 显然是因为你传递的信息较少 . 如果您不需要长度,那么这将节省大量空间并允许优化 .
你可以作弊 . 它's really just a pointer. Who says you have to read it as a string? What if you want to read it as a single character or a float? What if you want to do the opposite and read a float as a string? If you'小心你可以用NUL终止来做到这一点 . 您可以't do this with length-prefix, it'是一种与指针明显不同的数据类型 . 你很可能必须逐字节地构建一个字符串并获得长度 . 当然,如果你想要一个像整个浮点数(可能里面有一个NUL)的东西,你必须逐字节读取,但细节留待你决定 .
TL;DR 您使用的是二进制数据吗?如果不是,那么NUL终止允许更多算法自由 . 如果是,那么代码数量与速度/内存/压缩是您的主要关注点 . 两种方法或记忆的混合可能是最好的 .
Calavera是right,但是因为人们不提供一些代码示例 .
首先,让's consider what C is: a simple language, where all code has a pretty direct translation into machine language. All types fit into registers and on the stack, and it doesn' t需要一个操作系统或一个大的运行时库来运行,因为它是为了编写这些东西(这项任务非常适合,考虑到今天甚至没有可能的竞争者) .
如果C具有
string
类型,如int
或char
,则它将是一种不适合寄存器或堆栈的类型,并且需要以任何方式处理内存分配(及其所有支持基础结构) . 所有这些都违背了C的基本原则 .所以,C中的字符串是:
那么,让我们假设这是长度前缀的 . 让我们编写代码来连接两个字符串:
另一种方法是使用结构来定义字符串:
此时,所有字符串操作都需要进行两次分配,这在实践中意味着你会通过图书馆来处理它 .
有趣的是......结构确实存在于C中!它们不会用于您日常向用户处理显示消息 .
所以,这是Calavera正在制作的观点:C中没有字符串类型 . 要对它做任何事情,你必须使用指针并将其解码为指向两种不同类型的指针,然后它变得非常相关是字符串的大小,不能只保留为"implementation defined" .
现在,C无论如何都可以处理内存,库中的
mem
函数(在_338726中,甚至!)提供了处理内存所需的所有工具,作为一对指针和大小 . C中所谓的"strings"只是出于一个目的:在写入用于文本终端的操作系统的上下文中显示消息 . 而且,为此,空终止就足够了 .我认为,它有历史原因并发现this in wikipedia:
假设C实现了Pascal方式的字符串,通过长度为它们加前缀:是一个7字符长的字符串,相同的DATA TYPE是3-char字符串?如果答案是肯定的,那么当我将前者分配给后者时,编译器应该生成什么样的代码?该字符串应该被截断,还是自动调整大小?如果调整大小,该操作是否应该通过锁保护以使其线程安全? C方法方面解决了所有这些问题,无论是否喜欢:)
首先,对于短字符串,额外的3个字节可能是相当大的开销特别是,零长度字符串现在需要4倍的内存 . 我们中的一些人正在使用64位计算机,因此我们要么需要8个字节来存储零长度字符串,要么字符串格式无法处理平台支持的最长字符串 .
可能还存在对齐问题需要处理 . 假设我有一个包含7个字符串的内存块,例如“solo \ 0second \ 0 \ 0four \ 0five \ 0 \ 0seventh” . 第二个字符串从偏移量5开始 . 硬件可能要求32位整数在4的倍数处对齐,因此您必须添加填充,从而进一步增加开销 . 相比之下,C表示非常节省内存 . (内存效率很好;例如,它有助于缓存性能 . )
这个问题被称为
Length Prefixed Strings (LPS)
vszero terminated strings (SZ)
,但主要是暴露长度前缀字符串的好处 . 这可能看起来势不可挡,但说实话,我们也应该考虑LPS的缺点和SZ的优势 .据我了解,这个问题甚至可以被理解为一种偏见的方式来询问“零终结字符串的优点是什么?” .
Advantages (I see) of Zero Terminated Strings:
非常简单,无需在语言中引入新概念,char数组/ char指针就可以做到 .
核心语言只包含最小的语法糖,可以将双引号之间的内容转换为一堆字符(实际上是一堆字节) . 在某些情况下,它可用于初始化与文本完全无关的内容 . 例如,xpm图像文件格式是包含编码为字符串的图像数据的有效C源 .
_999_顺便说一句,你 can 在字符串文字中加零,编译器也会在文字的末尾添加另一个:
"this\0is\0valid\0C"
. 它是一个字符串?还是四串?或者一堆字节......平面实现,没有隐藏间接,没有隐藏整数 .
没有涉及隐藏的内存分配(好吧,一些臭名昭着的非标准函数,如strdup执行分配,但这主要是问题的根源) .
对于小型或大型硬件没有具体问题(想象一下在8位微控制器上管理32位前缀长度的负担,或者将字符串大小限制为小于256字节的限制,这是我在Turbo Pascal之前实际遇到的一个问题) .
字符串操作的实现只是极少数非常简单的库函数
主要使用字符串的效率:从已知的开始顺序读取的常量文本(主要是消息给用户) .
终止零甚至不是强制性的,所有必要的工具来操作像一堆字节一样的字符是可用的 . 在C中执行数组初始化时,您甚至可以避免使用NUL终结符 . 只需设置合适的尺寸 .
char a[3] = "foo";
是有效的C(不是C),并且不会在a中放入最后的零 .与unix的观点一致"everything is file",包括"files",它没有像stdin,stdout那样的内在长度 . 您应该记住,开放的读写原语是以非常低的级别实现的 . 它们不是库调用,而是系统调用 . 并且相同的API用于二进制或文本文件 . 文件读取原语获取缓冲区地址和大小并返回新大小 . 并且您可以使用字符串作为缓冲区来编写 . 使用另一种字符串表示意味着您不能轻易地使用文字字符串作为输出的缓冲区,或者在将其转换为
char*
时必须使其具有非常奇怪的行为 . 即不返回字符串的地址,而是返回实际数据 .非常容易操作从文件中就地读取的文本数据,没有无用的缓冲区副本,只需在正确的位置插入零(好吧,不是真的用现代C作为双引号字符串是const char数组,现在通常保持不可修改数据段) .
前置一些任何大小的int值都意味着对齐问题 . 初始长度应该是对齐的,但是对于字符数据没有理由这样做(并且再次强制字符串对齐会在将它们视为一堆字节时意味着问题) .
在编译时,
length对于常量文字字符串(sizeof)是已知的 . 那么为什么有人想将它存储在内存中,并将其置于实际数据之前呢?
在某种程度上C(几乎)所有其他人都在做,字符串被视为char数组 . 由于数组长度不由C管理,因此对于字符串不管理逻辑长度 . 唯一令人惊讶的是,最后添加了0项,但字符串的's just at core language level when typing a string between double quotes. Users can perfectly call string manipulation functions passing length, or even use plain memcopy instead. SZ are just a facility. In most other languages array length is managed, it'逻辑是相同的 .
在现代,无论如何1字节字符集是不够的,你经常需要处理编码的unicode字符串,其中字符数的字节数非常不同 . 这意味着用户可能想要的不仅仅是"just the size",还有其他信息 . 对于这些其他有用的信息,保持长度不使用任何东西(特别是没有自然存储它们的地方) .
也就是说,在标准C字符串确实效率低下的罕见情况下,无需抱怨 . Libs可用 . 如果我遵循这一趋势,我应该抱怨标准C不包含任何正则表达式支持函数......但实际上每个人都知道这不是一个真正的问题,因为有可用于此目的的库 . 因此,当需要字符串操作效率时,为什么不使用像bstring这样的库?甚至是C字符串?
EDIT :我最近看了D strings . 有趣的是,选择的解决方案既不是大小前缀,也不是零终止 . 与在C中一样,用双引号括起来的文字字符串只是不可变字符数组的简写,而且该语言还有一个字符串关键字,意思是(不可变字符数组) .
但D阵列比C阵列更丰富 . 在静态数组的情况下,长度在运行时是已知的,因此不需要存储长度 . 编译器在编译时有它 . 在动态数组的情况下,长度可用,但D文档没有说明它的保存位置 . 据我们所知,编译器可以选择将其保存在某个寄存器中,或者存储在远离字符数据的某些变量中 .
在普通的char数组或非文字字符串上没有最终的零,因此程序员必须自己设置,如果他想从D调用一些C函数 . 在文字字符串的特殊情况下,但是D编译器仍然在每个字符串的结尾(允许简单地转换为C字符串以便更容易调用C函数?),但是这个零不是字符串的一部分(D不计算字符串大小) .
唯一令我失望的是字符串应该是utf-8,但是长度显然仍然会返回一些字节(至少在我的编译器gdc上是这样),即使使用多字节字符也是如此 . 我不清楚它是编译器错误还是目的 . (好吧,我可能已经知道发生了什么 . 要对D编译器说你的源使用utf-8你必须在开头放一些愚蠢的字节顺序标记 . 我写傻了因为我知道不是编辑那样做,特别是对于UTF- 8应该是ASCII兼容的) .
在许多方面,C是原始的 . 我喜欢它 .
它比汇编语言高出一步,使用更易于编写和维护的语言为您提供几乎相同的性能 .
null终止符很简单,不需要语言的特殊支持 .
回想起来,它似乎并不方便 . 但是我在80年代使用汇编语言,当时看起来非常方便 . 我只是认为软件在不断发展,平台和工具不断变得越来越复杂 .
显然,为了性能和安全,你'll want to keep the length of a string while you'重新使用它而不是重复执行
strlen
或等效的 . 但是,将长度存储在字符串内容之前的固定位置是一个非常糟糕的设计 . 正如Jörgen在对Sanjit的回答的评论中指出的那样,它排除了将字符串的尾部视为字符串,例如,如果没有分配新内存(并且导致失败和错误的可能性),很多常见的操作如path_to_filename
或filename_to_extension
是不可能的处理) . 然后当然存在这样的问题:没有人能够同意字符串长度字段应该占用多少字节(大量错误的"Pascal string"语言使用16位字段甚至24位字段来排除处理长字符串) .C让程序员选择是否/何处/如何存储长度的设计更加灵活和强大 . 但当然程序员必须聪明 . C惩罚愚蠢的程序崩溃,停止,或给你的敌人根 .
来自horse's mouth
Dennis M Ritchie,C语言的发展
根据Joel Spolsky的说法this blog post,
在看到所有其他答案之后,我确信即使这是真的,这也只是C具有空终止“字符串”的部分原因 . 关于字符串之类的简单事情实际上是多么简单,这个帖子非常有启发性 .
gcc接受以下代码:
char s [4] =“abcd”;
如果我们把它当作一个字符数组而不是字符串就可以了 . 也就是说,我们可以使用s [0],s [1],s [2]和s [3]访问它,甚至可以使用memcpy(dest,s,4)访问它 . 但是当我们尝试使用puts(s)时,我们会变得混乱,或者更糟糕的是使用strcpy(dest,s) .
围绕C的许多设计决策源于这样一个事实:当它最初实现时,参数传递有点昂贵 . 给出了例如
与
后者本来会稍微便宜(因而也是首选),因为它只需要传递一个参数而不是两个参数 . 如果被调用的方法不需要知道数组的基址而不知道其中的索引,则传递组合这两者的单个指针比分别传递值要便宜 .
虽然C有许多合理的方法可以编码字符串长度,但到目前为止发明的方法将具有所有必需的函数,这些函数应该能够使用字符串的一部分来接受字符串的基址和所需的索引作为两个单独的参数 . 使用零字节终止使得可以避免该要求 . 虽然其他方法对于今天的机器会更好(现代编译器通常在寄存器中传递参数,而memcpy可以用strcpy()方式进行优化 - 等价物不能)足够的 生产环境 代码使用零字节终止字符串,这很难改变为其他任何东西 .
PS - 作为对某些操作的轻微速度惩罚以及较长字符串上的一小部分额外开销的交换,可能有使用字符串的方法接受指针直接指向字符串,边界检查字符串缓冲区,或者标识另一个字符串的子字符串的数据结构 . 像"strcat"这样的函数看起来像[现代语法]
比K&R strcat方法稍大,但它会支持边界检查,而K&R方法则不然 . 此外,与当前方法不同,可以容易地连接任意子串,例如,
请注意,temp_substring返回的字符串的生命周期将受到
s
和src
的生命周期的限制,这些更短(这就是为什么该方法需要传入inf
- 如果它是本地的,它将在方法返回时死亡) .就内存成本而言,最多64字节的字符串和缓冲区将有一个字节的开销(与零终止字符串相同);较长的字符串会稍微多一点(两个字节之间允许的开销量是多少,所需的最大值是时间/空间权衡) . 长度/模式字节的特殊值将用于表示字符串函数被赋予一个包含标志字节,指针和缓冲区长度的结构(然后可以任意索引到任何其他字符串) .
当然,K&R没有实现任何这样的事情,但这很可能是因为他们不想在字符串处理方面花费太多精力 - 即使在今天,许多语言看起来都很贫乏 .
不知怎的,我理解这个问题暗示在C中没有编译器支持长度前缀的字符串 . 下面的例子显示,至少你可以启动自己的C字符串库,其中字符串长度在编译时计算,使用如下结构:
但是,这不会带来任何问题,因为您需要特别小心何时专门释放该字符串指针以及何时静态分配(文字
char
数组) .Edit: 作为这个问题的更直接的答案,我认为这是C可以支持字符串长度可用(作为编译时常量)的方式,如果你需要它,但如果你只想使用它仍然没有内存开销指针和零终止 .
当然,似乎使用零终止字符串是推荐的做法,因为标准库通常不像
char * s = "abc"
那样直接代码,正如我的例子所示 .