C:连接字符串的最佳和最快的方法是什么

我目前使用string.h库中的strcat()函数在c中连接字符串。

我想到了,我得出一个结论,它应该是非常昂贵的函数,因为它开始连接之前,它必须迭代char数组,直到它找到'\0'字符。

例如,如果我使用strcat()将字符串"horses" 1000次,我将需要支付(1 + 2 + 3 + ... + 1000) * strlen("horses") = (1000*1001)/2 * 6 = 3003000

我想到了非标准的方法,维护一个字符串长度的整数,然后发送到strcat()指向字符串末尾的指针:

 strcat(dest + dest_len, "string"); 

在这种情况下,我只需支付1000 * strlen("horses") = 1000 * 6 = 6000

6000远低于3003000 ,因此如果你进行大量此类连接,它对性能非常关键。

有没有更标准的方法来做到这一点,看起来比我的解决方案更好?

Joel Spolsky在他的Back to Basics文章中描述了使用strcat作为Shlemiel画家算法的低效字符串连接问题(阅读文章,它非常好)。 作为低效代码的一个例子,他给出了这个在O(n 2 )时间内运行的例子:

 char bigString[1000]; /* I never know how much to allocate... */ bigString[0] = '\0'; strcat(bigString,"John, "); strcat(bigString,"Paul, "); strcat(bigString,"George, "); strcat(bigString,"Joel "); 

第一次走过第一根绳子并不是一个真正的问题; 因为我们已经遍历了第二个字符串,所以一个 strcat的运行时间在结果的长度上是线性的。 但是,多个strcat是有问题的,因为我们一次又一次地遍历先前连接的结果。 他提供了这种选择:

我们如何解决这个问题? 一些聪明的C程序员实现了他们自己的mystrcat如下:

 char* mystrcat( char* dest, char* src ) { while (*dest) dest++; while (*dest++ = *src++); return --dest; } 

我们在这做了什么? 只需很少的额外费用,我们就会返回指向新的较长字符串末尾的指针。 这样,调用此函数的代码可以决定在不重新扫描字符串的情况下进一步追加:

 char bigString[1000]; /* I never know how much to allocate... */ char *p = bigString; bigString[0] = '\0'; p = mystrcat(p,"John, "); p = mystrcat(p,"Paul, "); p = mystrcat(p,"George, "); p = mystrcat(p,"Joel "); 

当然,这在性能上是线性的,而不是n平方,所以当你有很多东西要连接时,它不会受到降级的影响。

当然,如果您想使用标准C字符串,这就是您可以做的。 您正在描述缓存字符串长度并使用特殊连接函数(例如,使用稍微不同的参数调用strcat )的替代方法是对Pascal字符串的一种变体,Joel还提到:

Pascal的设计者意识到了这个问题,并通过在字符串的第一个字节中存储字节数来“修复”它。 这些被称为Pascal字符串。 它们可以包含零并且不会以空值终止。 因为一个字节只能存储0到255之间的数字,所以Pascal字符串的长度限制为255个字节,但由于它们不是空终止,因此它们占用与ASCIZ字符串相同的内存量。 关于Pascal字符串的好处是你永远不需要有一个循环来计算你的字符串的长度。 在Pascal中查找字符串的长度是一个汇编指令而不是整个循环。 它的纪念性更快。

很长一段时间,如果你想在你的C代码中放一个Pascal字符串文字,你必须写:

 char* str = "\006Hello!"; 

是的,您必须手动计算字节数,并将其硬编码到字符串的第一个字节中。 懒惰的程序员会这样做,并且程序很慢:

 char* str = "*Hello!"; str[0] = strlen(str) - 1; 

如果你想要它简单,快速,通用安全,我建议使用open_memstream()函数(它是POSIX-2008标准的一部分,不幸的是它没有进入C11标准,想到)。 它的工作原理如下:

首先,您将指针的地址和大小交给它

 char* result = NULL; size_t resultSize = 0; FILE* stream = open_memstream(&result, &resultSize); 

返回值是一个文件流,就像您使用fopen()打开文件一样。 因此,您可以使用fprintf() &co的整个库。 将您喜欢的任何内容流式传输到内存缓冲区,并自动为您分配和管理。 最重要的是,它还会跟踪累积字符串的大小,因此不必重新扫描它来计算其大小。

 for(int i = 0; i < 1000000; i++) { fprintf(stream, "current number is %d, or 0x%x\n", i, i); } 

最后,关闭流,它将更新结果指针和大小变量,以反映写入的实际字符串数据量。

 fclose(stream); //Now you have a zero terminated C-string in result, and also its size in resultSize. //You can do with it whatever you like. //Just remember to free it afterwards: free(result); 

假设你有两个字符串: s1s2 ,长度为l1l2连接意味着你应该生成一个长度为l1+l2的新字符串s3 。 该操作的时间复杂度为O(l1+l2) 。 从这个角度来看, strcat()似乎是最好的选择。

但是,如果要指示两个字符串连接的状态,则只需要记录它们的指针,即O(1) 。 一个简单的例子是这样的:

 typedef struct ConcatStr { char* str1; char* str2; } ConcatStr; ConcatStr myStrcat( char* str1, char* str2 ) { ConcatStr cstr; cstr.str1 = str1; cstr.str2 = str2; } 

要连接多个字符串,代码可以使用strlen()memcpy() ,它们通常都是经过优化的函数。

使用这种方法,易于添加便宜的size限制。
鉴于目标缓冲区可能溢出的真实机会,否则大小限制是必不可少的。

运行时间与字符串长度之和成正比:O(len(S [0])+ len(S [1])+ len(S [2])+ …)

 char *strsncat(char *dest, size_t size, char * strs[], size_t n) { assert(size > 0); size--; char *p = dest; while (n-- > 0) { size_t len = strlen(*strs); if (len >= size) { len = size; } size -= len; memcpy(p, *strs, len); strs++; p += len; } *p = '\0'; return dest; } void cat_test(void) { char dest[10]; char *strs[] = { "Red", "Green", "Blue" }; printf("'%s'\n",strsncat(dest, sizeof dest, strs, sizeof strs/sizeof strs[0])); // 'RedGreenB' } 

我使用这个变种,它更像是strcat的替代品,但不完全是:

 char* mystrcat(char** dest, const char* src) { int i = 0; char cur; while(1) { cur = src[i]; (*dest)[i] = cur; if(cur == 0) break; i++; } *dest += i; return *dest; } 

返回值在这里并不重要。 char数组char str[32]不包含指向字符的实际指针的存储(以再次获取指针),因此您可以执行以下操作:

 char str[32]; char* pStr = str; //storage for pointer mystrcat(&pStr, "bla"); mystrcat(&pStr, "de"); mystrcat(&pStr, "bla\n"); printf(str); 

要么

 myfunction(char* pStr) { mystrcat(&pStr, "bla"); mystrcat(&pStr, "de"); mystrcat(&pStr, "bla\n"); } char str[32]; myfunction(str); printf(str); 

因为现在在myfunction()的堆栈上创建了指针的存储空间。

长度受限的版本将是:

 char* mystrcat(char** dest, const char* src, int max) { int i = 0; char cur; while(1) { if(i == max) { (*dest)[i] = 0; break; } cur = src[i]; (*dest)[i] = cur; if(cur == 0) break; i++; } *dest += i; return *dest; } 

检查一下

https://john.nachtimwald.com/2017/02/26/efficient-c-string-builder/

它帮助我在眨眼之间将char **复制到剪贴板

  str_builder_t *sb; sb = str_builder_create(); int colcnt=0; for (int i=0;i 

这是一个迟到的答案,但我刚遇到同样的问题。 为了找到起点,我决定重新阅读strcpystrncpystrlenstrnlenstrcatstrncat的手册页。

我几乎错过了它,但幸运的是……在我的开发系统(Debian stretch)上有一个有趣的段落。 引用它(格式化我的):

strlcpy()

某些系统(BSD,Solaris和其他系统)提供以下function:

 size_t strlcpy(char *dest, const char *src, size_t size); 

此函数类似于strncpy() ,但它最多将size-1字节复制到dest ,始终添加一个终止空字节,并且不会使用(更多)空字节填充目标。 此函数修复了strcpy()strncpy()一些问题,但如果size太小,调用者仍必须处理数据丢失的可能性。 函数的返回值是src的长度 ,它允许容易检测到截断:如果返回值大于或等于size ,则发生截断。 如果数据丢失很重要,调用者必须在调用之前检查参数,或者测试函数返回值。 strlcpy()不存在于glibc ,并且没有被POSIX标准化,但可以通过libbsd库在Linux上获得。

是的,您正在阅读此权利:glibc函数的手册页包含对另一个库中非标准化函数的提示,可以更好地完成工作。 这可能certificate了这个问题的重要性。

顺便说一句,我永远不会str(n)cpy()为什么str(n)cpy()函数的设计者没有选择复制的字节数或指向dest的新结尾的指针作为返回值。 只返回dest似乎很愚蠢,因为这些函数不会改变那个参数,因此在每种情况下,当函数返回时调用者仍然知道它,因此这个选择没有任何意义。 我错过了什么?

在我了解strlcpy() ,我大多使用了自己的字符串连接函数,就像@Joshua Taylor在他的回答中所表达的那样。 不过,这个想法有其自身的问题:

逐字节扫描/复制字符串可能效率非常低。 根据目标CPU,我们应该使用32位甚至64位寄存器并一次复制多个字节。 当然,这使得函数更复杂,因为我们必须检查是否还有足够的字节要复制,如果没有,则使用下一个较小的寄存器大小。 为了进一步提高性能,我们应该使用汇编代码来实现我们的function。

AFAIK,像glibc和libbsd这样的库让它以这种方式实现。 所以最好使用libbsd实现。 不过,我还没有完成性能测量。