就地替换字符串中的字符

Question

我有一个替换字符串中的字符的函数，它工作得很好！

然而，唯一的问题是，它需要另一个字符串作为缓冲区，修改后的文本将放置到该缓冲区中。

这对我来说是一场灾难，因为我的大部分工作都是关于I/O处理。因此，如果我使用calloc来包含一行，最多分配1024个字节，我将不得不复制它，以具有相同大小的修改版本(是的，1024个字节浪费在字符串替换上)。

下面是函数：

void replaceStr(buffer, haystack, needles, n_needles, rep)
    char *buffer;
    const char *haystack, **needles, *rep;
    const size_t n_needles;
{
    if (!buffer || !haystack || !needles || !rep)
        return;
    size_t rep_length = strlen(rep);
    char *found;
    for (int i = 0; i < n_needles; ++i) {
        const char *needle = needles[i];
        const size_t needle_length = strlen(needle);
        while ((found = strstr(haystack, needle))) {
            /* measure the length of what is before needle */
            size_t diff = found - haystack;
            /* copy that part until needle */
            strncpy(buffer, haystack, diff);
            /* copy needle (found == buffer + diff) */
            strcpy(buffer + diff, rep);
            /* adjust pointers */
            buffer += diff + rep_length;
            haystack = found + needle_length;
        }
        /* copy remaining string */
        strcpy(buffer, haystack);
    }
}

使用与buffer相同的字符串将导致：

• 更快的代码(对calloc的调用将是unneeded)
• Memory-efficient代码(同样，对calloc的调用将是unneeded)
• Neater代码。因为一行代码比三行代码(一行用于分配，一行用于函数调用，一行用于释放)要整洁得多(

您可能已经猜到了，我的问题是:如何使用相同的字符串作为buffer？

Answer 1

除非您能保证替换字符串rep始终与搜索字符串needle的大小完全相同，否则在寻找原始字符串的就地替换时，您的情况可能会变得更糟、更复杂，因为从算法上讲，您必须打乱整个字符串的内容。

然后，您将用O(N)线性复杂度的原始缓冲区中的字节交换替换固定时间的O(1)附加到输出缓冲区。

当您只是覆盖某个范围中的固定大小的元素时，或者如果您的算法涉及一个位于读指针后面的写指针，从而产生小于或等于原始大小的最终结果，则就地替换算法效果很好。在您的例子中，您正在处理可变大小的替换，并在相同的重叠位置读取和写入，这可能会导致更大的结果，这时您确实希望在内存中有一个单独的位置来输出结果，以提高效率，否则您将处理大量的开销，试图在同一内存中重复使用它。

通过接受指向输出缓冲区的指针，您的函数签名就很好。当然，如果调用代码在每次调用之前都对缓冲区执行callocs和frees操作，这显然会导致代码瓶颈。调用代码应该为每个线程重用相同的缓冲区，并将其向下传递到调用堆栈，以避免重新创建它。

现在，如果您希望优化调用代码以避免过多的callocs和frees，那么如果您不能有效地预先确定输出缓冲区大小的上限，那么这可能会很棘手。在这种情况下，重用相同的缓冲区，但在遇到需要更大的新输入用例时，还要跟踪它的大小和realloc (或者每次都简单地使用realloc )。然后继续重复使用它，然后冲洗，完成后重复和free。