循环内的 strcat() 与 sprintf()

Question

我有一个程序可以删除字符串中的所有变量。这些变量以“$”开头。因此，例如，如果我给出一个像 [1,2,$1,$2] 这样的字符串，它应该 return 只是 [1,2].

但是，哪个循环的性能更好？

这个：

while (token != NULL)
{
    if (*token != '$')
    {
        sprintf(dst, "%s,%s", dst, token);
    }
    token = strtok(NULL, "], ");
}

或者这个：

while (token != NULL)
{
    if (*token != '$')
    {
        strcat(dst, token);
        strcat(dst, ",");
    }
    token = strtok(NULL, "], ");
}

Answer 1

根据C11 standard 7.21.6.6 p2，描述sprintf：

If copying takes place between objects that overlap, the behavior is undefined.

所以您的第一个代码片段在从 dst 复制到 dst 时调用了未定义的行为。 strcat 方法没有这个问题。

Answer 2

两种方法都不受欢迎：

传递 sprintf 相同的指针作为 %s 格式说明符的目标和源具有未定义的行为。此外，如果目标数组不够大，sprintf 无法防止缓冲区溢出。
第二种方法有几个 strcat 调用有潜在的缓冲区溢出问题，并且由于重复扫描目标字符串以找到副本的位置而效率低下。

这是另一种方法：

char src[LINE_SIZE];
char dst[LINE_SIZE + 1];  /* dst is large enough for the copy */
int pos = 0;

token = strtok(src, "], ");
while (token != NULL) {
    if (*token != '$') {
        pos += sprintf(dst + pos, "%s,", token);
    }
    token = strtok(NULL, "], ");
}

Answer 3

strtok是破坏性的，所以这段代码执行后输入的字符串将无法使用。既然如此，还不如就地进行改造。这有几个优点，其中之一是您不需要分配任何内存（因为最终字符串不能比原始字符串长）。这也需要一些额外的簿记，但这提供了另一个优势：结果函数的执行时间与输入的大小成线性关系。在每次迭代中从头开始重新开始扫描输出缓冲区——正如您的两个解决方案所做的那样——使得函数 quadratic 在字符串的长度上。 [注 1] 二次算法的使用比替代标准库调用成本的微小差异要严重得多。
正如许多人提到的那样，以输出缓冲区与要打印的字符串之一之间存在重叠的方式调用 sprintf 是未定义行为。因此，您对 sprintf 的使用是不正确的，即使它可能在某些实现上似乎有效。
strcat 和 sprintf 都不能防止缓冲区溢出。您可以使用 snprintf（通过将新字符串放在累积缓冲区的末尾，而不是在每次迭代时用自身覆盖缓冲区的开头）或者您可以使用 strncat，但在这两种情况下你需要做一些额外的簿记工作。

下面是第一点中提出的算法的快速实现。请注意，它不会调用 malloc() 也不会在堆栈上分配任何字符串。另请注意，它使用 memmove 而不是 memcpy 在字符串中向前移动新发现的标记，以避免标记与其目的地重叠时出现问题。（memmove 允许重叠；memcpy、strcpy 和 strcat 不允许重叠。）

/* Compresses the string str in place by removing leading and trailing separator
 * characters (which are the characters in 'fs') and replacing any interior
 * sequence of separator characters with a single instance of 'ofs'.
 * Returns 'str'.
 */
char* compress(char* str, const char* fs, char ofs) {
  char* out = str;
  char* token = strtok(str, fs);
  while (token != NULL) {
    size_t tlen = strlen(token);
    memmove(out, token, tlen);
    out += tlen;
    *out++ = ofs;
    token = strtok(NULL, fs);
  }
  /* Overwrite the last delimiter (if there was one) with a NUL */
  if (out != str) --out;
  *out = 0;
  return str;
}

API 备注：

与原来的不同，这不会丢弃以 $ 开头的标记。添加这将是微不足道的。
另外，与原始函数不同的是，此函数避免了尾随 , 的麻烦。同样，如果有充分的理由，这将很容易改变。（但是，尾随逗号意味着只有一个标记的字符串最终会长一个字符，因此无法进行就地保证。）
我选择return压缩字符串的起始地址（与输入缓冲区的地址相同）与各种标准C接口保持一致。但是，在许多情况下，return out（这是尾随 NUL 的地址）会更有用，以便允许进一步连接而不必计算字符串的新长度。或者，可以 return 字符串的新长度，如 sprintf 那样 (return out - str;)
这个API是诚实的，它破坏了原始字符串（通过用转换后的字符串覆盖它）；仅在其输入上调用 strtok 但在单独的输出上调用 return 的函数可能会导致细微的错误，因为对于调用者来说原始字符串已被破坏并不明显。虽然在调用 strtok 后无法恢复字符串，但通过简单地复制原始字符串，很容易将就地算法转换为非破坏性算法：
```
/* Returns freshly allocated memory; caller is responsible for freeing it */
char* compress_and_copy(const char* str, const char* fs, char ofs) {
  return compress(strdup(str), fs, ofs);
}
```
当然有可能是原始的未简化函数没有保证生成较短字符串的特性；例如，它可能会扩展以 $ 开头的段，方法是将它们替换为变量的值。在这种情况下，有必要生成一个新字符串。

在某些情况下，甚至可能在大多数情况下，输出仍然会比输入短。但是人们应该抵制尽可能就地进行转换并仅在必要时才分配新字符串的诱惑。虽然它可能更有效，但它使分配所有权的规则变得复杂；你最终不得不说 "caller owns the returned string only if it is different from the original string"，这很笨拙而且容易发生事故。

所以如果这是实际用例，最佳解决方案（从干净 API 设计的角度来看）是使用 strspn() 和 strcspn() 非破坏性地遍历原始细绳。这需要更多的工作，因为它需要更多的簿记；另一方面，它避免了在识别令牌后重新计算 strlen(token) 的需要。

备注：

从技术上讲，时间与字符串长度和令牌数量的乘积成正比，但在最坏的情况下（令牌很短），这实际上是 O(n²).

循环内的 strcat() 与 sprintf()

strcat() vs sprintf() inside a loop

c

performance

loops

printf

strcat

API 备注：

备注：