我目前在c语言中使用string.h库的strcat()函数来连接字符串。
我想了一下，得出一个结论：这应该是非常昂贵的函数，因为在开始连接之前，它必须迭代字符数组直到找到'\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 小了500倍，因此如果您进行许多这样的连接操作，它可能对性能非常关键。
是否有一种更标准的方法来执行此操作，比我的解决方案更好看？
在他的回归基础文章中，Joel Spolsky描述了使用strcat进行字符串拼接的低效问题，称之为Shlemiel the painter's algorithm（读一下这篇文章，非常好）。作为低效代码的例子，他给出了以下运行时间为O(n2)的示例：
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字符串，这就是您可以做的。您所描述的另一种选择是缓存字符串的长度并使用特殊的连接函数（例如，使用略有不同的参数调用How do we fix this? A few smart C programmers implemented their own
mystrcatas follows:char* mystrcat( char* dest, char* src ) { while (*dest) dest++; while (*dest++ = *src++); return --dest; }What have we done here? At very little extra cost we're returning a pointer to the end of the new, longer string. That way the code that calls this function can decide to append further without rescanning the string:
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 ");This is, of course, linear in performance, not n-squared, so it doesn't suffer from degradation when you have a lot of stuff to concatenate.
strcat），这有点像Pascal字符串的变体，Joel也提到了这点：
The designers of Pascal were aware of this problem and "fixed" it by storing a byte count in the first byte of the string. These are called Pascal Strings. They can contain zeros and are not null terminated. Because a byte can only store numbers between 0 and 255, Pascal strings are limited to 255 bytes in length, but because they are not null terminated they occupy the same amount of memory as ASCIZ strings. The great thing about Pascal strings is that you never have to have a loop just to figure out the length of your string. Finding the length of a string in Pascal is one assembly instruction instead of a whole loop. It is monumentally faster.
…
For a long time, if you wanted to put a Pascal string literal in your C code, you had to write:
char* str = "\006Hello!";Yep, you had to count the bytes by hand, yourself, and hardcode it into the first byte of your string. Lazy programmers would do this, and have slow programs:
char* str = "*Hello!"; str[0] = strlen(str) - 1;
char* str = "*Hello!"; 中的字符串字面量，该字符串会自动以 null 结尾。如果要得到一个 没有 null 结尾的字符串，实际上需要创建一个字符数组，并将六个字符 'H'、'e'、...、'o'、'!' 放入其中。 - Joshua Taylormystrcat 中，如果添加 src 会超出 dest 可用的空间，则必须防止越界。这是一个很好的例子，但可能值得传递指向 dest 剩余可用字符数的指针，以防止出现此情况。 - David C. Rankinstrcat() 这个函数设计得如此低效... 我原以为 C 语言的创造者会更加周到一些... - 71GAopen_memstream()函数（它是 POSIX-2008 标准的一部分，不幸的是它没有被包含在 C11 标准中）。它的使用方法如下：char* result = NULL;
size_t resultSize = 0;
FILE* stream = open_memstream(&result, &resultSize);
返回值就像你使用fopen()打开文件一样是一个文件流。因此，你可以使用整个fprintf()系列函数将任何东西流式传输到自动分配和管理的内存缓冲区中。最重要的是，它还会跟踪累积字符串的大小，因此不必重新扫描以计算其大小。
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);
为了将多个字符串连接起来，代码可以使用 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'
}
strcpy、strncpy、strlen、strnlen、strcat和strncat的手册页面。man strcpy中有一个有趣的段落。引用它（格式化为我的）：
strlcpy()Some systems (the BSDs, Solaris, and others) provide the following function:
size_t strlcpy(char *dest, const char *src, size_t size);This function is similar to
strncpy(), but it copies at mostsize-1bytes todest, always adds a terminating null byte, and does not pad the target with (further) null bytes. This function fixes some of the problems ofstrcpy()andstrncpy(), but the caller must still handle the possibility of data loss ifsizeis too small. The return value of the function is the length ofsrc, which allows truncation to be easily detected: if the return value is greater than or equal tosize, truncation occurred. If loss of data matters, the caller must either check the arguments before the call, or test the function return value.strlcpy()is not present inglibcand is not standardized byPOSIX, but is available on Linux via thelibbsdlibrary.
没错，你没有看错：glibc函数的手册中包含了对另一个库中非标准化函数的提示，后者执行得更好。这可能证明了这个问题有多么重要。
顺便说一句，我永远不明白 str(n)cpy() 函数的设计者为什么没有选择返回复制的字节数或指向新的 dest 结尾的指针作为返回值。仅返回 dest 看起来很愚蠢，因为这些函数不会改变该参数，所以在每种情况下，调用者仍然知道函数何时返回，因此这个选择毫无意义。难道我错过了什么吗？
在我了解 strlcpy() 之前，我大多使用自己编写的字符串连接函数，类似于 @Joshua Taylor 在他的答案中展示的那样。然而，这个想法也有它自己的问题：
逐字节扫描/复制字符串可能非常低效。根据目标 CPU，我们应该使用 32 位甚至 64 位寄存器并一次复制多个字节。当然，这使得函数更加复杂，因为我们必须检查是否有足够的字节剩余需要复制，如果没有，就使用下一个较小的寄存器大小。为了进一步提高性能，我们应该使用汇编代码来实现我们的函数。
据我所知，像 glibc 和 libbsd 这样的库就是这样实现的。因此，最好使用 libbsd 的实现。不过我还没有进行过性能测量。
strcat在实际追加其他字符串之前会扫描现有字符串中的0，并抱怨与此相关的性能损失。然后他展示了如何通过维护一个始终包含现有字符串长度的临时变量，将问题的顺序从二次降低到线性。为了维护该变量，在每次循环中必须对追加的字符串调用strlen。strlcpy避免了这些多余的strlen调用。顺序当然仍然是线性的，但CPU时间可能会减少30%到50%（经验猜测）。 - undefineds1和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;
}
strcat 是线性的。但是如果有多个操作（例如，strcat(bigString,"John, "); strcat(bigString,"Paul, ");），那么最终你会做 O(n^2) 的工作，因为你会再次遍历之前连接的部分。不过对于单个情况，你是正确的：线性性能是可以接受的。 - Joshua Taylorint L=0;
char buffer[100000];
char *str[1000]; // assume this is already populated
for (int i=0; i<1000; i++) // 1000 or whatever number you actually have
{
L+=sprintf(buffer+L,"%s ",str[i]); // this is the important part
}
sprintf将返回写入的字符数，并继续推进指针buffer+L。这没有任何安全检查。您可以检查L是否超过100000，但这取决于您。如果buffer+L超出字符串的末尾，它将使您的应用程序崩溃。
请检查这个
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<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();
我使用这个变体，它更像是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;
}
src中的字符导致您写入dest[i]之外的位置（例如str），会发生什么？ - David C. Rankinstrcat()发生的情况相同；未为此目的分配的内存将被覆盖。因此，请使用足够大的缓冲区、进行输入验证或使用长度受限的版本。 - Rik Ruiter这里是一个简单、安全和高效的连接函数：
#include <stdio.h>
#include <string.h>
char *strwrite(char *dest, size_t size, size_t *ppos, const char *src) {
size_t pos = *ppos;
if (pos < size) {
size_t len = strlen(src);
if (pos + len < size)
memcpy(dest + pos, src, len + 1);
*ppos += len;
} else {
memcpy(dest + pos, src, size - pos - 1);
dest[size - 1] = '\0';
*ppos = size - 1;
}
}
return dest;
}
int main() {
char dest[10];
size_t pos = 0;
for (int i = 0; i < 3; i++) {
strwrite(dest, sizeof dest, &pos, "Test");
}
printf("%s\n", dest); // TestTestT
return 0;
}
在 POSIX 系统上，可以使用 strnlen() 函数简化代码：
char *strwrite(char *dest, size_t size, size_t *ppos, const char *src) {
size_t pos = *ppos;
if (pos < size) {
size_t len = strnlen(src, size - pos - 1);
memcpy(dest + pos, src, len);
pos += len;
dest[pos] = '\0';
*ppos = pos;
}
return dest;
}
snprintf(buf, len, "%s%s%s", str1, str2, str3)。 - Grijesh Chauhanstrcat()和维护字符串长度的方法不同，前者需要遍历目标字符串（O(n)），以寻找字符串结尾，而后者可以在常数时间内完成相同操作（O(1)）。 - Andreas Fester