在现代编程领域,C语言的广泛应用无疑展现了它在高级语言和汇编语言中的独特优势。相比于其他编程语言,C语言的优势尤为明显。
译者 | 苏本如,责编 | 刘静
出品 | CSDN(ID:CSDNnews)
以下为译文:
在C语言的标准库<string.h>中,有关字符串处理的函数主要集中在复制和连接操作上。这些函数都涉及将字符从一个对象复制到另一个对象,并且通常会返回第一个参数,即目标对象的起始指针。这种设计也引发了效率上的问题,本文将对此进行详细探讨。
需要注意的是,文中的示例代码仅用于阐述,可能并不代表最佳实践。
标准解决方案
函数返回第一个参数的设计,有时会被使用者质疑。这种疑问在StackOverflow等讨论平台上屡见不鲜。例如,strcpy为何返回其第一个参数的讨论。实际上,这种设计源于历史,最初由Unix第七版引入,包括strcat、strncat、strcpy和strncpy等函数。尽管这些函数在Unix的各种版本中广泛使用,但其返回值往往被忽视。实际上,如果函数返回指向最后一个复制字符的位置,效率会更高。
连接两个字符串的操作复杂度与字符数量成线性关系。当函数返回指向目标字符串的指针时,效率会显著低于最佳水平。函数会遍历源字符串和目标字符串,并获取指向它们末尾的指针。如果返回指针指向第一个字符而非最后一个字符,NUL结束符的位置会丢失,必须重新计算。这种效率低下的现象在连接字符串s1和s2到目标缓冲区d的例子中尤为明显。例如:
```c
char *d1 = strcpy(d, s1); // pass 1 over s1
strcat(d1, s2); // pass 2 over the copy of s1 in d
```
因为strcpy返回的是d的值,所以d1与d相同。为了简化,我们在后续示例中直接使用d。strcat调用时,需要遍历刚复制到d1的字符串以确定最后一个字符的位置,这个过程与第一个字符串s1的长度成正比。最终的连接操作成本等于连接的字符串数量与总字符串长度的乘积,即接近二次方复杂度。这种低效率的现象有时被称为画师施莱米尔算法(更多见:.open-/jtc1/sc22/wg14//docs/n2349.htm#sad-string)。
值得一提的是,strcat和strcpy因不限制复制字符数量,容易导致缓冲区溢出,已经声名狼藉。
克服局限性的尝试
当源字符串长度未知且目标字符串大小固定时,遵循一些安全编码准则会导致冗余传递。例如,按照CERT关于安全使用strncpy和strncat的建议,如果目标区大小为dsize字节,可能会得到如下代码:
需要注意的是,当s1的长度大于d的大小时,strncpy的调用不会在d上追加NUL('\0')结束符。这是一个常见的误解。当s1短于dsize-1时,strncpy会用NUL('\0')填充剩余空间,而strncat则会覆盖这些字符。
为了减少冗余,程序员有时会计算字符串长度后使用memcpy,但这种方法效率也不高,且易出错,维护性差。
使用sprintf和snprintf进行连接
一些编译器(如GCC和Clang)通过将简单的sprintf和snprintf调用转换为strcpy或memcpy调用来提高效率,从而避免了部分I/O开销(参见/z/RaWkyd)。由于C库中没有完全等效的字符串函数,转换往往不会发生。memcpy因为复制的字节数完全相同而不合适,strncpy则因为覆盖了NUL结束符之后的位数而不适用。
由于额外的冗余传递,将snprintf调用转换为strlen和memcpy的序列产生的额外开销也被认为是不值得的。关于GCC优化器在这方面的限制及其改进措施,可参考“Better builtin string functions”部分。
POSIX的stpcpy和stpncpy函数
为了解决上述问题,POSIX标准引入了stpcpy和stpncpy函数。这些函数的实现方式是在遇到NUL结束符时,返回指向该字符的指针,从而缓解了效率低下的问题。
特别地,stpcpy可以在不考虑缓冲区溢出的情况下连接字符串:
但当字符串副本必须遵循目标大小限制时,使用stpncpy不会消除将第一个NUL字符之后的剩余目标空间清零并直到边界的开销。
这个函数仍然效率低下,因为每次调用都将目标中的剩余空间以及复制字符串的末尾空间清零,操作复杂度仍为二次方。效率低下的程度随目标大小增加而增加,而与被连接字符串的长度成反比。
OpenBSD的strlcpy和strlcat函数
为了应对strcpy和strcat的不足以及strncpy和strncat的缺点,OpenBSD项目在20世纪90年代末引入了strlcpy和strlcat函数,旨在提升字符串复制和连接的安全性(详见:.open-/jtc1/sc22/wg14//docs/n2349.htm)。
strlcpy与strncpy的主要区别在于返回值,strlcpy返回的是复制的字符数,而strncpy则返回指向目标的指针。strlcpy总是在目标中存储一个NUL结束符。连接s1和s2可以按如下方式使用strlcpy:
这种方法在使用性和简单性方面可以与snprintf相媲美,尽管snprintf的开销更大。
除了OpenBSD之外,strlcpy和strlcat也可在Solaris和Linux(在BSD兼容库中)找到。由于这些系统不受POSIX标准的约束,这两个函数并不总是存在。
POSIX的memccpy函数
POSIX还定义了memccpy函数,它结合了memcpy和memchr的特性,以及其他API的优点,用于解决上述问题。
这个函数可以扫描源序列查找指定字符的第一次出现,且最多将指定数量的字符从源序列复制到目标序列,而不会超出其范围。这解决了strncpy和stpncpy存在的一些问题。