c++ - 在 C++ 中搜索和替换 C 风格的字符串

Question

我正在尝试编写一个接受三个 C 风格字符串并返回一个 C 风格字符串的函数。此函数在 C 字符串中搜索所有出现的子字符串，并用不同的字符串替换它们。
这个程序有效但看起来很不优雅。我情不自禁地觉得它可以用一种不那么笨重的方式来完成。

char* replaceSubstring(char *original, char *from, char *to)
{
     int origlen = strlen(original);
     int i = 0;
     int count = 0;
     char *ptr;

     //figure out how many times the sub-string occurs in a string.
     //i couldn't figure out a way to avoid this loop
     while (i<origlen)
     {
           ptr = strstr(original+i, from);
           if (!ptr)
               break;
           else
           {
               i = ptr - original + 1;
               count++;
           }
     }
     //figure out what the size of the output string has to be
     int newsize = origlen + (strlen(to) - strlen(from)) * count;

     char *newstring = new char[newsize];  
     newstring[0] = '\0';  
     i = 0;
     while (i < origlen)
     {
          ptr = strstr(original+i, from);
          if (!ptr)
          {
               strcat(newstring,original+i);
               break;
          }
          else
          {
               //this looks extremely ugly and bulky...
               strncat(newstring, original+i, ptr-(original+i));
               strcat(newstring, to);
               i = i + ptr - (original + i) + strlen(from);
          }
     }
     strcat(newstring,"\0");
     return newstring;
}

有人可以就如何使这段代码更清晰和/或更高效提出任何建议吗？ 欢迎任何意见。 请不要建议改用类字符串。那不是一个选择。该函数必须使用 C 字符串

Answer 1

我想做的一项改进可能会同时提高优雅和效率，那就是

1. 分配一个整数数组，该数组将保存与给定字符串匹配的子字符串的索引。
2. 遍历字符串并找到所有匹配的子字符串，并将每个子字符串添加到数组中，根据需要重新分配更大的数组(因为您不想使用我推测的 STL；如果可以，请使用 std::vector std::list std::deque).
3. 根据原始字符串的长度和找到的子字符串数量为修改后的字符串分配新内存。
4. 同时迭代旧字符串和数组，将旧字符串中不匹配的部分复制到新字符串中。
5. 用替换字符串填充您留下的孔。

此外，我不会在函数内部动态分配内存，而是将其更改为接受调用者分配的缓冲区和最大缓冲区大小。这样，调用者可以完全负责内存的生命周期(如果他们愿意/可以使用自动内存)，您不必担心计算缓冲区大小(您依赖于调用者)。

---

编辑:

这是我快速创建的示例实现。如果有人发现任何错误，请告诉我，这很可能。 (如果您想自己弄清楚，您可能不想阅读此内容。)

char* strreplace(const char* haystack, const char* needle, const char* replacement) {
    // using deque for pop_front
    std::deque<const char*> positions;
    unsigned int haystacklen    = strlen(haystack),
                 needlelen      = strlen(needle),
                 replacementlen = strlen(replacement);

    for (const char* cur = haystack, *pos = strstr(cur, needle); pos; cur = pos + 1, pos = strstr(cur, needle))
        positions.push_back(pos);

    char* newstr    = new char[haystacklen + replacementlen * positions.size() + 1],
          dst       = newstr;
    const char* src = haystack;

    while (src <= haystack + haystacklen)
        if (!positions.empty() && src == positions.front()) {
            strcpy(dst, replacement);
            dst += replacementlen;
            src += needlelen;
            positions.pop_front();
        } else
            *dst++ = *src++;

    return newstr;
}

并且不要忘记删除[]该函数的返回值。

我在没有进行最大优化的情况下追求效率。例如，您可以在 positions.empty() 为假时执行一个 while 循环，然后当它变为真时，退出循环并直接执行 strcpy 用于其余部分，因为没有更多的替换要进行，这可以让您避免为 每个字符不必要地调用 positions.empty()，即使没有留下或根本没有替换。但我认为这是一个小问题，代码传达了这一点。

此外，我使用 std::list std::deque 删除所有数组管理代码，但如果您这样做，那应该是直截了当的想自己做。

正如 ildjarn 在评论中提到的，我从 list 更改为 deque 因为我使用了 size 成员，并且根据他的评论，它是在所有 C++11 之前的实现上不是 O(1)(通常是 O(n))，所以 deque 是恒定时间 size 会更有效率。