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

Question

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

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

例如,如果我"horses"使用1000 连接字符串strcat(),我将不得不付费 (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,所以如果你做了很多这样的连接,它对于性能来说非常关键.

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

Answer 1

乔尔·斯波尔斯基(Joel Spolsky)在他的" 回归基础知识 "(Back to Basics)一文中,描述了低效的字符串连接问题,strcat作为画家的算法Shlemiel(阅读文章,这是非常好的).作为低效代码的一个例子,他给出了这个在O(n ²)时间内运行的例子:

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但是,多个s是有问题的,因为我们一次又一次地遍历先前连接的结果.他提供了这种选择:

我们如何解决这个问题？一些聪明的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;

Answer 2

如果你想要它简单,快速,通用和安全,我建议使用该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);