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();