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

Question

尽管我喜欢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终止字符串只是在你希望新结束的地方粘贴一个空值,长度前缀只是从前缀中减去.)

Answer 1

从马的嘴里

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

_{Dennis M Ritchie,C语言的发展}

Answer 2

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

"遗漏字符串类型的理由是什么"可能更具相关性.为此,我要指出C不是面向对象的语言,只有基本的值类型.字符串是更高级别的概念,必须通过某种方式组合其他类型的值来实现.C处于较低的抽象层次.

鉴于下面肆虐的狂风:

我只想指出,我并不是说这是一个愚蠢或糟糕的问题,或者表示字符串的C方式是最好的选择.我试图澄清,如果考虑到C没有将字符串作为数据类型与字节数组区分开的机制,那么问题会更简洁.鉴于当今计算机的处理能力和内存能力,这是最佳选择吗？可能不是.但后见之明总是20/20和所有:)

Answer 3

这个问题被视为Length Prefixed Strings (LPS)vs的zero terminated strings (SZ)事情,但主要是暴露长度前​​缀字符串的好处.这可能看起来势不可挡,但说实话,我们也应该考虑LPS的缺点和SZ的优势.

据我所知,这个问题甚至可以被理解为一种偏见的方式来问"零终止字符串的优点是什么？".

Zero Terminated Strings的优点(我看到):

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

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

编辑:我最近看了D弦.有趣的是,选择的解决方案既不是大小前缀,也不是零终止.与在C中一样,用双引号括起来的文字字符串只是不可变字符数组的简写,并且该语言还有一个字符串关键字,意思是(不可变字符数组).

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

在普通的char数组或非文字字符串上没有最终的零,因此如果他想从D调用一些C函数,程序员必须自己设置.在文字字符串的特殊情况下,D编译器仍然在每个字符串的结尾(允许简单地转换为C字符串以便更容易调用C函数？),但是这个零不是字符串的一部分(D不计算字符串大小).

唯一令我失望的是字符串应该是utf-8,但是长度显然仍然会返回一些字节(至少在我的编译器gdc上是这样),即使使用多字节字符也是如此.我不清楚它是编译器错误还是目的.(好吧,我可能已经发现了发生了什么.要对D编译器说你的源使用utf-8你必须在开头放一些愚蠢的字节顺序标记.我写的很愚蠢因为我知道不是编辑那样做,特别是对于UTF- 8应该是ASCII兼容的).

Answer 4

我认为,它有历史原因,并在维基百科中发现:

在开发C(及其衍生的语言)时,内存非常有限,因此仅使用一个字节的开销来存储字符串的长度是很有吸引力的.当时唯一流行的替代方案,通常称为"Pascal字符串"(尽管早期版本的BASIC也使用),使用前导字节来存储字符串的长度.这允许字符串包含NUL并且使得查找长度仅需要一次存储器访问(O(1)(恒定)时间).但是一个字节将长度限制为255.这个长度限制比C字符串的问题限制得多,因此C字符串通常会胜出.

Answer 5

Calavera是对的,但由于人们似乎没有明白他的观点,我将提供一些代码示例.

首先,让我们考虑一下C是什么:一种简单的语言,所有代码都可以直接翻译成机器语言.所有类型都适合寄存器和堆栈,并且它不需要运行操作系统或大型运行时库,因为它是为了编写这些东西(一个非常适合的任务,考虑到那里甚至不是今天的竞争对手).

如果C有string类型,int或者类型,char那么它将是一种不适合寄存器或堆栈的类型,并且需要以任何方式处理内存分配(及其所有支持基础结构).所有这些都违背了C的基本原则.

所以,C中的字符串是:

char s*;

那么,让我们假设这是长度前缀的.让我们编写代码来连接两个字符串:

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;
}

另一种方法是使用结构来定义字符串:

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

此时,所有字符串操作都需要进行两次分配,实际上,这意味着您将通过库来对其进行任何处理.

有趣的是......这样的结构也用C存在!它们不会用于日常向用户处理显示消息.

所以,这是Calavera的观点:C中没有字符串类型.要对它做任何事情,你必须拿一个指针并将其解码为指向两种不同类型的指针,然后它变得非常相关什么是字符串的大小,并且不能只是留下"实现定义".

现在,C 无论如何都可以处理内存,mem库中的函数(in <string.h>,甚至!)提供了处理内存所需的所有工具,作为一对指针和大小. C语言中的所谓"字符串"仅用于一个目的:在写入用于文本终端的操作系统的上下文中显示消息.而且,为此,空终止就足够了.

Answer 6

显然,对于性能和安全性,您需要在使用它时保持字符串的长度,而不是重复执行strlen或等效.但是,将长度存储在字符串内容之前的固定位置是一个非常糟糕的设计.正如Jörgen在对Sanjit的回答的评论中所指出的那样,它排除了将字符串的尾部视为字符串,例如,在没有分配新内存(并且导致失败和错误处理的可能性)的情况下,这会使许多常见操作变得相似path_to_filename或filename_to_extension不可能. .当然还有一个问题是没有人能够同意字符串长度字段应该占用多少字节(大量不好的"Pascal字符串")

C让程序员选择是否/何处/如何存储长度的设计更加灵活和强大.但当然程序员必须聪明.C惩罚愚蠢的程序崩溃,停止,或给你的敌人根.

Answer 7

懒惰,注册节俭和可移植性考虑到任何语言的汇编,特别是C比汇编高出一步(因此继承了许多汇编遗留代码).您会同意,因为null char在那些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个常见的字符串操作

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

复杂度O(n)其中大多数情况下PASCAL字符串是O(1),因为字符串的长度预先设置为字符串结构(这也意味着此操作必须在较早阶段进行).

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)和前置字符串长度不会改变操作的复杂性,而我承认它需要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也有它的问题,但是受到这里提出的问题的影响很小.

Answer 8

在许多方面,C是原始的.我喜欢它.

它比汇编语言高出一步,使用更易于编写和维护的语言为您提供几乎相同的性能.

null终止符很简单,不需要语言的特殊支持.

回想起来,它似乎并不方便.但是我在80年代使用汇编语言,当时看起来非常方便.我只是认为软件在不断发展,平台和工具不断变得越来越复杂.

Answer 9

假设C实现了Pascal方式的字符串,通过长度为它们加前缀:是一个7字符长的字符串,相同的DATA TYPE是3-char字符串？如果答案是肯定的,那么当我将前者分配给后者时,编译器应该生成什么样的代码？字符串应该被截断,还是自动调整大小？如果调整大小,该操作是否应该通过锁保护以使其线程安全？C方法方面解决了所有这些问题,不管你喜欢与否:)

Answer 10

不知怎的,我理解这个问题暗示C中没有编译器支持长度前缀字符串.下面的例子显示,至少你可以启动自己的C字符串库,其中字符串长度在编译时计算,使用如下结构:

#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;
}

但是,这不会带来任何问题,因为您需要特别小心何时专门释放该字符串指针以及何时静态分配(文字char数组).

编辑:作为一个更直接的问题答案,我认为这是C可以支持字符串长度可用的方式(作为编译时常量),如果你需要它,但如果你想使用它仍然没有内存开销只有指针和零终止.

当然,似乎使用零终止字符串是推荐的做法,因为标准库通常不会将字符串长度作为参数,并且因为提取长度char * s = "abc"不像我的示例所示那样简单.

Answer 11

有一点尚未提及：当设计 C 语言时，有许多机器的“char”不是八位（即使在今天也有 DSP 平台不是八位）。如果决定字符串要加上长度前缀，那么应该使用多少个“字符”的长度前缀？使用两个会对具有 8 位字符和 32 位寻址空间的机器施加人为的字符串长度限制，而在具有 16 位字符和 16 位寻址空间的机器上浪费空间。

如果想要有效地存储任意长度的字符串，并且“char”始终为 8 位，则可以（在速度和代码大小方面付出一些代价）定义一种方案，即以偶数为前缀的字符串N 的长度为 N/2 个字节，以奇数 N 和偶数 M（向后读）为前缀的字符串可以是 ((N-1) + M*char_max)/2 等，并且要求任何缓冲区声称提供一定量的空间来容纳字符串必须在该空间之前留出足够的字节来处理最大长度。然而，“char”并不总是 8 位这一事实会使这种方案变得复杂，因为保存字符串长度所需的“char”数量会根据 CPU 架构而变化。

Answer 12

"即使在32位机器上,如果你允许字符串是可用内存的大小,长度前缀字符串只比空终止字符串宽三个字节."

首先,对于短字符串,额外的3个字节可能是相当大的开销 特别是,零长度字符串现在需要4倍的内存.我们中的一些人正在使用64位计算机,因此我们要么需要8个字节来存储零长度字符串,要么字符串格式无法处理平台支持的最长字符串.

可能还存在对齐问题需要处理.假设我有一个包含7个字符串的内存块,例如"solo\0second\0\0four\0five\0\0seventh".第二个字符串从偏移量5开始.硬件可能要求32位整数在4的倍数处对齐,因此您必须添加填充,从而进一步增加开销.相比之下,C表示非常节省内存.(内存效率很好;例如,它有助于缓存性能.)