什么是空string的基本原理？

就像我喜欢C和C ++一样，我忍不住用零结尾的string来select我的头：

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

这些事情中有几个比C更早出现，所以C不知道它们是有意义的。 然而，在C成立之前，有好几个都很清楚。 为什么会selectnull终止的string，而不是明显优越的长度前缀？

编辑 ：因为有些人在我的效率点上面提出了一些事实 （而且不喜欢那些我已经提供的），他们来自于一些事情：

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

从下面的答案，这些是一些情况下，空string更有效：

  • 当你需要中断一个string的开始，并且需要将它传递给某种方法。 即使允许销毁原始string，也不能在长度为前缀的情况下实时执行此操作，因为长度前缀可能需要遵循alignment规则。
  • 在某些情况下，你只是逐个字符地循环，你可能会保存一个CPU寄存器。 请注意，这只适用于你没有dynamic分配string的情况（因为那么你必须释放它，因此必须使用你保存的CPU寄存器来保存你最初从malloc和朋友那里得到的指针）。

以上都不是长度和连续的一样普遍。

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

  • 你需要切断string的结尾

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

从马的嘴里

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

Dennis M Ritchie， C语言的发展

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

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

鉴于下面的狂风暴雨：

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

这个问题是作为一个Length Prefixed Strings (LPS)与zero terminated strings (SZ)东西，但主要暴露长度前​​缀string的好处。 这似乎是压倒性的，但说实话，我们也应该考虑LPS的缺点和深圳的优势。

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

零终止string的优点（我看到）：

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

也就是说，在标准Cstring确实效率低下的情况下，不需要抱怨。 Libs可用。 如果我遵循这个趋势，我应该抱怨标准C不包括任何正则expression式支持function…但是真的每个人都知道这不是一个真正的问题，因为有这样的库可用。 所以当需要string操作效率的时候，为什么不使用像bstring这样的库呢？ 甚至是C ++string？

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

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

在普通的char数组或非literalstring中，没有最终的零，因此如果程序员想从D中调用一些C函数，程序员必须自己放置它。在string的特殊情况下，D编译器仍然在每个string的末尾（为了方便地转换成Cstring，使调用C函数更容易？），但是这个零不是string的一部分（D不计算string大小）。

唯一令我失望的是string应该是utf-8，但是即使在使用多字节字符时，长度显然仍然会返回一些字节（至less在我的编译器gdc中是这样）。 我不清楚这是一个编译器错误还是目的。 （好吧，我可能已经知道了发生了什么事情，对D编译器来说，使用utf-8，你必须在开始时写一些愚蠢的字节顺序标记，因为我知道不是编辑器，所以我写愚蠢的，特别是对于UTF- 8应该是ASCII兼容的）。

我认为，它有历史的原因，并发现在维基百科 ：

在C语言（以及它所源自的语言）被开发出来的时候，内存是非常有限的，所以只用一个字节的开销来存储一个string的长度是有吸引力的。 当时唯一受欢迎的替代方法，通常称为“Pascalstring”（虽然也被早期版本的BASIC使用）使用前导字节来存储string的长度。 这允许string包含NUL，并且find长度只需要一个存储器访问（O（1）（常量）时间）。 但是一个字节将长度限制为255.这个长度限制比Cstring的问题要严格得多，所以Cstring一般就胜出了。

Calavera是正确的 ，但是由于人们似乎没有明白他的观点，我会提供一些代码示例。

首先，我们来考虑C是什么：一种简单的语言，所有的代码都可以直接翻译成机器语言。 所有types都适用于寄存器和堆栈，并且不需要操作系统或大运行时库来运行，因为它是为了写这些东西（一个非常适合的任务，考虑到甚至不是今天可能的竞争对手）。

如果C有一个stringtypes，比如int或者char ，它将是一个不适合在寄存器或堆栈中的types，并且需要以任何方式处理内存分配（及其所有支持基础设施）。 所有这些违背了C的基本原则

所以，C中的一个string是： 

 char s*;

所以，我们假设这是以长度为前缀的。 我们来编写代码来连接两个string： 

 char* concat(char* s1, char* s2) { /* What? What is the type of the length of the string? */ int l1 = *(int*) s1; /* How much? How much must I skip? */ char *s1s = s1 + sizeof(int); int l2 = *(int*) s2; char *s2s = s2 + sizeof(int); int l3 = l1 + l2; char *s3 = (char*) malloc(l3 + sizeof(int)); char *s3s = s3 + sizeof(int); memcpy(s3s, s1s, l1); memcpy(s3s + l1, s2s, l2); *(int*) s3 = l3; return s3; }

另一种select是使用一个结构来定义一个string： 

 struct { int len; /* cannot be left implementation-defined */ char* buf; }

在这一点上，所有的string操作都需要进行两次分配，实际上，这意味着你要通过一个库来处理它。

有趣的是…这样的结构确实存在于C中！ 他们只是没有用于你的日常显示消息给用户处理。

所以，这就是Calavera所做的一点： C中没有stringtypes 。 要做任何事情，你必须把一个指针作为一个指向两种不同types的指针来解码，然后它变得非常相关，一个string的大小是多less，而不能只剩下“实现定义”。

现在，C 可以处理内存，并且库中的mem函数（在<string.h> ，甚至！）提供了所有需要处理内存的工具，作为一对指针和大小。 C中所谓的“string”只是为了一个目的而创build的：在写作用于文本terminal的操作系统的上下文中显示消息。 而且，为此，空终止就足够了。

显然，为了性能和安全性，当你使用它时，你会想要保持一个string的长度，而不是重复执行strlen或其等价物。 然而，将长度存储在string内容的固定位置是一个令人难以置信的糟糕的devise。 正如Jörgen在关于Sanjit的回答的评论中指出的那样，它排除了将string的尾部视为string，例如，如果不分配新的内存，就会导致很多常见的操作，如path_to_filename或filename_to_extension （并导致失败和error handling）。 当然，还有一个问题是，没有人会同意string长度字段应该占用多less字节（大量坏的“Pascalstring”语言使用了16位字段，甚至是24位字段，这样就排除了长string的处理）。

C让程序员select如何/何地/如何存储长度的devise更为灵活和强大。 但是，程序员当然要聪明。 C惩罚愚蠢的程序崩溃，研磨到停顿，或给你的敌人的根源。

懒惰，注册节俭和可移植性，考虑到任何语言的汇编语言，特别是在汇编之上的一步（因此inheritance了大量汇编遗留代码）的C语言。 你会同意作为一个空字符在这些ASCII的日子里是无用的，它（也可能是一个EOF控制字符）。

让我们看看伪代码 

 function readString(string) // 1 parameter: 1 register or 1 stact entries pointer=addressOf(string) while(string[pointer]!=CONTROL_CHAR) do read(string[pointer]) increment pointer

共有1个注册使用

情况2 

  function readString(length,string) // 2 parameters: 2 register used or 2 stack entries pointer=addressOf(string) while(length>0) do read(string[pointer]) increment pointer decrement length

共使用了2个寄存器

这在当时可能看起来是短视的，但考虑到代码和注册的节俭（当时是PREMIUM，当你知道的时候，他们使用打卡）。 因此速度更快（当处理器速度可以以kHz计）时，这个“Hack”对于无寄存器的处理器来说是相当不错的。

为了参数，我将实现2个常见的string操作 

 stringLength(string) pointer=addressOf(string) while(string[pointer]!=CONTROL_CHAR) do increment pointer return pointer-addressOf(string)

复杂性O（n）在大多数情况下，PASCALstring是O（1），因为string的长度被预先挂载到string结构（这也意味着该操作将不得不在早期阶段进行）。 

 concatString(string1,string2) length1=stringLength(string1) length2=stringLength(string2) string3=allocate(string1+string2) pointer1=addressOf(string1) pointer3=addressOf(string3) while(string1[pointer1]!=CONTROL_CHAR) do string3[pointer3]=string1[pointer1] increment pointer3 increment pointer1 pointer2=addressOf(string2) while(string2[pointer2]!=CONTROL_CHAR) do string3[pointer3]=string2[pointer2] increment pointer3 increment pointer1 return string3

复杂性O（n）和预先考虑string长度不会改变操作的复杂性，而我承认它会花费3倍的时间。

另一方面，如果使用PASCALstring，则必须重新devise用于考虑寄存器长度和位字节顺序的API，PASCALstring具有255字符（0xFF）的已知限制，因为长度存储在1个字节（8位），你想要一个更长的string（16bits->任何东西），你将不得不考虑在你的代码层的体系结构，这意味着在大多数情况下不兼容的stringAPI，如果你想要更长的string。

例：

一个文件是用一个8位计算机上的前缀stringapi编写的，然后在32位计算机上读取，那么懒惰程序会认为你的4字节是string的长度，然后分配大量的内存然后尝试读取那么多字节。 另一种情况是PPC将32字节的string读到一个x86（big endian）上，当然如果你不知道另一个是由另一个写的话会有麻烦。 1字节长度（0x00000001）将变为16777216（0x0100000），即16 MB用于读取1字节的string。 当然你可以说人们应该同意一个标准，但即使是16bit的unicode也只能得到一个小小的大的sorting。

当然C也会有问题，但是这里提出的问题很less受到影响。

在许多方面，C是原始的。 我喜欢它。

It was a step above assembly language, giving you nearly the same performance with a language that was much easier to write and maintain.

The null terminator is simple and requires no special support by the language.

Looking back, it doesn't seem that convenient. But I used assembly language back in the 80s and it seemed very convenient at the time. I just think software is continually evolving, and the platforms and tools continually get more and more sophisticated.

Assuming for a moment that C implemented strings the Pascal way, by prefixing them by length: is a 7 char long string the same DATA TYPE as a 3-char string? If the answer is yes, then what kind of code should the compiler generate when I assign the former to the latter? Should the string be truncated, or automatically resized? If resized, should that operation be protected by a lock as to make it thread safe? The C approach side stepped all these issues, like it or not 🙂

Somehow I understood the question to imply there's no compiler support for length-prefixed strings in C. The following example shows, at least you can start your own C string library, where string lengths are counted at compile time, with a construct like this: 

 #define PREFIX_STR(s) ((prefix_str_t){ sizeof(s)-1, (s) }) typedef struct { int n; char * p; } prefix_str_t; int main() { prefix_str_t string1, string2; string1 = PREFIX_STR("Hello!"); string2 = PREFIX_STR("Allows \0 chars (even if printf directly doesn't)"); printf("%d %s\n", string1.n, string1.p); /* prints: "6 Hello!" */ printf("%d %s\n", string2.n, string2.p); /* prints: "48 Allows " */ return 0; }

This won't, however, come with no issues as you need to be careful when to specifically free that string pointer and when it is statically allocated (literal char array).

Edit: As a more direct answer to the question, my view is this was the way C could support both having string length available (as a compile time constant), should you need it, but still with no memory overhead if you want to use only pointers and zero termination.

Of course it seems like working with zero-terminated strings was the recommended practice, since the standard library in general doesn't take string lengths as arguments, and since extracting the length isn't as straightforward code as char * s = "abc" , as my example shows.

The null termination allows for fast pointer based operations.

"Even on a 32 bit machine, if you allow the string to be the size of available memory, a length prefixed string is only three bytes wider than a null terminated string."

First, extra 3 bytes may be considerable overhead for short strings. In particular, a zero-length string now takes 4 times as much memory. Some of us are using 64-bit machines, so we either need 8 bytes to store a zero-length string, or the string format can't cope with the longest strings the platform supports.

There may also be alignment issues to deal with. Suppose I have a block of memory containing 7 strings, like "solo\0second\0\0four\0five\0\0seventh". The second string starts at offset 5. The hardware may require that 32-bit integers be aligned at an address that is a multiple of 4, so you have to add padding, increasing the overhead even further. The C representation is very memory-efficient in comparison. (Memory-efficiency is good; it helps cache performance, for example.)

One point not yet mentioned: when C was designed, there were many machines where a 'char' was not eight bits (even today there are DSP platforms where it isn't). If one decides that strings are to be length-prefixed, how many 'char's worth of length prefix should one use? Using two would impose an artificial limit on string length for machines with 8-bit char and 32-bit addressing space, while wasting space on machines with 16-bit char and 16-bit addressing space.

If one wanted to allow arbitrary-length strings to be stored efficiently, and if 'char' were always 8-bits, one could–for some expense in speed and code size–define a scheme were a string prefixed by an even number N would be N/2 bytes long, a string prefixed by an odd value N and an even value M (reading backward) could be ((N-1) + M*char_max)/2, etc. and require that any buffer which claims to offer a certain amount of space to hold a string must allow enough bytes preceding that space to handle the maximum length. The fact that 'char' isn't always 8 bits, however, would complicate such a scheme, since the number of 'char' required to hold a string's length would vary depending upon the CPU architecture.

Many design decisions surrounding C stem from the fact that when it was originally implemented, parameter passing was somewhat expensive. Given a choice between eg 

 void add_element_to_next(arr, offset) char[] arr; int offset; { arr[offset] += arr[offset+1]; } char array[40]; void test() { for (i=0; i<39; i++) add_element_to_next(array, i); }

与 

 void add_element_to_next(ptr) char *p; { p[0]+=p[1]; } char array[40]; void test() { int i; for (i=0; i<39; i++) add_element_to_next(arr+i); }

the latter would have been slightly cheaper (and thus preferred) since it only required passing one parameter rather than two. If the method being called didn't need to know the base address of the array nor the index within it, passing a single pointer combining the two would be cheaper than passing the values separately.

While there are many reasonable ways in which C could have encoded string lengths, the approaches that had been invented up to that time would have all required functions that should be able to work with part of a string to accept the base address of the string and the desired index as two separate parameters. Using zero-byte termination made it possible to avoid that requirement. Although other approaches would be better with today's machines (modern compilers often pass parameters in registers, and memcpy can be optimized in ways strcpy()-equivalents cannot) enough production code uses zero-byte terminated strings that it's hard to change to anything else.

PS–In exchange for a slight speed penalty on some operations, and a tiny bit of extra overhead on longer strings, it would have been possible to have methods that work with strings accept pointers directly to strings, bounds-checked string buffers, or data structures identifying substrings of another string. A function like "strcat" would have looked something like [modern syntax] 

 void strcat(unsigned char *dest, unsigned char *src) { struct STRING_INFO d,s; str_size_t copy_length; get_string_info(&d, dest); get_string_info(&s, src); if (d.si_buff_size > d.si_length) // Destination is resizable buffer { copy_length = d.si_buff_size - d.si_length; if (s.src_length < copy_length) copy_length = s.src_length; memcpy(d.buff + d.si_length, s.buff, copy_length); d.si_length += copy_length; update_string_length(&d); } }

A little bigger than the K&R strcat method, but it would support bounds-checking, which the K&R method doesn't. Further, unlike the current method, it would be possible to easily concatenate an arbitrary substring, eg 

 /* Concatenate 10th through 24th characters from src to dest */ void catpart(unsigned char *dest, unsigned char *src) { struct SUBSTRING_INFO *inf; src = temp_substring(&inf, src, 10, 24); strcat(dest, src); }

Note that the lifetime of the string returned by temp_substring would be limited by those of s and src , which ever was shorter (which is why the method requires inf to be passed in–if it was local, it would die when the method returned).

In terms of memory cost, strings and buffers up to 64 bytes would have one byte of overhead (same as zero-terminated strings); longer strings would have slightly more (whether one allowed amounts of overhead between two bytes and the maximum required would be a time/space tradeoff). A special value of the length/mode byte would be used to indicate that a string function was given a structure containing a flag byte, a pointer, and a buffer length (which could then index arbitrarily into any other string).

Of course, K&R didn't implement any such thing, but that's most likely because they didn't want to spend much effort on string handling–an area where even today many languages seem rather anemic.

According to Joel Spolsky in this blog post ,

It's because the PDP-7 microprocessor, on which UNIX and the C programming language were invented, had an ASCIZ string type. ASCIZ meant "ASCII with a Z (zero) at the end."

After seeing all the other answers here, I'm convinced that even if this is true, it's only part of the reason for C having null-terminated "strings". That post is quite illuminating as to how simple things like strings can actually be quite hard.

gcc accept the codes below:

char s[4] = "abcd";

and it's ok if we treat is as an array of chars but not string. That is, we can access it with s[0], s[1], s[2], and s[3], or even with memcpy(dest, s, 4). But we'll get messy characters when we trying with puts(s), or worse with strcpy(dest, s).

Interesting Posts