在C语言中执行大量的字符串连接操作？

Question

我正在将一些Java代码移植到C，目前进展顺利。

然而，我有一个特定的Java函数，它大量使用StringBuilder，像这样：

StringBuilder result = new StringBuilder();
// .. build string out of variable-length data
for (SolObject object : this) {
    result.append(object.toString());
}
// .. some parts are conditional
if (freezeCount < 0) result.append("]");
else result.append(")");

我知道SO不是代码翻译服务，但我并不要求任何人翻译上面的代码。

我想知道如何在C语言中高效地执行这种大量字符串连接。大部分都是小字符串，但每个字符串都由条件确定，所以我不能将它们合并成一个简单的调用。

我该如何可靠地执行这种字符串连接？

- Alexis King

---

你严格使用C语言吗？还是也可以使用C++？ - Nico

你可以使用一堆sprintf()调用将它们组合起来。只需使用返回值... - wildplasser

@Nico 我正在使用纯C，我想避免使用C++。 - Alexis King

那么，“result”是什么？一些带有函数指针的结构体（有很多种）吗？顺便说一句：在C语言中，冒号只用于位域和标签。 - wildplasser

@wildplasser：这是Java。 - Daniel Sloof

啊，我明白了。嗯：每个人都想要冒号... - wildplasser

Answer 1

一种相当“巧妙”的将多个“对象”转换为字符串的方法是：

 char buffer[100];
 char *str = buffer;
 str += sprintf(str, "%06d", 123);
 str += sprintf(str, "%s=%5.2f", "x", 1.234567);

这是相当有效的，因为sprintf返回所复制字符串的长度，所以我们可以通过返回值“移动”str，并继续填充。当然，如果存在真正的Java对象，则需要找出如何将Java风格的ToString函数转换成C的printf家族中的“%something”。

- Mats Petersson

---

请确保您使用sprintf格式化的内容不超过99个字符（留一个字符给终止空字符），否则会导致缓冲区溢出，可能会出现分段错误。 - Alex Reynolds

我最终使用缓冲区溢出检查来完成这个任务（如果有必要，使用reallocf进行重新分配）。我想如果它最终成为一个问题，我会稍后对其进行优化，但是目前看起来非常优雅！ - Alexis King

Answer 2

字符串拼接性能差的原因是内存重新分配。Joel Spolsky在他的文章Back to basics中讨论了这个问题。他描述了一种朴素的字符串拼接方法：

舍米尔成为了一名街头画家，负责画路中间的虚线。第一天，他拿着一桶油漆走到路上，完成了300码的路线。 "太棒了！"他的老板说，"你是个快速工作者！"并给了他一枚戈比。

第二天，舍米尔只完成了150码。 "嗯，显然不如昨天好，但你仍然是一个快速工作者。150码还算可以接受。"老板付给了他一枚戈比。

第三天，舍米尔只刷了30码的路线。 "只有30码！"老板大声喊道。 "这是不能接受的！第一天你完成了那么多的工作！发生了什么事？"

"我没办法，"舍米尔说。 "每天我离油漆桶越来越远了！"

如果可能的话，您希望在分配缓冲区之前知道目标缓冲区需要多大。唯一现实的方法是对您想要连接的所有字符串调用strlen。然后分配适当数量的内存并使用略微修改的strncpy版本，该版本返回指向目标缓冲区结尾的指针。

// Copies src to dest and returns a pointer to the next available
// character in the dest buffer.
// Ensures that a null terminator is at the end of dest.  If
// src is larger than size then size - 1 bytes are copied
char* StringCopyEnd( char* dest, char* src, size_t size )
{
    size_t pos = 0;
    if ( size == 0 ) return dest;

    while ( pos < size - 1 && *src )
    {
        *dest = *src;
        ++dest;
        ++src;
        ++pos;
    }
    *dest = '\0';
    return dest;
}

请注意，您必须将size参数设置为目标缓冲区剩余的字节数。

以下是一个示例测试函数：

void testStringCopyEnd( char* str1, char* str2, size_t size )
{
    // Create an oversized buffer and fill it with A's so that 
    // if a string is not null terminated it will be obvious.
    char* dest = (char*) malloc( size + 10 ); 
    memset( dest, 'A', size + 10 );
    char* end = StringCopyEnd( dest, str1, size );
    end = StringCopyEnd( end, str2, size - ( end - dest ) );
    printf( "length:  %d - '%s'\n", strlen( dest ), dest );
}

int main(int argc, _TCHAR* argv[])
{
    // Test with a large enough buffer size to concatenate 'Hello World'.
    // and then reduce the buffer size from there
    for ( int i = 12; i > 0; --i )
    {
        testStringCopyEnd( "Hello", " World", i );
    }
    return 0;
}

这句话的意思是“产生以下内容：”。

length:  11 - 'Hello World'
length:  10 - 'Hello Worl'
length:  9 - 'Hello Wor'
length:  8 - 'Hello Wo'
length:  7 - 'Hello W'
length:  6 - 'Hello '
length:  5 - 'Hello'
length:  4 - 'Hell'
length:  3 - 'Hel'
length:  2 - 'He'
length:  1 - 'H'
length:  0 - ''

- Steve

---

@wildplasser 我已经添加了一条注释，说明它永远不会终止目标字符串，并确保调用代码确保存在空终止符。 - Steve

在我看来，它仍然很糟糕。你只是通过名字来吹嘘自己（顺便说一句，Joel Spolsky有C++口音，所以你们在同一条船上）。让调用者负责NUL终止是一个非常糟糕的习惯，从API设计的角度来看。字符串就是字符串，接受它吧。注意：我不会点踩。我从不这样做。我认为那些相信这种做法的人注定会失败。 - wildplasser

顺便提一下：以“str”开头，后跟小写字母的标识符/函数名称被保留供标准库将来使用。 - wildplasser

更改了函数名称并确保始终附加空终止符。 - Steve

@wildplasser - 我非常确定它不会。但我确实意识到*dest = '\0'存在冗余的if检查。循环中的size - 1确保这是可以的。我添加了一个测试函数和测试输出。 - Steve

Answer 3

使用strcat()的性能问题在于它必须扫描目标字符串以查找终止的\0'，然后才能开始附加。

但请记住，strcat()不使用字符串作为参数，它使用指针作为参数。

如果您维护一个单独的指针，它始终指向要附加到的字符串的终止'\0'，则可以将该指针用作strcat()的第一个参数，这样它就不必每次重新扫描。同样，您可以使用strcpy()而不是strcat()。

保持此指针的值并确保有足够的空间留作练习。

注意：您可以使用strncat()来避免覆盖目标数组的末尾（尽管它会默默截断您的数据）。我不建议为此目的使用strncpy()。请参见我的抱怨。

如果您的系统支持它们，则（非标准）strcpy()和strlcat()函数对于此类事情可能很有用。它们都返回它们尝试创建的字符串的总长度。但是它们的使用会使您的代码不太可移植；另一方面，有开源实现可以在任何地方使用。

另一种解决方案是对要附加的字符串调用strlen()。这并不理想，因为它被扫描了两次，一次由strcat()，一次由strlen() - 但至少它避免了重新扫描整个目标字符串。

- Keith Thompson

---

"保持该指针的值并确保还有足够的空间留作练习。但是使用标准字符串函数似乎没有好的方法来实现这一点。不幸的是，标准字符串函数不返回指向终止符\0的指针，而是返回指向字符串开头的指针。我认为需要其他的字符串库来解决这个限制。" - Craig McQueen

你可以始终在传入的字符串上运行 strlen 并使用 mem* 函数集来避免另一个 strlen 调用。(以跟踪内存和字符串尾部) - Eugene

Answer 4

如果这样的操作非常频繁，你可以在自己的缓冲类中实现它们。例如（出于简洁性，省略了错误处理；-）：

struct buff {
        size_t used;
        size_t size;
        char *data;
        } ;

struct buff * buff_new(size_t size)
{
struct buff *bp;
bp = malloc (sizeof *bp);
bp->data = malloc (size);
bp->size = size;
bp->used = 0;
return bp;
}

void buff_add_str(struct buff *bp, char *add)
{
size_t len;
len = strlen(add);

        /* To be implemented: buff_resize() ... */
if (bp->used + len +1 >= bp->size) buff_resize(bp, bp->used+1+len);

memcpy(buff->data + buff->used, add, len+1);

buff->used += len;
return;
}

- wildplasser

Answer 5

鉴于这些字符串看起来很小，我倾向于只使用strcat，如果性能成为问题，则重新考虑。

您可以创建自己的方法，记住字符串长度，因此无需迭代字符串以查找结尾（如果您正在对长字符串进行大量附加，则可能是strcat的慢部分）

- John3136