C：连接字符串的最佳和最快方式是什么

Question

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

我想到了这一点，我得出了一个结论，即它应该是非常昂贵的函数，因为在开始连接之前，它必须遍历char数组，直到找到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，所以如果您进行大量这样的连接，它对性能可能非常关键。

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

Answer 1

乔尔斯波斯基在他的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的设计者意识到了这个问题，并通过 “在该字符串的第一个字节中存储了一个字节数”来“修复”这个问题。这些被称为 Pascal字符串。它们可以包含零并且不是空的。 因为一个字节只能存储0到255之间的数字，所以Pascal 字符串的长度限制为255个字节，但由于它们不是 空终止，它们占用与ASCIZ 字符串相同数量的内存。关于Pascal字符串的好处是，你永远不会有 有一个循环来确定你的字符串的长度。查找 Pascal中字符串的长度是整个循环的一个汇编指令，而不是 。它的速度非常快。

...

很长一段时间，如果你想把一个Pascal字符串字面量在 C代码，你必须写：

char* str = "\006Hello!"; 

是的，你必须以计算字节手，你自己，并将其 硬编码为字符串的第一个字节。懒惰的程序员会做到这一点， 并有缓慢的程序：

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

Answer 2

假设你有两个字符串：s1和s2长度为l1和l2串联意味着你应该产生一个新的字符串s3长度为l1+l2。此操作的时间复杂度为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; 
} 

Answer 3

如果你想让它方便，快捷，一般情况下，和安全，我建议使用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); 

Answer 4

要连接多个字符串，代码可以使用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' 
} 

Answer 5

我用这个变体更是一个下拉更换为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 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; 
} 

Answer 6

入住这

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

它帮助我复制一个字符**在眨眼间到剪贴板

str_builder_t *sb; 
    sb = str_builder_create(); 

         int colcnt=0; 
         for (int i=0;i<nrF;i++) // nrF = number of Fileds 
        { 
          //strcat(DATA,sqlite_array[i]); 
        str_builder_add_str(sb, sqlite_array[i], 0); 
          if (colcnt<nrofcolumns) // my list view 
           { 
          str_builder_add_str(sb, "\t", 0); 
           colcnt++; 

          } 
           if (colcnt==nrofcolumns) 
          { 

          str_builder_add_str(sb, "\n", 0); 
            colcnt=0; 
          } 

        } 

    HANDLE glob =GlobalAlloc(GMEM_FIXED,str_builder_len(sb)+1); 
    memcpy(glob,str_builder_peek(sb),str_builder_len(sb)+1); 
    OpenClipboard(NULL); 
    EmptyClipboard(); 
    SetClipboardData(CF_TEXT,glob); 
    CloseClipboard();