在C语言中如何高效地复制和连接字符串？

时间：2020-07-20 16:23:35

关键字： C语言字符串

手机看文章

扫描二维码
随时随地手机看文章

[导读]来源：CSDN 就目前而言，在编程领域中，C语言的运用非常之多，它兼顾了高级语言的汇编语言的优点，相较于其它编程语言具有较大优势。在所有标准C语言头文件中声明的字符串处理函数中，最常用的是那些用来复制和连接字符串的函数。这两组函数都将

来源：CSDN

就目前而言，在编程领域中，C语言的运用非常之多，它兼顾了高级语言的汇编语言的优点，相较于其它编程语言具有较大优势。

在所有标准C语言<string.h>头文件中声明的字符串处理函数中，最常用的是那些用来复制和连接字符串的函数。这两组函数都将字符从一个对象复制到另一个对象，并且都返回它们的第一个参数：指向目标对象的起始指针。这种返回值的方式是导致函数效率低下的一个原因，而这正是本文要探讨的主题。

本文中展示的示例代码仅仅用于说明目的。它们可能包含细微的错误，不应该被视为最佳代码实践。

标准解决方案

这种返回函数的第一个参数的设计，有时候会被不明白其用途的用户所质疑。这样的例子在StackOverflow网站上有不少，例如关于strcpy()返回值，或者C语言的strcpy为什么返回它的参数？的讨论。简单的答案是，这是一个历史性的意外。函数的第一个子集是由Unix第七版在1979年引入的，它由strcat、strncat、strcpy和strncpy函数组成。尽管这四个函数都在Unix的各种版本中使用，但通常情况下，对这些函数的调用却没有使用它们的返回值。尽管这些函数可以同样很容易地定义为返回一个指针来指向最后一个复制的字符（或它的后一位），而且事实证明这种做法也非常有用。

两个或多个字符串的连接操作的最佳复杂度和字符数量成线性关系。但是，如上所述，让函数返回指向目标字符串的指针会导致操作的效率明显低于最佳效率。该函数遍历源字符串序列和目标字符串序列，并获取指向这两个序列末尾的指针。该指针指向函数（strncpy除外）附加到目标序列上的字符串结束符NUL（'\0'）处或它的后一位。但是，如果返回的指针指向第一个字符而不是最后一个字符（或它的下一个字符），NUL结束符的位置会丢失，必须在需要时重新计算。这种做法的低效率可以在将两个字符串s1和s2连接到目标缓冲区d中的示例中得到说明。将一个字符串添加到另一个字符串的惯用方法（虽然远非理想）是调用strcpy和strcat函数，如下所示：

    
     strcat (
     strcpy (d, s1), s2);

为了执行这个连接操作，除了同时发生的相应地在d上的传递之外，一次在s1的传递和一次在s2上的传递是必须要执行的操作，但是上面的调用在s1上进行了两次传递。让我们把这些调用分成两个语句。

    
     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，而不是将返回值存储在d1中并使用它。在strcat调用中，我们遍历刚刚复制到d1的字符串以确定最后一个字符的位置，这个成本和第一个字符串s1的长度是线性关系。这个成本乘以每个要连接的字符串。因而最终整个连接操作的成本相当于连接数和所以字符串长度的乘积，趋于一种二次方的关系。这种低效率是如此的臭名昭著，以至于为自己赢得了一个名字：画师施莱米尔算法。（另见http://www.open- std.org/jtc1/sc22/wg14/www/docs/n2349.htm#sad-string）

必须指出的是，除了效率低下之外，strcat和strcpy还因其缓冲区溢出的问题而臭名昭著，因为它们都对复制字符的数量不做任何限制。

克服局限性的尝试

当源字符串的长度未知且目标字符串大小固定时，遵循一些流行的安全编码准则来将连接结果限制为目标区大小实际上会导致两个冗余的传递。例如，按照CERT关于安全使用strncpy()和strncat() 的建议，并且目标区的大小是dsize字节，我们可能会得到以下代码。

    
     strncpy (d, s1, dsize - 
     1);      
     // pass 1 over s1 plus over d up to dsize - 1
     
    d[dsize - 
     1] = 
     '\0';             
     // remember to nul-terminate
     
    
     size_t n = 
     strlen (d);           
     // pass 2 over copy of s1 in d
     
    
     strncat (d, s2, dsize - n - 
     1);  
     // pass 3 over copy of s1 in d

注意，与对strncat的调用不同，当s1的长度大于d的大小时，上面对strncpy的调用不会将NUL('\0')结束符追加到d上。它是一个常见的想当然的错误。此外，当s1短于dsize-1时，strncpy函数将所有剩余的字符填满为NUL('\0')，这也被视为一种浪费的，因为随后对strncat的调用将覆盖掉它们。

为了避免一些冗余，程序员有时会选择先计算字符串长度，然后使用memcpy，如下所示。这种方法仍然效率不高，而且更容易出错，并且代码难以阅读和维护。

    
     size_t s1len = 
     strlen (s1);      
     // pass 1 over s1
     
    
     if (dsize <= s1len)
     
          s1len = dsize - 
     1;            
     // no need to nul-terminate
     
    
     memcpy (d, s1, s1len);           
     // pass 2 over s1
     
    
     size_t s2len = 
     strlen (s2);      
     // pass 1 over s2
     
    
     if (dsize - s1len <= s2len)
     
          s2len = dsize - s1len - 
     1;
     
    
     memcpy (d + s1len, s2, s2len);   
     // pass 2, over s2
     
    d[s1len + s1len] = 
     '\0';         
     // nul-terminate result

使用sprintf和snprintf进行连接

出于对代码复杂性和可读性的担心，程序员们有时会使用snprintf函数进行字符串连接。

    
     snprintf (d, dsize, 
     "%s%s", s1, s2);

这样做代码的可读性非常好，但是，由于snprintf的开销相当大，它的低效率导致它可能比使用字符串函数慢几个数量级。snprintf的开销不仅是由于解析格式字符串，而且还由于格式化I/O函数实现中通常固有的复杂性。

一些编译器（如GCC和Clang）试图通过将非常简单的sprintf和snprintf调用转换为strcpy或memcpy调用以提高效率，避免了对I/O函数的某些调用的开销（请参阅这个在线示例https://godbolt.org/z/RaWkyd）。然而，由于C库中没有等价的字符串函数，而只有当snprintf调用被证明不会导致输出的截断时，转换才会完成，因此对snprintf的相应转换很少能够发生。memcpy本身不合适，因为它复制的字节数与指定的字节数完全相同，strncpy也不适合，因为它把目标字符串的最后的NUL结束符之后的位数都覆盖了。

由于字符串的冗余传递次数，将snprintf调用转换为strlen和memcpy调用序列产生的额外开销，也被视为得不偿失。在这个页面上，标题为Better builtin string functions部分列出了GCC优化器在这方面的一些限制，以及改进它的一些折中措施。

POSIX的stpcpy和stpncpy函数

为了帮助解决这个问题，在过去很多年里出现了很多超出标准C的库解决方案。POSIX标准包括stpcpy和stpncpy函数，这两个函数的实现方法是如果找到NUL结束符，则返回指向该字符的指针。这些函数可以用来缓解上面提到的麻烦和低效率。

    
     const char* stpcpy (char* restrict, const char* restrict);
     
    
     const char* stpncpy (char* restrict, const char* restrict, size_t);

特别是，在不考虑缓冲区溢出的情况下，可以像下面这样调用stpcpy来连接字符串：

    
     stpcpy (stpcpy (d, s1), s2);

然而，当字符串副本必须以目标大小为边界时，等效地使用stpncpy并不会消除将第一个NUL字符之后的剩余目标位置清零并直到边界指定的最大字符位置的开销。

    
     char *ret = stpncpy (d, dsize, s1);   
     // zeroes out d beyond the end of s1
     
    dsize -= (ret - d);
     
    stpncpy (d, dsize, s2);               
     // again zeroes out d beyond the end

所以，这个函数仍然效率低下，因为对它的每次调用都会将目标中剩余的空间以及复制的字符串的末尾的空间清零。因此，这个操作的复杂性仍然是二次方的。效率低下的严重程度随着目标的大小成比例地增加，而与被连接的字符串的长度成反比增加。

OpenBSD的strlcpy和strlcat函数

为了应对针对strcpy和strcat函数的弱点以及上面讨论的strncpy和strncat的一些缺点的缓冲区溢出攻击，OpenBSD项目在20世纪90年代末引入了一对替代API（strlcpy和strlcat），旨在使字符串复制和连接更加安全(http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2349.htm)。

    
     size_t strlcpy (
     char* 
     restrict, 
     const 
     char* 
     restrict, 
     size_t);
     
    
     size_t strlcat (
     char* 
     restrict, 
     const 
     char* 
     restrict, 
     size_t);

strncpy和strlcpy函数之间的主要区别在于返回值：前者返回指向目标的指针，后者则返回复制的字符数。另一个区别是strlcpy函数总是在目标中只存储一个NUL结束符。要连接s1和s2，可以按以下方式使用strlcpy函数：

    
     size_t n = strlcpy (d, s1, dsize);
     
    
     dsize -= n;
     
    
     d += n;
     
    
     strlcpy (d, s2, dsize);

这使得strlcpy在使用性和简单性方面都可以与snprintf相提并论（当然snprintf的开销虽然恒定，但要大得多）。

除了OpenBSD以外，strlcpy和strlcat函数在其他系统上也可用，包括Solaris和Linux（在BSD兼容库中）。但是由于这些系统不是由POSIX指定的，所以这两个函数在那些系统中并不总是存在。

POSIX的memccpy函数

POSIX还定义了另一个函数memccpy，该函数具有上面讨论过的所有理想属性，可以用来解决上面的问题。

    
     void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n);

这个函数结合了memcpy、memchr的特性以及上面讨论的API的最佳方面的特性。

和memchr一样，它会扫描源序列以查找由其参数之一指定的字符的第一次出现。字符可以是任何值，包括零。
和strlcpy一样，它最多将指定数量的字符从源序列复制到目标序列，而不会写入超出其范围。这解决了有关strncpy和stpncpy的低效率的报怨。
和stpcpy和stpncpy类似（尽管不完全相同），它返回一个指针，该指针指向指定字符的副本（如果存在）的后一位。（回想一下stpcpy和stpncpy返回一个指向复制的NUL的指针。）这避免了strcpy和strncpy固有的低效性。

因此，可以使用memccpy重写上面的第一个示例（strcat（strcpy（d，s1，s2））以避免在字符串上进行任何冗余传递，如下所示。请注意，这里使用SIZE_MAX作为大小限制,这个重写无法避免原始示例中存在的目标缓冲区溢出的风险，因此应避免。

    
     memccpy (memccpy (d, s1, 
     '\0', SIZE_MAX) - 
     1, s2, 
     '\0', SIZE_MAX);

为了避免缓冲区溢出的风险，需要为每个调用确定适当的大小限制并作为参数提供。因此，像在snprintf(d, dsize, "%s%s", s1, s2)函数中那样限制目标大小的连接调用，可以像下面这样计算目标大小：

    
     char *p = memccpy (d, s1, 
     '\0', dsize);
     
    
     dsize -= (p - d - 
     1);
     
    
     memccpy (p - 
     1, s2, 
     '\0', dsize);

选择一个解决方案

如果字符串函数返回指向最后一个存储字符或它的后面一位的指针，而不是返回其第一个参数的值，则上面讨论的效率问题可以得到解决。然而，在现有函数使用了接近半个世纪后，对其进行更改是不太可行的。

尽管解决现有C标准字符串函数的问题是不可行的，但是可以通过添加一个或多个不受相同限制的函数来在新代码中缓解这个问题。由于C标准的章程正在对现有的实践进行编纂整理，所以C语言标准化委员有义不容辞的责任调查这种功能是否已经存在于流行的实现中，如果已经存在，则应该考虑采纳它们。如上文提到的这几种解决方案。

在上面提到的解决方案中，memccpy函数是最通用和最高效的，它由ISO 标准支持。即使在POSIX标准实现之外，它的应用范围最广，争议最小。

相比之下，stpcpy和stpncpy函数的通用性较差，stpncpy函数会产生不必要的开销，因此无法达到既定的目标。这些函数在C2X中仍然值得采用，以提高移植性。详情请参阅N2352–将stpcpy和stpncpy添加到C2X中的提案。

OpenBSD的strlcpy和strlcat函数虽然是最优的，但是它们的通用性较差，支持范围也较低，而且没有得到ISO标准的指定。

memccpy函数不仅存在于Unix实现的子集中，它还由另一个名为ISO/IEC 9945的ISO标准指定。ISO/IEC 9945还有另外一个名字，也即大家熟知的IEEE Std 1003.1, 2017版，或者简言之- POSIX: memccpy，在那里它是作为XSI扩展提供给C的。这个函数可以追溯到System V接口定义第1版（SVID1），最初于1985年发布。

memccpy甚至可以用于UNIX和POSIX以外的实现，例如：

安卓系统中的memccpy函数,
苹果Mac OS X中的memccpy函数,
BlackBerry Native SDK 的memccpy函数，
Compaq Run-Time Library for VAX中的memccpy函数,
微软Visual Studio C Runtime Library中的 memccpy 函数,
IBM z/OS 中的memccpy函数.

下面提供了一个简单（但是效率低下）的memccpy参考实现：

    
      
     void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n)
      {
     
        
     void *pc = 
     memchr (src, c, n);
     
        
     void *ret;
     

     
        
     if (pc)
     
        {
     
          n = (
     char*)pc - (
     char*)src + 
     1;
     
          ret = (
     char*)dst + n;
     
        }
     
        
     else
     
          ret = 
     0;
     

     
        
     memcpy (dst, src, n);
     
        
     return ret;
     
      }

这个函数的一个更优化的实现可能如下。

    
      
     void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n)
      {
     
        
     const 
     char *s = src;
     
        
     for (
     char *ret = dst; n; ++ret, ++s, --n)
     
        {
     
          *ret = *s;
     
          
     if ((
     unsigned 
     char)*ret == (
     unsigned 
     char)c)
     
            
     return ret + 
     1;
     
        }
     
        
     return 
     0;
     
      }

借助于memccpy的性能优化，编译器将能够把对snprintf (d, dsize, "%s", s)函数的简单调用转换为对memccpy(d, s, '\0', dsize)的最佳有效调用。通过以代码大小换取速度，激进的优化器甚至可以将符合下列条件的snprintf函数调用(其格式字符串由多个%s指令组成，这些指令中间穿插有普通字符，如%s/%s)转换成一系列的此类memccpy函数调用：如下所示

    
     char *p = memccpy (d, s1, 
     '\0', dsize);
     
      
     if (p)
     
      {
     
        
     --p;
     
        p = memccpy (p, 
     "/", 
     '\0', dsize - (p - d));
     
        
     if (p)
     
        {
     
          
     --p;
     
          p = memccpy (p, s2, 
     '\0', dsize - (p - d));
     
        }
     
      }
     
      
     if (!p)
     
        d[dsize - 
     1] = 
     '\0';