空终止字符串的基本原理是什么?

尽管我很喜欢C和c++，但我还是忍不住对空结尾字符串的选择抓耳挠脑:

Length prefixed (i.e. Pascal) strings existed before C Length prefixed strings make several algorithms faster by allowing constant time length lookup. Length prefixed strings make it more difficult to cause buffer overrun errors. 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. On 16 bit machines this is a single byte. On 64 bit machines, 4GB is a reasonable string length limit, but even if you want to expand it to the size of the machine word, 64 bit machines usually have ample memory making the extra seven bytes sort of a null argument. I know the original C standard was written for insanely poor machines (in terms of memory), but the efficiency argument doesn't sell me here. Pretty much every other language (i.e. Perl, Pascal, Python, Java, C#, etc) use length prefixed strings. These languages usually beat C in string manipulation benchmarks because they are more efficient with strings. C++ rectified this a bit with the std::basic_string template, but plain character arrays expecting null terminated strings are still pervasive. This is also imperfect because it requires heap allocation. Null terminated strings have to reserve a character (namely, null), which cannot exist in the string, while length prefixed strings can contain embedded nulls.

其中一些东西比C语言出现得更晚，所以C语言不知道它们是有道理的。然而，在C语言出现之前，有些语言就已经很简单了。为什么会选择空终止字符串，而不是明显更好的长度前缀?

编辑:因为有些人问了关于我上面提到的效率点的事实(他们不喜欢我已经提供的事实)，他们源于以下几点:

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

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

When you need to cut off the start of a string and need to pass it to some method. You can't really do this in constant time with length prefixing even if you are allowed to destroy the original string, because the length prefix probably needs to follow alignment rules. In some cases where you're just looping through the string character by character you might be able to save a CPU register. Note that this works only in the case that you haven't dynamically allocated the string (Because then you'd have to free it, necessitating using that CPU register you saved to hold the pointer you originally got from malloc and friends).

上面这些词都没有length和concat常见。

下面的答案中还有一个断言:

你需要把绳子的一端剪掉

但这个是不正确的——对于以null结尾的字符串和有长度前缀的字符串，它的时间是相同的。(以Null结尾的字符串只是在你想要的新结尾的地方插入一个Null，长度前缀只是从前缀中减去。)

当前回答

空终止允许基于快速指针的操作。

2010-12-11 20:22:05

其他回答

GCC接受以下代码:

Char s[4] = "abcd";

如果我们把is当作字符数组，而不是字符串数组，这是可以的。也就是说，我们可以使用s[0]， s[1]， s[2]和s[3]，甚至使用memcpy(dest, s, 4)访问它。但是当我们尝试使用put (s)时，我们会得到混乱的字符，或者更糟糕的是使用strcpy(dest, s)。

2017-06-20 01:21:12

在很多方面，C语言是原始的。我很喜欢。

它比汇编语言高了一步，用一种更容易编写和维护的语言提供了几乎相同的性能。

空结束符很简单，不需要语言的特殊支持。

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

2010-12-11 23:02:16

假设C以Pascal的方式实现字符串，通过前缀长度:7字符长字符串与3字符字符串的数据类型相同吗?如果答案是肯定的，那么当我将前者分配给后者时，编译器应该生成什么样的代码?字符串应该被截断，还是自动调整大小?如果调整大小，该操作是否应该被锁保护以使其线程安全?不管你喜不喜欢，C语言的方法回避了所有这些问题。

2010-12-12 04:26:17

Calavera是对的，但由于人们似乎没有理解他的观点，我将提供一些代码示例。

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

如果C语言有一个字符串类型，比如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来定义字符串:

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

此时，所有的字符串操作都需要进行两次分配，这实际上意味着您将通过一个库来进行任何处理。

有趣的是……这样的结构体在C中确实存在!它们只是不用于日常显示消息给用户处理。

所以，这就是Calavera的观点:在c语言中没有字符串类型，要对它做任何事情，你必须获取一个指针，并将其解码为指向两个不同类型的指针，然后字符串的大小就变得非常相关，而不能仅仅是“实现定义”。

现在，C可以以任何方式处理内存，并且库中的mem函数(甚至在<string.h>中!)提供了将内存作为一对指针和大小来处理所需的所有工具。C语言中所谓的“字符串”的创建只有一个目的:在为文本终端编写操作系统的上下文中显示消息。因此，空终止就足够了。

2010-12-13 11:41:05

即使在32位机器上，如果允许字符串的大小与可用内存相同，带前缀的长度字符串也只比以空结尾的字符串宽3个字节。

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

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

2012-07-23 12:45:26

空终止字符串的基本原理是什么?

推荐文章

标签

最新文章