在 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] = '';  
     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,"");
     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;
}

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

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

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

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

Answer 2

如果您只需将 newstring 的大小设置为解决方案后的最大可能大小，则可以摆脱代码的第一部分来计算计数。

特别：

int newsize = origlen + (strlen(to) - strlen(from)) * origlen/strlen(from);

此外，与其多次调用 strlen（from），只需将其分配给一个变量（例如 srtlen_from）并使用它。

Answer 3

这是我

制作的一个版本，它几乎只使用指针（省略了错误检查等）（我还注意到它在某些情况下会失败）：

#include <cstring>
#include <cstdlib>
#include <iostream>
char* replaceSubstring(char *original, char *from, char *to)
{
// This could be improved (I was lazy and made an array twice the size)
    char* retstring = new char[std::strlen(original) * 2];
    int pos = 0;
    for (int i = 0; *(original + i); ++i)
    {   
        if (*(original + i) == *(from)) 
        {
            // Got a match now check if the two are the same
            bool same = true; // Assume they are the same
            for (int j = 1, k = i + 1; *(from + j) && *(original + k); ++j, ++k)
            {
                if (*(from + j) != *(original + k))
                {
                    same = false;
                    break;
                }
            }
            if (same)
            {
                // They are the same now copy to new array
                for (int j = 0; *(to + j); ++j)
                {
                    retstring[pos++] = *(to + j);
                }
                i += std::strlen(from) - 1;
                continue;
            }
        }
        retstring[pos++] = *(original + i);
    }
    retstring[pos] = '';
    return retstring;
}
int main()
{
    char orig1[] = "Replace all the places that say all";
    char* r1 = replaceSubstring(orig1, "all", "Replacement");
    std::cout << r1 << std::endl;
    delete [] r1;
    char orig2[] = "XXXXXX with something else XXXXXX";
    char* r2 = replaceSubstring(orig2, "XXXXXX", "hello");
    std::cout << r2 << std::endl;
    delete [] r2;
}

Answer 4

不言自明：http://ideone.com/ew5pL

这就是丑陋和笨重的样子——除了最后的 strlen 和 memcpy 之外，没有 C 功能。

我认为你的看起来不错，很紧凑。