c - 就地替换字符串中的字符

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);
    }
}

与缓冲区具有相同的字符串会导致:
- 更快的代码(不需要调用 calloc)
- 内存高效代码(同样，不需要调用 calloc)
- 更整洁的代码。因为一行代码比三行代码(一行用于分配，一行用于函数调用，一行用于释放)要整洁得多

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

Answer 1

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

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

如果您只是简单地覆盖一个范围内的固定大小的元素，或者如果您的算法涉及一个写指针落后于读指针并产生小于或等于的最终结果，则就地替换算法非常有效到原来的大小。在您的情况下，您正在处理可变大小的替换并在相同的重叠位置进行读写，这可能会导致更大的结果，而那时您真的希望在内存中有一个单独的位置来输出结果以提高效率，否则您将处理围绕同一内存进行大量开销改组以尝试重用它。

您的函数签名可以接受指向输出缓冲区的指针。自然地，如果调用代码 callocs 和 frees 缓冲区每次在调用它之前，这显然会导致容易出现瓶颈的代码。调用代码应该为每个线程重用相同的缓冲区并将其向下传递到调用堆栈以避免重新创建它。

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